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

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

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

3、兩個(gè)頂點(diǎn)中，至少?gòu)囊粋€(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)是可達(dá)的，稱有向圖G是弱連通的。,一 、圖的基本概念,鄰接和關(guān)聯(lián) 無(wú)向圖和有向圖 零圖和平凡圖 簡(jiǎn)單圖 完全圖（無(wú)向完全圖和有向完全圖） 有環(huán)圖,一 、圖的基本概念,有限圖和無(wú)限圖 設(shè)圖G為 （l）當(dāng)V和E為有限集時(shí)，稱G為有限圖，否則稱G為無(wú)限圖。 （2）當(dāng)G為單射時(shí)，稱G為單圖；當(dāng)G為非單射時(shí)，稱G為重圖，又稱滿足(e1) = (e2)的不同邊e1，e2，為重邊,或平行邊。 正則圖 各頂點(diǎn)的度均相同的圖稱為正則圖（regular graph）。 各頂點(diǎn)度均為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。,握手定理的證明,每個(gè)圖中，節(jié)點(diǎn)度數(shù)的總和等于邊的2倍。 證明： 因?yàn)槊織l邊必關(guān)聯(lián)兩個(gè)節(jié)點(diǎn)，而一 條邊給予關(guān)聯(lián)的每個(gè)節(jié)點(diǎn)的度數(shù)為1，因此在一個(gè)圖中，節(jié)點(diǎn)度數(shù)的總和等于邊數(shù)的2倍。,握手定理的運(yùn)用,定理1：在任何圖中，度數(shù)為奇數(shù)的節(jié)點(diǎn)個(gè)數(shù)必定是偶數(shù)個(gè)。 證明： （自己思考?。?定理2：在任何有向圖中，所有節(jié)點(diǎn)入度之和等于所有節(jié)點(diǎn)的出度之和。 證明： 因?yàn)槊恳粭l

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

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

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

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

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

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

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

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

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

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

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

16、片樹(shù)葉。,二、生成樹(shù) 1、生成樹(shù)定義： 若無(wú)向圖的一個(gè)生成子圖T是樹(shù)，則稱T 為G的生成樹(shù)，T中的邊稱為樹(shù)枝，E（G）-E（T）稱為樹(shù)T的補(bǔ)，其中的每一邊稱為樹(shù)T 的弦。 注：(1)由定義知，只有連通圖才有生成樹(shù)。,(2)連通圖的生成樹(shù)不唯一，至少有一棵，因通過(guò)不斷地刪去圖G中的回路中的邊，總能得到一棵生成樹(shù)。,基本回路： 生成樹(shù) 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個(gè)頂點(diǎn)，m條邊，則G的任一生成樹(shù)有n-1條邊，m-(n-1)條弦，m-n+1

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

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

19、Tei+1中有一回路r,而T是樹(shù)，因任一回路與生成樹(shù)的補(bǔ)必有一公共邊，所以在r中必存在一條邊f(xié)T 對(duì)于樹(shù)T(邊集至少為e1.ei,f)，若用ei+1代換f，得一棵新樹(shù)T1(邊集至少為e1.eiei+1) 則T1的權(quán)W(T1)=W(T1)+W(ei+1)-W(f),因?yàn)門為最小生成樹(shù) 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的最小生成樹(shù)。而T1與T的公共邊比T與T的公共邊多1，用T1置換T，重復(fù)上面論證直至T與T有n-1條公共邊，從而證得T也是G的最小生成樹(shù)。

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

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

22、稱G為(有向)森林，在森林中，若所有樹(shù)是有序樹(shù)，且給每棵樹(shù)指定次序，稱此森林為有序森林 .,b,c,b,c,a,b,c,完全3元樹(shù),完全2元樹(shù),正則2元樹(shù),6、有序樹(shù)，有序森林與二元樹(shù)相互轉(zhuǎn)換 有序樹(shù)轉(zhuǎn)換為二元樹(shù)，轉(zhuǎn)換過(guò)程為： a)在各兄弟結(jié)點(diǎn)之間加一連線。 b)對(duì)任何結(jié)點(diǎn)，除最左的兒子之外，擦掉該結(jié)點(diǎn)與其余兒子的聯(lián)線。 c)對(duì)新圖向下旋轉(zhuǎn)45度。,b,c,b,c,-,2. 有序森林轉(zhuǎn)換為二元樹(shù)轉(zhuǎn)換過(guò)程 a)設(shè)置一個(gè)總根，聯(lián)結(jié)各樹(shù)的根，得T b)把T轉(zhuǎn)換為二元樹(shù) c)刪除總根,二.完全m元樹(shù)性質(zhì) 1.設(shè)完全m元樹(shù)，葉數(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計(jì)算機(jī)有一計(jì)算三數(shù)之和的加法器,現(xiàn)求十個(gè)數(shù)之和,問(wèn)至少執(zhí)行多少次加法指令?,證明:若把完全m元樹(shù)視為m個(gè)選手參加淘汰賽, 則t表示選手總數(shù), i表示比賽場(chǎng)數(shù),每場(chǎng)比賽淘汰 m-1人,共淘汰 i (m-1)人,剩下一個(gè)冠軍,所以 t=(m-1)i+1,2 、內(nèi)部通數(shù)長(zhǎng)度I定義：各分枝點(diǎn)路徑長(zhǎng)度之和。 內(nèi)部通數(shù)長(zhǎng)度E定義：各 葉子路徑長(zhǎng)度之和. 性質(zhì)：完全二叉樹(shù)T有E=I+2n 其中: n為分枝點(diǎn)數(shù),證：對(duì)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時(shí)，結(jié)論成立; 則n=k時(shí)，若刪去長(zhǎng)度為e+