大一各科課件-離散圖論

圖 1圖 重點： (K?nigsbergbridgesdadab從四塊陸地的任何一塊出發(fā)，怎樣通過每座橋恰巧一次，哥尼斯堡七橋1736年 “哥尼斯堡的七座橋.LuChaojun, 路徑 閉圖G中包含其所有邊的簡單開路徑稱為G的路徑。圖G中包含其所有邊的簡單閉路徑稱為G的閉(回)路。Definition:AnEulercircuit(cycle)isacyclethattraverseseveryedgeofagraphexactlyonce.Ifthereisanopenpaththattraverseeachedgeonlyonce,itiscalledanEulerpath. c Eulercircuit:

Eulerpath:圖 有向 圖每個結點的出度和入度都相等的有向圖稱 有向圖找到了連通無向圖 定理6圖論8引8G的每個頂點的度數(shù)的d(v)2,則G（Ifd(G)>=2thenGcontainsaLetPbealongestpath(actually, alpathsuffices)inGletubeanendpointofP.SincePcannotbeextended,everyofuisavertexinSinced(u)>=2,uhasaneighborvinPviaanedgethatisnotinTheedge{u,v}completesthecyclewiththeportionofPfromvto圖論設G是連通無向圖，G 圖(每個結點都是偶結點 閉路。(WecallagraphEulerianifithasan(1)):對任一 回路沿ei進入v必然有ej從v出來，同時 閉路每條邊是不相同的，因此，必然結點的度是偶 （2）)對G的n用第二歸納法n0G令n∈I＋，設任意邊數(shù)少于n的連通 閉路。若G有n條邊，連通、偶結G是連 圖 引 G定理

設G有長度為m的回路C Cv0e1v1…vm-1emv0v0,v1,…,vm-1各不相同，并且{v0,v1,…,vm-1}{e1,e2,…,em}分別是C的結點集合和邊集合。定理G＝〈Ｖ，Ｅ，Ψ〉，vG是回路或有向回路當且僅當G的階與邊數(shù)相等，并且在G中存在這樣一條從v到v的閉路徑，使得除了v在該閉路徑中圖論G{e1em}，設有k個分支G1GkG是連通

的每個分支GiC都有公共結點設vni為的分支Gi（1ik）與C的一個公共結點，0n1…nkm–1。顯然，Gi為邊數(shù)小于n的連 點仍為偶結點）。由歸納假設：GiPi

vni到vni 閉路v0e1v1…en1P1en1+1…enkPkenk+1…vm- CCAnEuleriancomponentofAnAnEuleriancomponentof圖論Euler’sTheoremsareexamplesofexistencelswhetherornotsomethingbut lushowtocreatewewantaconstructivemethodforfindingEulerpathsand 圖論圖論pickanyvertextofromthatvertexpickanedgetotraverse(seebelowforimportantdarkenthatedge,asareminderthatyoucan'ttraverseittravelthatedge,comingtothenextrepeat2-4untilalledgeshavebeentraversed,andyouarebackattheAteachstageofthetheoriginalgraphminusthedarkened(alreadyused)edges=reducedimportantrule:nevercrossabridgeofthereducedgraphunlessthereisotherbridge:bridge(alsoknownasacut-edgeorcutarcoranisthmus)isanedgewhosedeletionincreasesthenumberofconnectedcomponents.Equivalently,anedgeisabridgeifandonlyifitisnotcontainedinanycycle.Thinkaboutit:whymustweobservethatEuleriangraphcontainsnoReduced Therestofthetripisobvious,andcompleteEulercircuit(F,C,D,A,C,E,A,B,D,圖論定理設G＝〈Ｖ，Ｅ，Ψ〉為連通無向圖，v1，v2∈Ｖ且v1v2。 G有一條從v1至v2的 G恰有兩個v1和v2證明：任取eE，并令Ψ′＝｛〈e，｛v1，v2｝〉｝，則G有一條從v1至v2的 G′中每個結點都是G中恰有兩個奇結點v1和

圖論定理設G為弱連通的有向圖。G是

G 圖論定理G為弱連通的有向圖。v1和v2GG有一條從v1至v2 路 dＧ＋(v1)＝dＧ－(v1)＋1，dＧ＋(v2)＝dＧ－(v2)G的其它結點vdＧ＋(v)＝ 圖論根據(jù)哥尼斯堡橋問題畫出的圖不 因此不存 圖論周游世界的數(shù)學 ) 二十個頂點 問：找一條從某城市出發(fā)，經(jīng)過每個城市恰好一次，并且最后：在圖中找出一條，并且，除始點和終點重合外，這條閉路所含結點是互不相同的。根據(jù)定理7.3.6，這 圖）：無向圖G中穿過每個頂點 圈,具有

定義13.4無向圖G中穿過每個頂點一次且僅一次的非閉合鏈，稱為鏈.有向圖D中穿過每個頂點一次且僅一次的非閉合通路，稱為通路.定理(Ore,1960(SufficientIfGisasimplegraphwithn≥3verticessuchforeachpairofnon-adjacentverticesu,v,thenGis證明首先證明G是連通圖。假設G非連通，則G至少有兩個連所有的v1inV（G1），v2in(V（G2），因為d（v1）≤n1-1d（v2）≤n2-1，故d（v1）+d（v2）≤n1+n2-2＜n-1，這與 ，因此，G必連通定理(NecessaryIfagraphGcontainsabridge,thatis,anedgewhoseremovaldisconnectsthegraph,thenGdoenothaveaHamiltoniancycle.定理(NecessaryForeachvert