大一各科課件-離散圖論

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

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

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

的每個(gè)分支GiC都有公共結(jié)點(diǎn)設(shè)vni為的分支Gi（1ik）與C的一個(gè)公共結(jié)點(diǎn)，0n1…nkm–1。顯然，Gi為邊數(shù)小于n的連 點(diǎn)仍為偶結(jié)點(diǎn)）。由歸納假設(shè)：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,圖論定理設(shè)G＝〈Ｖ，Ｅ，Ψ〉為連通無向圖，v1，v2∈Ｖ且v1v2。 G有一條從v1至v2的 G恰有兩個(gè)v1和v2證明：任取eE，并令Ψ′＝｛〈e，｛v1，v2｝〉｝，則G有一條從v1至v2的 G′中每個(gè)結(jié)點(diǎn)都是G中恰有兩個(gè)奇結(jié)點(diǎn)v1和

圖論定理設(shè)G為弱連通的有向圖。G是

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

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