離散數(shù)學(xué)PPT教學(xué)圖論.ppt

1、歡 迎 進 入 第 11 章 圖 論,本章重難點:,重點了解圖的各種概念，理解并掌握握手定理的應(yīng)用以及各種矩陣的表示。 難點是圖的最短路徑和關(guān)鍵路徑的求法。,第11章 圖 論,第一節(jié) 圖的基本概念 第二節(jié) 圖的矩陣表示 第三節(jié) 生成樹、最短路徑和關(guān)鍵路徑 第四節(jié) 特殊圖（歐拉圖和哈密頓圖等） 第五節(jié) 樹、二叉樹和哈夫曼樹,一 、圖的基本概念,圖的定義： 圖（graph）G由三個部分所組成： （1）非空集合V(G)稱為圖G的結(jié)點集，其成員稱為節(jié)點或頂點（nodes or vertices） （2）集合 E(G)，稱為圖G的邊集，其成員稱為邊(edges)。 （3）函數(shù)G：E(G)(V(G)，V(

2、G)，稱為邊與頂點的關(guān)聯(lián)映射。 度的相關(guān)定義： 在任何圖中，結(jié)點v的度（degree）d(v)是v所關(guān)聯(lián)邊的數(shù)目。 而在有向圖中，結(jié)點v的出度（out-degree）d+(v)是v作為有向邊起點的數(shù)目，v的入度（in-degree）d-(v)是v作為有向邊終點的數(shù)目，這時結(jié)點v的度是它的出度與入度的和；結(jié)點v的環(huán)使其度增加2。,一 、圖的基本概念,連通圖、強連通圖、弱連通圖 若無向圖中的任意兩個頂點都相互可達，則稱無向圖G是連通的（connected）； 若有向圖G的任何兩個頂點都是相互可達的，則稱有向圖G是強連通的； 如果G的任何兩個頂點都是相互可達的，稱有向圖G是單向連通的； 如果G的任何

3、兩個頂點中，至少從一個頂點到另一個頂點是可達的，稱有向圖G是弱連通的。,一 、圖的基本概念,鄰接和關(guān)聯(lián) 無向圖和有向圖 零圖和平凡圖 簡單圖 完全圖（無向完全圖和有向完全圖） 有環(huán)圖,一 、圖的基本概念,有限圖和無限圖 設(shè)圖G為 （l）當(dāng)V和E為有限集時，稱G為有限圖，否則稱G為無限圖。 （2）當(dāng)G為單射時，稱G為單圖；當(dāng)G為非單射時，稱G為重圖，又稱滿足(e1) = (e2)的不同邊e1，e2，為重邊,或平行邊。 正則圖 各頂點的度均相同的圖稱為正則圖（regular graph）。 各頂點度均為k的正則圖稱為k-正則圖。 同構(gòu)圖,一 、圖的基本概念,子圖、真子圖、生成子圖,設(shè)圖G1，G2，

4、 稱G1為G2的子圖（subgraph）； 如果V1V2，E1E2，1 2，稱G1為G2的真子圖； 如果G1是G2的子圖，且G1 G2，稱G1為G2的生成子圖 （spanning subgraph）；如果G1是G2的子圖，且V1 = V2。,握手定理的證明,每個圖中，節(jié)點度數(shù)的總和等于邊的2倍。 證明： 因為每條邊必關(guān)聯(lián)兩個節(jié)點，而一 條邊給予關(guān)聯(lián)的每個節(jié)點的度數(shù)為1，因此在一個圖中，節(jié)點度數(shù)的總和等于邊數(shù)的2倍。,握手定理的運用,定理1：在任何圖中，度數(shù)為奇數(shù)的節(jié)點個數(shù)必定是偶數(shù)個。 證明： （自己思考?。?定理2：在任何有向圖中，所有節(jié)點入度之和等于所有節(jié)點的出度之和。 證明： 因為每一條

5、有向邊必對應(yīng)一個入度及一個出度，所以有向圖中各節(jié)點入度之和等于邊數(shù)，各節(jié)點的出度之和也等于邊數(shù)。,例：設(shè)圖G為下列情況： (1) 16條邊，每個頂點都是2度； (2) 21條邊，3個4度頂點，其余均為度頂點； (3) 24條邊，各節(jié)點的度數(shù)均相同； 試求每個圖有幾個節(jié)點？,握手定理的應(yīng)用,解答：利用握手定理，設(shè)圖有x個節(jié)點，則 x=16*2 x=16 21*2=12+3*x x=10 故圖中有個節(jié)點 (3)x*m=24*2,二、圖的矩陣表示,關(guān)聯(lián)矩陣 2. 鄰接矩陣 3. 可達矩陣 4. 布爾矩陣 5. 代價矩陣,二、圖的矩陣表示,關(guān)聯(lián)矩陣 無向圖的關(guān)聯(lián)矩陣 - 以節(jié)點數(shù)為行,邊數(shù)為列.若有環(huán)

6、,則關(guān)聯(lián)數(shù)為2,無關(guān)聯(lián)則為0.每行之和為該頂點的度,列之和一定為2. 有向圖的關(guān)聯(lián)矩陣 - 以節(jié)點數(shù)為行,邊數(shù)為列.節(jié)點與邊無關(guān)系,為0,有關(guān)系,則起點為1,終點為-1;列之和一定為0,每行絕對值之和等于該節(jié)點的度數(shù);其中1的個數(shù)為該節(jié)點的出度,-1的個數(shù)為對應(yīng)節(jié)點的入度;所有元素的和為0,1的個數(shù)等于-1的個數(shù),都等于邊數(shù)m.,二、圖的矩陣表示,2. 鄰接矩陣 無向圖的鄰接矩陣 - 行和列均為節(jié)點的數(shù)目;是個對稱距陣,行之和等于列之和,均等于該頂點的度;主對角線都為0,除非有環(huán)才為1;邊的數(shù)目m為1的數(shù)目總和的一半. 有向圖的鄰接矩陣 - 行和列均為節(jié)點的數(shù)目;不是對稱距陣,行之和等于該頂點

7、的出度,列之和等于該頂點的入度;主對角線都為0,除非有環(huán)才為1;邊的數(shù)目m為非0的數(shù)目的總和.,二、圖的矩陣表示,可達矩陣 - 行和列均為節(jié)點的數(shù)目;節(jié)點和節(jié)點之間若至少存在一條路則為1,不存在路則為0. 4.布爾矩陣 - 由可達距陣轉(zhuǎn)變,把非0的數(shù)值均改為1即可. 代價矩陣 - 若鄰接距陣元素為1的以權(quán)值表示,距陣元素為0的則以表示.,三、生成樹、最短路徑和關(guān)鍵路徑,生成樹定義 1、深度優(yōu)先遍歷 2、廣度優(yōu)先遍歷 最小生成樹 構(gòu)造最小生成樹的三種方法： 1、Kruskal算法 2、管梅谷算法 3、Prim算法,第四節(jié) 歐拉圖和哈密頓圖,歐拉圖的由來： 哥尼斯堡七橋問題哥尼斯堡城市有一條橫貫全

8、城的普雷格爾河，河中有兩個小島，城的各部分用七座橋連接，每逢假日，城中居民進行環(huán)城逛游，這樣就產(chǎn)生了一個問題，能不能設(shè)計一次遍游，使得從某地出發(fā)對每座跨河橋只走一次，而在遍歷了七橋之后卻又能回到原地。,第四節(jié) 歐拉圖和哈密頓圖,通過圖中所有邊一次且僅一次行遍所有頂點的通路稱為歐拉通路（歐拉路）。通過圖中所有邊一次且僅一次行遍所有頂點的回路稱為歐拉回路。 只有具有歐拉回路的圖才能稱為歐拉圖。 具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。,第四節(jié) 歐拉圖和哈密頓圖,歐拉在1736年的論文中提出了一條簡單準則，確定了哥尼斯堡七橋問題是不能解的。 定理1：無向圖是歐拉圖當(dāng)且僅當(dāng)G是連通圖且沒有奇度頂點。

9、 定理2：無向圖是半歐拉圖當(dāng)且僅當(dāng)G是連通的且恰有兩個奇度頂點。,第四節(jié) 歐拉圖和哈密頓圖,定理3：有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強連通的且每個頂點的 入度等于出度。 定理4：有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的且恰有兩個奇度頂點，其中一個頂點的入度比出度大1，另一個頂點出度比入度大1，而其余頂點的 入度等于出度。,第四節(jié) 歐拉圖和哈密頓圖,歐拉圖的應(yīng)用： 一筆畫問題： 一個圖能一筆畫出是指從圖某一點出發(fā)，不間斷地畫完整個圖，最后回到起點。,第四節(jié) 歐拉圖和哈密頓圖,哈密頓圖的由來周游世界問題： 一個數(shù)學(xué)游戲，能不能在一個十二面體中找到一條回路，使它含有這個圖的所有結(jié)點？把每個結(jié)點看成一個城

10、市，連接兩個結(jié)點的邊看成是交通線，也即能否找到旅游線路，沿著交通線經(jīng)過每個城市恰好一次再回到原來的出發(fā)地？,第四節(jié) 歐拉圖和哈密頓圖,經(jīng)過圖中所有頂點一次且僅一次的通路稱為哈密頓通路（哈密頓路）。通過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。 只有具有哈密頓回路的圖才能稱為哈密頓圖。 具有哈密頓通路而無哈密頓回路的圖稱為半哈密頓圖。,第四節(jié) 歐拉圖和哈密頓圖,定理1（必要條件）：設(shè)無向圖G=是哈密頓圖，則對于任意V1 V且V1 空集 ，均有 P（G-V1）V1 定理2（充分條件）：設(shè)G是n階無向簡單圖，若對于G中任意不相鄰的頂點u，v，均有 d（u）+d（v）n-1，則G中存在哈密頓通路。

11、 推論：設(shè)G為n（n3）階無向簡單圖，若對于G中任意兩個不相鄰的頂點u，v均有 d（u）+d（v）n，則G中存在哈密頓回路。,第四節(jié) 歐拉圖和哈密頓圖,哈密頓圖的應(yīng)用 在某次國際會議的預(yù)備會中，共有8人參加，他們來自不同的國家，已知他們中任何兩個無共同語言的人，與其余有共同語言的人數(shù)之和大于或等于8，試證明能將這8個人排在圓桌旁，使其任何人都能與兩邊的人交談。,一、無向樹 1. 定義： 無回路的連通無向圖稱為無向樹，簡稱樹。 樹中度數(shù)為1 的頂點稱為樹葉，度數(shù)大于1 的頂點稱為內(nèi)部結(jié)點或分枝點。 若圖G的每個連通分圖都是樹,G稱為森林 。,第五節(jié) 樹、二叉樹和哈夫曼樹,2、樹的五個等價定義 T

12、h1.無向圖T是樹，當(dāng)且僅當(dāng)下列條件之一成立： 1.無回路且m=n-1的圖 2.連通且m=n-1 的圖 3.無回路，但增加任一新邊，得到且僅得到 一個基本回路 4.連通但刪去任一邊，圖便不連通。(n=2) 5.每一對頂點間有唯一的一條通路。(n=2),證明：證明思路 (1)樹=1 (2)1=2 (3)2=3 (4)3=4 (5)4=5 (6)5=6,(1)樹=1 即無回路的連通無向圖=無回路且m=n-1 證明：對頂點數(shù)作歸納證明。 n=1時，m=0， m=n-1成立 設(shè)n=k命題成立，當(dāng)n=k+1時，因樹連通而無回路，所以至少有一個度數(shù)為1的頂點v，在T中刪去v，及其關(guān)聯(lián)邊，得k個頂點的樹T由

13、歸納假設(shè)，它有k-1條邊。 原圖T邊數(shù)為k-1+1,頂點數(shù)為k+1 m=n-1成立。 樹是無回路且m=n-1的圖。,(2)無回路且m=n-1的圖=連通且m=n-1 的圖 反證法. 證明：設(shè)T不連通，有k個連通分圖 T1.Tk(k2)，頂點數(shù)及邊數(shù)分別為 n1.nk,m1.mk,因每個連通分圖是無回路連通圖，故符合樹的定義，所以ni=mi-1成立 n=m-k k1,這與m=n-1前提矛盾 T連通且具有m=n-1的圖,(3)2=3 即連通且m=n-1 的圖=無回路，但增加任一新邊，得到且僅得到一個基本回路。 證明：(a)T無回路，因T是連通,并且m=n-1的圖， 故當(dāng)n=1時，m=n-1=0,無回

14、路 設(shè)頂點數(shù)為n-1時無回路。 當(dāng)頂點數(shù)為n時，m=n-1，故至少有一個頂點v， 使d(v)=1，刪去v及其關(guān)連邊得圖T 則由歸納假設(shè)T無回路，再加回v及關(guān)聯(lián)邊得 圖T，則T也無回路。,(b)在連通圖T中,任意取兩點vi，v j, 因為T連通所以vi，v j存在一路經(jīng)， 若增加新邊 (vi,vj)，則得一回路， 且該回路是唯一的。 ( 否則，刪去新邊，路經(jīng)中必有回路。),(4) 3=4. 即無回路，但增加任一新邊，得到且僅得到一個基本回路=連通，但刪去任一邊，圖便不連通。(n=2) 證明：若圖不連通，則存在vi,vj,，使vi,vj之間沒有路，增加邊不產(chǎn)生回路，與前提矛盾。 因T無回路，故刪去

15、任一邊，圖便不連通。,(5)4=5.即連通，但刪去任一邊，圖便不連通。(n=2) =每一對頂點間有唯一的一條通路。 證明：因圖連通，故任二頂點間有一條通路，若二頂點間路徑不唯一，則T中有回路，刪去回路上任一條邊，圖仍連通，與假設(shè)矛盾，所以，每一對頂點間必有唯一的一條通路 (6) 5=樹定義 （無回路的連通無向圖） 因每一對頂點有唯一的一條通路，故圖連通，若圖有回路，則任二頂點有兩條不同通路，與題設(shè)矛盾。,證：若T中只有一片樹葉， 則 d（vi）2（n-1）+1=2n-1 若T中沒有樹葉，則d（vi）2n 均與d（vi）=2m=2（n-1）矛盾。,3、Th2：結(jié)點數(shù)大于等于2 的任意樹，至少有兩

16、片樹葉。,二、生成樹 1、生成樹定義： 若無向圖的一個生成子圖T是樹，則稱T 為G的生成樹，T中的邊稱為樹枝，E（G）-E（T）稱為樹T的補，其中的每一邊稱為樹T 的弦。 注：(1)由定義知，只有連通圖才有生成樹。,(2)連通圖的生成樹不唯一，至少有一棵，因通過不斷地刪去圖G中的回路中的邊，總能得到一棵生成樹。,基本回路： 生成樹 e1,e7,e5,e6 ， e1，e7，e5，e2，e4 e7,e2,e3,e4 ， e1，e6，e5，e2，e4 e5,e4,e8 ， e7，e6，e5，e2，e4,(3)設(shè)連通圖G 有n個頂點，m條邊，則G的任一生成樹有n-1條邊，m-(n-1)條弦，m-n+1

17、稱為連通圖的秩。 2.圖G中任一條回路和任何一棵生成 樹的補至少有一條公共邊。 證明：若G中一條回路和一生成 樹的補無公共邊，則表示該回路在該生成樹中。這與生成樹定義矛盾。 3.圖G中任何一個邊割集和任何一棵生成樹至少有一條公共邊。 證明：若G中一個邊割集和一生成 樹無公共邊，則表示該邊割集所分離的結(jié)點不在生成樹中，這導(dǎo)致與生成樹的定義矛盾。,三、最小生成樹 1、最小生成樹定義： 設(shè)圖G=是賦權(quán)連通簡單圖，其中每一邊的權(quán)W(i，j)是非負實數(shù)。生成樹T的權(quán)定義為W(T)= W（i，j），（i，j）T，使W(T）具有最小值的生成樹稱為G的最小生成樹。 2、最小生成樹求法-kruskal算法。,設(shè)

18、圖G有n 個頂點，m條邊，w(e1)w(em) k1，A 若Aek導(dǎo)出子圖不包 含回路，則AA ek kk+1 N0 A=n-1 Yes 結(jié)束,證明：因T 是有n-1條邊，且無回路的圖。 由樹的等價定義可知，它是樹。 又T包含了n個頂點， 故包含了G的全部頂點。 T是G的生成樹。,算法的正確性證明 證明邊集A最后所得子圖T是G的生成樹。,、T是最小生成樹,注：當(dāng)G中的權(quán)相等時，仍可用本算法，只是所得之最小生成樹不唯一。,證明T是最小生成樹 （證明方法：T逐步轉(zhuǎn)化T,證明：設(shè)T是最小生成樹，T是由krusal算法生成的樹，若T與T不同，但有公共邊e1.ei(i=0),則ei+1Tei+1T,則在

19、Tei+1中有一回路r,而T是樹，因任一回路與生成樹的補必有一公共邊，所以在r中必存在一條邊f(xié)T 對于樹T(邊集至少為e1.ei,f)，若用ei+1代換f，得一棵新樹T1(邊集至少為e1.eiei+1) 則T1的權(quán)W(T1)=W(T1)+W(ei+1)-W(f),因為T為最小生成樹 W(T)W(T1) W(ei+1)W(f) 又根據(jù)T生成法 自e1.ei之后將取f而不是ei+1 而現(xiàn)在T取ei+1 W(ei+1)W(f) W(ei+1)=W(f) T1也是G的最小生成樹。而T1與T的公共邊比T與T的公共邊多1，用T1置換T，重復(fù)上面論證直至T與T有n-1條公共邊，從而證得T也是G的最小生成樹。

20、,一、有向樹 定義: 1.若一個有向圖T的底圖是無向樹，且恰有一個結(jié)點的入度為0，其余所有結(jié)點入度為1，稱T為有向樹。入度為0的結(jié)點稱為根，出度不為0的結(jié)點稱為分枝點或內(nèi)部結(jié)點，出度為0的結(jié)點稱為數(shù)葉或外部結(jié)點。 注意：有向樹通常采用根在頂點上，所有邊方向向下的圖表示.(箭頭也可省略),有 向 樹 及 應(yīng) 用,2.基本概念: 設(shè)a和b是樹T的結(jié)點，若從a到b有一條邊稱a是b的父親， b是a的兒子，同一個分枝點的兒子，稱為“兄弟”。 若從a到c有一有向路徑，稱a是c的祖先，c是a的子孫. 由結(jié)點a和它所有的后代導(dǎo)的子圖，稱為T的子樹. 從樹根r到一結(jié)點a的路徑所含的邊數(shù)稱為a的路徑長度。 樹T中

21、最長的路徑稱為樹T的高度。,例題:,a,b,c,由有向樹的結(jié)構(gòu)可知，它還可以遞歸定義如下: 3.有向樹有一個根，其余的結(jié)點劃分為m0個不相交的集合T1.Tm，且每個集合是子有向樹。,4. 有向樹的括號表示 若T中只有一個結(jié)點，則此結(jié)點就是它的括號表示。 若T由根v和子樹T1T2.Tn組成，則T的括號表示為v(T1T2.Tn）.,5. m元完全樹，正則樹的定義 定義: 在樹T中若每一結(jié)點的兒子個數(shù)小于或等于m ,稱T為m元樹;在樹T中若每一結(jié)點的兒子個數(shù)等于m或者等于0，稱T為完全m元樹。若完全m元樹所有樹葉層次相同，稱為正則m元樹。,5.有向森林定義 一個有向圖G，若它的每個連通分量是有向樹，

22、稱G為(有向)森林，在森林中，若所有樹是有序樹，且給每棵樹指定次序，稱此森林為有序森林 .,b,c,b,c,a,b,c,完全3元樹,完全2元樹,正則2元樹,6、有序樹，有序森林與二元樹相互轉(zhuǎn)換 有序樹轉(zhuǎn)換為二元樹，轉(zhuǎn)換過程為： a)在各兄弟結(jié)點之間加一連線。 b)對任何結(jié)點，除最左的兒子之外，擦掉該結(jié)點與其余兒子的聯(lián)線。 c)對新圖向下旋轉(zhuǎn)45度。,b,c,b,c,-,2. 有序森林轉(zhuǎn)換為二元樹轉(zhuǎn)換過程 a)設(shè)置一個總根，聯(lián)結(jié)各樹的根，得T b)把T轉(zhuǎn)換為二元樹 c)刪除總根,二.完全m元樹性質(zhì) 1.設(shè)完全m元樹，葉數(shù)為t，分枝數(shù)為i，則t=(m-1)i+1,解: i =(t-1)/(m-1)

23、=(10-1)/(3-1)=5 答:至少執(zhí)行5次加法指令.,例：若 t=i(m-1)+1計算機有一計算三數(shù)之和的加法器,現(xiàn)求十個數(shù)之和,問至少執(zhí)行多少次加法指令?,證明:若把完全m元樹視為m個選手參加淘汰賽, 則t表示選手總數(shù), i表示比賽場數(shù),每場比賽淘汰 m-1人,共淘汰 i (m-1)人,剩下一個冠軍,所以 t=(m-1)i+1,2 、內(nèi)部通數(shù)長度I定義：各分枝點路徑長度之和。 內(nèi)部通數(shù)長度E定義：各 葉子路徑長度之和. 性質(zhì)：完全二叉樹T有E=I+2n 其中: n為分枝點數(shù),證：對n用數(shù)學(xué)歸納法: 當(dāng)n=1, 則葉數(shù)為2，I=0，E=2， E=I+2n成立; 當(dāng)n=2, 則葉數(shù)為3，I=1，E=5， E=I+2n成立; 設(shè)n=k-1時，結(jié)論成立; 則n=k時，若刪去長度為e+