大一各科課件-離散圖論

1圖論1圖論 圖論圖論樹(shù)、有向目的：樹(shù)的六種定義，了解分支、森林、生成樹(shù)、生成森、最小生成樹(shù)、枝、弦、基本回路、有向樹(shù)、有向優(yōu)二叉樹(shù)的算法、定位二元有序樹(shù)和有序森林的雙重點(diǎn)：樹(shù)的六種定義，各種概念、算法及基本的證明思2難點(diǎn)：通過(guò)樹(shù)的六種定義方式如何發(fā)現(xiàn)樹(shù)的各種性質(zhì)，大23圖論3圖論樹(shù)非循環(huán)的連通無(wú)向圖稱為樹(shù)4圖論4圖論圖論圖論定理G＝〈Ｖ，Ｅ，Ψn階無(wú)向圖?？梢韵铝鶄€(gè)條件等價(jià)G是連通的，又是非循環(huán)的G沒(méi)有自圈，并且對(duì)于G的任意兩結(jié)點(diǎn)v和v′，在G中 v至v′的基本路徑。G是連通的，v和v′是G的兩結(jié)點(diǎn)，e不是GΨ〈e，{v，v〉}G＋{e}Ψ′有唯一的G是連通的Ge，Ge5G是連通的，并且有n–1條邊。vi)G是非循環(huán)的，并且有n1條邊。證明參見(jiàn)P145–146（P193）。5圖論圖論定理定理12.2T是一個(gè)G(n,m)圖，則mn-1證明：用歸納法證明，對(duì)Tn對(duì)于n=1和n=2，定理顯然成立。設(shè)對(duì)于所有的(i,mi)樹(shù)(i<n)定理都成立。 T變成具有兩個(gè)連通分支的不連通圖，并且這兩個(gè)連通分 (n1,m1)樹(shù)和 和n2<n， n1- n2-1nn1+n2mm1+m21=n1-6+n2-1+1,所以，m=n–1,定理得證 6圖論圖論定理12.3：非平凡樹(shù)T中至少有兩片樹(shù)葉證明：設(shè)T為(n,m)圖，n>1，T因?yàn)椋篸ui2m=2(n–1 (m=n–1=2n–Tk片樹(shù)葉，則分支頂點(diǎn)為nk個(gè)，分支頂點(diǎn)的次數(shù)大于1，即至少為2。 2n–2≥k+2(n–k7 k≥ 78圖論8圖論圖論森每個(gè)分支都是樹(shù)的無(wú)向圖稱為森林 圖論圖論定如果森林F有n個(gè)結(jié)點(diǎn)，m條邊和kmn–k證明：n個(gè)頂點(diǎn)的樹(shù)有n-頂點(diǎn)，則：V1+V2+…+Vk

條邊，設(shè)每個(gè)分支有Vi(V1-1)+(V2-1)+…+(Vk-1)=圖論圖論生成樹(shù)、生成如果樹(shù)T是無(wú)向圖G的生成子圖，則稱TG的生成樹(shù)FG的生成子圖，則稱FSpanningTree–圖論圖論找連通圖的生成樹(shù)找連通圖G的生成樹(shù)的方法 1、避圈法

添加e1，…，ei，在添加的每一步均保證：ei+1不與{e１，…，ei}的任何子集構(gòu)成回路。2、破圈法：在G0(即G)，G1，G2，…中去掉e1，e2，e3，…eiGi-1即把G中的所有回路均挑若Gi無(wú)圈，則TG←Gi并終止；否則轉(zhuǎn)+1←Gi- 圖論 圖，G′G 長(zhǎng)度之和稱為G′ 長(zhǎng)度設(shè)G是連通無(wú)向圖，〈G，W〉 圖G的所有生成樹(shù) 長(zhǎng)度最小者稱為〈G，W〉的最小生成樹(shù) MinimumSpanningTreeAminimumspanningtreeisasubgraphofanundirectedweightedgraphG,suchthatitisatree(i.e.,itisitcoversallthevertices–contains|V|-1thetotalcostassociatedwithtreeedgesisminimumamongallpossiblespanningnotnecessarily圖論MinimumSpanningTreesProblem: ephoneCentral NaveCentralCentralWiring:BetterCentralMinimizethetotallengthofwireconnectingtheMinimumSpanningThequestioncanbesolvedbymanyalgorithms,hereisthreeclassicalminimum-spanningtreealgorithms:Prim's圖論圖論Kruskal'sAlgorithm(JosephBernardKruskal,Kruskal–SelecttheminimumweightedgethatdoesnotformacycleKruskal算法(避圈法) 設(shè)G是n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖設(shè)已選取的邊為e1e2，…，ei，在G中選取不同于e1e2…，ei的邊ei+1，使ei+1與{e1e2，…，ei中的邊不構(gòu)成圈，并且（4）ii+1，轉(zhuǎn) Kruskal'sAlgorithm- Kruskal'sAlgorithm- Prim’sAlgorithm(RobertClayPrim,Input:Anon-emptyconnectedweightedgraphwithverticesVedgesEInitialize:Vnew={x},wherexisanarbitrarynode(root)fromV,Enew=RepeatuntilVnew=Chooseanedge(u,v)withminimalweightsuchthatuisinVnewandvis(iftherearemultipleedgeswiththesameweight,anyofthemmaybeAddvtoVnew,and(u,v)toOutput:VnewandEnewdescribeaminimalspanningPrim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-966 Prim'sAlgorithm-966 Prim'sAlgorithm-99136圖論圖論Boruvka'sOtakarInventorofCzechIntroducedtheTheoriginalpaperwaswritteninCzechThepurposewastoefficientlyprovidecoverageofPrim“in圖論圖論設(shè)TG的生成樹(shù)T的邊為枝G的不屬于T的邊稱為弦與給定的TeG的任何生成樹(shù)，枝的數(shù)目弦的數(shù)目圖論定設(shè)G是有m條邊的n階連通無(wú)向圖，則對(duì)于G的任何生成樹(shù)T，都有n–1個(gè)枝和m–n+1個(gè)弦。 圖論圖論基本回路（圈由定理7.6.1知，如果在生成樹(shù)中增加一條弦，則恰產(chǎn)生一個(gè)G的只包含一條弦的回路稱為基本回路 所有基本圈構(gòu)成的集合，稱為關(guān)于生成樹(shù)TG的基本圈組e e5 e e3C1=(e1,e2,e6,eC2=(e5,e6,C3=(e4,e3,e6,eG234基本圈C4=(e7,e3,G234基本圈11

,C,

C} 問(wèn)(n,m圖的生成樹(shù)

有多圖論圖論課后實(shí)驗(yàn)?zāi)俊?2.4定義12.2（根樹(shù)）若一個(gè)有向樹(shù)有一個(gè)引入次數(shù)為0的頂點(diǎn)，根樹(shù)是一種特殊的有樹(shù)葉：在根樹(shù)中，稱引出次數(shù)為0的頂點(diǎn)為頂點(diǎn)的級(jí)是從樹(shù)根出發(fā)到該頂點(diǎn)的通路的長(zhǎng)度。所有結(jié)點(diǎn)的級(jí)的最大值稱為有向樹(shù)的高 圖論圖論有向每個(gè)弱分支都是有向樹(shù)的有向圖稱為有向森林 圖論常用譜系中的一些術(shù)語(yǔ)來(lái)描述根樹(shù)中的頂點(diǎn)：稱從頂點(diǎn)u出發(fā)可以到達(dá)的每一個(gè)頂點(diǎn)為u的后裔，稱u為其后裔的祖先;稱u親;稱同一個(gè)父親的頂點(diǎn)互為兄弟。 Tree: internalinternalancestorancestorofdescendantsofparentparentofchildofsiblingsiblingof有序樹(shù):給根樹(shù)的頂點(diǎn)或弧都指定了次序的根有序林:每個(gè)連通分支都是有序樹(shù)的的有序樹(shù)。例如，圖12.2的b和c表示的是同一根樹(shù)，但是不Definition2Arootedtreeiscalledanm-arytree(m元樹(shù)）ifeveryinternalvertexhasnomorethanmchildrenThetreeiscalledafullm-arytreeifeveryinternalvertexhasexactlymchildren（完全n元樹(shù)）Anm-arytreewithm2iscalledabinarytree.Arethesefullm-aryTheoremTheorem.Afullm-arytreewithiinternalverticesn=mi+1Everyvertex(exceptroot)isthechildofaninternalEachoftheiinternalverticeshasmTherearemivertices(otherthantheThereforen=mi+ii=4internalm=n=3×4+1=最優(yōu)二元(叉）樹(shù)及其t為帶權(quán)二元樹(shù)T的權(quán)

樹(shù)中，稱權(quán)最小的帶權(quán)二元樹(shù)為最優(yōu)二元樹(shù)。3

2圖論圖論7A57A5B2C4D2C4D7A5B7A5B2C (a)帶權(quán)路徑長(zhǎng)度為 (b)帶權(quán)路徑長(zhǎng)度為 最優(yōu)二叉樹(shù)的Huffman輸入：正實(shí)數(shù)序列w1,w2,…,wtT棵根樹(shù)（森林），其根的權(quán)分別是w1,w2,…,wt ）2重復(fù)第2步，直至形成一注意結(jié)果可能不唯一(如果“當(dāng)前”權(quán)最小頂點(diǎn)對(duì)不唯一)位置m元樹(shù)：每一個(gè)頂點(diǎn)的兒子都分別有確定的位置的m元

圖12.3a是二元樹(shù)，b是完當(dāng)m2時(shí)，分別稱為二元樹(shù)，二元樹(shù)，c是位置二元樹(shù)完全二元樹(shù)和位置二元樹(shù)

雖然d與a是同構(gòu)根位置二元樹(shù)的前綴編碼表示樹(shù)根的左兒子的字符串為a0，u的位置二元樹(shù)的前綴編碼｜a是樹(shù)葉對(duì)應(yīng)的字符串}給定一個(gè)位置二元樹(shù),可以得到一個(gè)前綴編碼。反之,給出一個(gè)前綴編碼,也能夠畫出對(duì)應(yīng)的位置二元樹(shù)。最優(yōu)二元樹(shù)的例：設(shè)在通訊中7個(gè)字母出現(xiàn)的頻率如 0 55數(shù)位為：（（5＋5）×4＋（10＋10＋15）

0

1

5

5

思考 證明：假設(shè)P是T中最長(zhǎng)的基本鏈，P的起點(diǎn)或終點(diǎn)的次數(shù)不為，即它的次數(shù)至少是2，則至少有一個(gè)頂點(diǎn)與P的起點(diǎn)或終點(diǎn)鄰接，因存更長(zhǎng)與是中的本鏈 因樹(shù)T中最長(zhǎng)基本鏈的起點(diǎn)和終點(diǎn)次數(shù)必為1?；A(chǔ)圖是完全無(wú)向圖的有向圖有 路徑，試證明假設(shè)n個(gè)頂點(diǎn)時(shí)成立，設(shè)G是n+1個(gè)頂點(diǎn)，且滿足上述條件從G中刪去頂點(diǎn)v及其關(guān)聯(lián)邊，得到G’，由歸納假設(shè)， （v1,v2,…,vn),G在G中有一條弧(v,v1)，則 有向路(v,v1,v2,…,在G中沒(méi)有弧(v,v1)，則必有弧(v1,v)。若存在vi，vi是v1之后第一個(gè)到并且有弧 vi)的頂點(diǎn)，則顯然得到一 有向路 …,vi-1,v,vi,在G中沒(méi)有弧(vvi)，而對(duì)所有vi，均有弧(viv)，i=12n，則若G是簡(jiǎn)單連通圖，邊數(shù)為e，結(jié)點(diǎn)數(shù)為n。若e>=n，G至少有3棵生成樹(shù)/*只需證明e=n時(shí)，命題成立證明：若e=n-1，因?yàn)镚是連通的，所以為一棵樹(shù)(樹(shù)的定一個(gè)長(zhǎng)度大于等于3的回路，則在這個(gè)回任意證明：證明恰好有兩個(gè)頂點(diǎn)的次數(shù)為1的樹(shù)必為一基本證明：假設(shè)T是任意一個(gè)恰好有兩個(gè)頂點(diǎn)的次數(shù)為1的樹(shù)，如果T不是一基本鏈則至少有一個(gè)分支頂點(diǎn)的次數(shù)大于2。設(shè)T有n個(gè)頂點(diǎn)，則T有n-2個(gè)分頂點(diǎn)(去除兩片葉子），n-1條邊。根據(jù)握手定理，T的頂點(diǎn)的度數(shù)之等于T的邊數(shù)的2倍，可>2+2（n-2）（兩片葉子次數(shù)+所有次數(shù)為2的分支結(jié)點(diǎn)的次數(shù)因此得到2n-2>2n-2， nt），它等于邊的總數(shù)m。又因?yàn)閙=n-1，故有2（n-nt）=n-1，解得n2nt-1。因此mn-12(nt-1)證明：設(shè)完全二元樹(shù)T有n個(gè)頂點(diǎn)，條邊，它有n片樹(shù)葉，由上題知：m=1=2nt（）m=。另：有（的路C’為G中的最長(zhǎng)路，則C是圖G 回路/*反證法證明令C的長(zhǎng)度為m。若C不 回路，則圈外必存在一圈上與v關(guān)聯(lián)的一邊為e，則C-e的長(zhǎng)度為m-而C-e+uv的長(zhǎng)度為m；得C-e不是最長(zhǎng)路 Foralln≥3,thenumberofdistinctHamiltoncyclesinthecompletegraphKnis(n?1)!/2.Proof：Inacompletegraph,everyvertexisadjacenttoeveryothervertex.Therefore,ifweweretotakealltheverticesinacompletegraphinanyorder,therewillbeapaththroughthoseverticesinthatorder.JoiningeitherendofthatpathgivesusaHamiltoncy