大一各科課件-離散圖論

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

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

添加e1，…，ei，在添加的每一步均保證：ei+1不與{e１，…，ei}的任何子集構成回路。2、破圈法：在G0(即G)，G1，G2，…中去掉e1，e2，e3，…eiGi-1即把G中的所有回路均挑若Gi無圈，則TG←Gi并終止；否則轉+1←Gi- 圖論 圖，G′G 長度之和稱為G′ 長度設G是連通無向圖，〈G，W〉 圖G的所有生成樹 長度最小者稱為〈G，W〉的最小生成樹 MinimumSpanningTreeAminimumspanningtreeisasubgraphofanundirectedweightedgraphG,suchthatitisatree(i.e.,itisitcoversallthevertices–contains|V|-1thetotalcostassociatedwithtreeedgesisminimumamongallpossiblespanningnotnecessarily圖論MinimumSpanningTreesProblem: ephoneCentral NaveCentralCentralWiring:BetterCentralMinimizethetotallengthofwireconnectingtheMinimumSpanningThequestioncanbesolvedbymanyalgorithms,hereisthreeclassicalminimum-spanningtreealgorithms:Prim's圖論圖論Kruskal'sAlgorithm(JosephBernardKruskal,Kruskal–SelecttheminimumweightedgethatdoesnotformacycleKruskal算法(避圈法) 設G是n個頂點的帶權連通無向圖設已選取的邊為e1e2，…，ei，在G中選取不同于e1e2…，ei的邊ei+1，使ei+1與{e1e2，…，ei中的邊不構成圈，并且（4）ii+1，轉 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圖論圖論設TG的生成樹T的邊為枝G的不屬于T的邊稱為弦與給定的TeG的任何生成樹，枝的數(shù)目弦的數(shù)目圖論定設G是有m條邊的n階連通無向圖，則對于G的任何生成樹T，都有n–1個枝和m–n+1個弦。 圖論圖論基本回路（圈由定理7.6.1知，如果在生成樹中增加一條弦，則恰產生一個G的只包含一條弦的回路稱為基本回路 所有基本圈構成的集合，稱為關于生成樹TG的基本圈組e e5 e e3C1=(e1,e2,e6,eC2=(e5,e6,C3=(e4,e3,e6,eG234基本圈C4=(e7,e3,G234基本圈11

,C,

C} 問(n,m圖的生成樹

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

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

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

圖12.3a是二元樹，b是完當m2時，分別稱為二元樹，二元樹，c是位置二元樹完全二元樹和位置二元樹

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

0

1

5

5

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