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

離散數(shù)學(xué)教學(xué)圖論第一頁(yè)，共六十頁(yè)，編輯于2023年，星期日本章重難點(diǎn):重點(diǎn)了解圖的各種概念，理解并掌握握手定理的應(yīng)用以及各種矩陣的表示。難點(diǎn)是圖的最短路徑和關(guān)鍵路徑的求法。第二頁(yè)，共六十頁(yè)，編輯于2023年，星期日第11章圖論第一節(jié)

圖的基本概念第二節(jié)圖的矩陣表示第三節(jié)生成樹、最短路徑和關(guān)鍵路徑第四節(jié)特殊圖（歐拉圖和哈密頓圖等）第五節(jié)樹、二叉樹和哈夫曼樹第三頁(yè)，共六十頁(yè)，編輯于2023年，星期日一、圖的基本概念圖的定義：圖（graph）G由三個(gè)部分所組成：（1）非空集合V(G)稱為圖G的結(jié)點(diǎn)集，其成員稱為節(jié)點(diǎn)或頂點(diǎn)（nodesorvertices）（2）集合E(G)，稱為圖G的邊集，其成員稱為邊(edges)。（3）函數(shù)ΨG：E(G)→(V(G)，V(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。第四頁(yè)，共六十頁(yè)，編輯于2023年，星期日

一、圖的基本概念連通圖、強(qiáng)連通圖、弱連通圖

若無向圖中的任意兩個(gè)頂點(diǎn)都相互可達(dá)，則稱無向圖G是連通的（connected）；若有向圖G的任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，則稱有向圖G是強(qiáng)連通的；如果G的任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，稱有向圖G是單向連通的；如果G的任何兩個(gè)頂點(diǎn)中，至少?gòu)囊粋€(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)是可達(dá)的，稱有向圖G是弱連通的。第五頁(yè)，共六十頁(yè)，編輯于2023年，星期日

一、圖的基本概念鄰接和關(guān)聯(lián)無向圖和有向圖零圖和平凡圖簡(jiǎn)單圖完全圖（無向完全圖和有向完全圖）有環(huán)圖第六頁(yè)，共六十頁(yè)，編輯于2023年，星期日一、圖的基本概念有限圖和無限圖設(shè)圖G為<V，E，Ψ>（l）當(dāng)V和E為有限集時(shí)，稱G為有限圖，否則稱G為無限圖。（2）當(dāng)ΨG為單射時(shí)，稱G為單圖；當(dāng)ΨG為非單射時(shí)，稱G為重圖，又稱滿足Ψ(e1)=Ψ(e2)的不同邊e1，e2，為重邊,或平行邊。正則圖各頂點(diǎn)的度均相同的圖稱為正則圖（regulargraph）。各頂點(diǎn)度均為k的正則圖稱為k-正則圖。同構(gòu)圖第七頁(yè)，共六十頁(yè)，編輯于2023年，星期日一、圖的基本概念子圖、真子圖、生成子圖設(shè)圖G1＝<V1，E1，Ψ1>，G2＝<V2，E2，Ψ2>，稱G1為G2的子圖（subgraph）；如果V1V2，E1E2，Ψ1Ψ2，稱G1為G2的真子圖；如果G1是G2的子圖，且G1G2，稱G1為G2的生成子圖（spanningsubgraph）；如果G1是G2的子圖，且V1=V2。第八頁(yè)，共六十頁(yè)，編輯于2023年，星期日握手定理的證明每個(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è)，共六十頁(yè)，編輯于2023年，星期日握手定理的運(yùn)用定理1：在任何圖中，度數(shù)為奇數(shù)的節(jié)點(diǎn)個(gè)數(shù)必定是偶數(shù)個(gè)。

證明：

（自己思考?。┒ɡ?：在任何有向圖中，所有節(jié)點(diǎn)入度之和等于所有節(jié)點(diǎn)的出度之和。

證明：因?yàn)槊恳粭l有向邊必對(duì)應(yīng)一個(gè)入度及一個(gè)出度，所以有向圖中各節(jié)點(diǎn)入度之和等于邊數(shù)，各節(jié)點(diǎn)的出度之和也等于邊數(shù)。第十頁(yè)，共六十頁(yè)，編輯于2023年，星期日例：設(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=1621*2=12+3*xx=10故圖中有１３個(gè)節(jié)點(diǎn)．(3)

x*m=24*2第十一頁(yè)，共六十頁(yè)，編輯于2023年，星期日

二、圖的矩陣表示關(guān)聯(lián)矩陣2.鄰接矩陣3.可達(dá)矩陣4.布爾矩陣5.代價(jià)矩陣第十二頁(yè)，共六十頁(yè)，編輯于2023年，星期日

二、圖的矩陣表示關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣-----以節(jié)點(diǎn)數(shù)為行,邊數(shù)為列.若有環(huán),則關(guān)聯(lián)數(shù)為2,無關(guān)聯(lián)則為0.每行之和為該頂點(diǎn)的度,列之和一定為2.有向圖的關(guān)聯(lián)矩陣-----以節(jié)點(diǎn)數(shù)為行,邊數(shù)為列.節(jié)點(diǎn)與邊無關(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.第十三頁(yè)，共六十頁(yè)，編輯于2023年，星期日

二、圖的矩陣表示2.鄰接矩陣無向圖的鄰接矩陣-----行和列均為節(jié)點(diǎn)的數(shù)目;是個(gè)對(duì)稱距陣,行之和等于列之和,均等于該頂點(diǎn)的度;主對(duì)角線都為0,除非有環(huán)才為1;邊的數(shù)目m為1的數(shù)目總和的一半.有向圖的鄰接矩陣-----行和列均為節(jié)點(diǎn)的數(shù)目;不是對(duì)稱距陣,行之和等于該頂點(diǎn)的出度,列之和等于該頂點(diǎn)的入度;主對(duì)角線都為0,除非有環(huán)才為1;邊的數(shù)目m為非0的數(shù)目的總和.第十四頁(yè)，共六十頁(yè)，編輯于2023年，星期日

二、圖的矩陣表示可達(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的則以∞表示.第十五頁(yè)，共六十頁(yè)，編輯于2023年，星期日三、生成樹、最短路徑和關(guān)鍵路徑生成樹定義1、深度優(yōu)先遍歷2、廣度優(yōu)先遍歷最小生成樹構(gòu)造最小生成樹的三種方法：1、Kruskal算法2、管梅谷算法3、Prim算法第十六頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖歐拉圖的由來：哥尼斯堡七橋問題—哥尼斯堡城市有一條橫貫全城的普雷格爾河，河中有兩個(gè)小島，城的各部分用七座橋連接，每逢假日，城中居民進(jìn)行環(huán)城逛游，這樣就產(chǎn)生了一個(gè)問題，能不能設(shè)計(jì)一次遍游，使得從某地出發(fā)對(duì)每座跨河橋只走一次，而在遍歷了七橋之后卻又能回到原地。第十七頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖通過圖中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路（歐拉路）。通過圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。只有具有歐拉回路的圖才能稱為歐拉圖。具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。第十八頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖歐拉在1736年的論文中提出了一條簡(jiǎn)單準(zhǔn)則，確定了哥尼斯堡七橋問題是不能解的。定理1：無向圖是歐拉圖當(dāng)且僅當(dāng)G是連通圖且沒有奇度頂點(diǎn)。定理2：無向圖是半歐拉圖當(dāng)且僅當(dāng)G是連通的且恰有兩個(gè)奇度頂點(diǎn)。第十九頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(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)的入度等于出度。第二十頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖歐拉圖的應(yīng)用：一筆畫問題：一個(gè)圖能一筆畫出是指從圖某一點(diǎn)出發(fā)，不間斷地畫完整個(gè)圖，最后回到起點(diǎn)。第二十一頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖哈密頓圖的由來—周游世界問題：一個(gè)數(shù)學(xué)游戲，能不能在一個(gè)十二面體中找到一條回路，使它含有這個(gè)圖的所有結(jié)點(diǎn)？把每個(gè)結(jié)點(diǎn)看成一個(gè)城市，連接兩個(gè)結(jié)點(diǎn)的邊看成是交通線，也即能否找到旅游線路，沿著交通線經(jīng)過每個(gè)城市恰好一次再回到原來的出發(fā)地？第二十二頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖經(jīng)過圖中所有頂點(diǎn)一次且僅一次的通路稱為哈密頓通路（哈密頓路）。通過圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密頓回路。只有具有哈密頓回路的圖才能稱為哈密頓圖。具有哈密頓通路而無哈密頓回路的圖稱為半哈密頓圖。第二十三頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖定理1（必要條件）：設(shè)無向圖G=<V,E>是哈密頓圖，則對(duì)于任意V1V且V1≠空集，均有P（G-V1）≤∣V1∣定理2（充分條件）：設(shè)G是n階無向簡(jiǎn)單圖，若對(duì)于G中任意不相鄰的頂點(diǎn)u，v，均有d（u）+d（v）≥n-1，則G中存在哈密頓通路。推論：設(shè)G為n（n≥3）階無向簡(jiǎn)單圖，若對(duì)于G中任意兩個(gè)不相鄰的頂點(diǎn)u，v均有d（u）+d（v）≥n，則G中存在哈密頓回路。第二十四頁(yè)，共六十頁(yè)，編輯于2023年，星期日第四節(jié)歐拉圖和哈密頓圖哈密頓圖的應(yīng)用在某次國(guó)際會(huì)議的預(yù)備會(huì)中，共有8人參加，他們來自不同的國(guó)家，已知他們中任何兩個(gè)無共同語言的人，與其余有共同語言的人數(shù)之和大于或等于8，試證明能將這8個(gè)人排在圓桌旁，使其任何人都能與兩邊的人交談。第二十五頁(yè)，共六十頁(yè)，編輯于2023年，星期日一、無向樹1.

定義：①無回路的連通無向圖稱為無向樹，簡(jiǎn)稱樹。②樹中度數(shù)為1的頂點(diǎn)稱為樹葉，度數(shù)大于1

的頂點(diǎn)稱為內(nèi)部結(jié)點(diǎn)或分枝點(diǎn)。③若圖G的每個(gè)連通分圖都是樹,G稱為森林

。第五節(jié)樹、二叉樹和哈夫曼樹

第二十六頁(yè)，共六十頁(yè)，編輯于2023年，星期日

2、樹的五個(gè)等價(jià)定義Th1.無向圖T是樹，當(dāng)且僅當(dāng)下列條件之一成立：

1.無回路且m=n-1的圖

2.連通且m=n-1的圖

3.無回路，但增加任一新邊，得到且僅得到一個(gè)基本回路

4.連通但刪去任一邊，圖便不連通。(n>=2)5.每一對(duì)頂點(diǎn)間有唯一的一條通路。(n>=2)

第二十七頁(yè)，共六十頁(yè)，編輯于2023年，星期日證明：證明思路

(1)樹=>1(2)1=>2(3)2=>3(4)3=>4(5)4=>5(6)5=>6第二十八頁(yè)，共六十頁(yè)，編輯于2023年，星期日

(1)樹=>1

即無回路的連通無向圖=>無回路且m=n-1證明：對(duì)頂點(diǎn)數(shù)作歸納證明。

n=1時(shí)，m=0，∴m=n-1成立設(shè)n=k命題成立，當(dāng)n=k+1時(shí)，因樹連通而無回路，所以至少有一個(gè)度數(shù)為1的頂點(diǎn)v，在T中刪去v，及其關(guān)聯(lián)邊，得k個(gè)頂點(diǎn)的樹T`由歸納假設(shè)，它有k-1條邊?！嘣瓐DT邊數(shù)為k-1+1,頂點(diǎn)數(shù)為k+1∴m=n-1成立?！鄻涫菬o回路且m=n-1的圖。

第二十九頁(yè)，共六十頁(yè)，編輯于2023年，星期日(2)無回路且m=n-1的圖=>連通且m=n-1的圖反證法.證明：設(shè)T不連通，有k個(gè)連通分圖T1...Tk(k≥2)，頂點(diǎn)數(shù)及邊數(shù)分別為n1...nk,m1...mk,因每個(gè)連通分圖是無回路連通圖，故符合樹的定義，所以ni=mi-1成立∴n=m-kk>1,這與m=n-1前提矛盾∴T連通且具有m=n-1的圖

第三十頁(yè)，共六十頁(yè)，編輯于2023年，星期日(3)2=>3即連通且m=n-1的圖=>無回路，但增加任一新邊，得到且僅得到一個(gè)基本回路。證明：(a)T無回路，因T是連通,并且m=n-1的圖，故當(dāng)n=1時(shí)，m=n-1=0,無回路設(shè)頂點(diǎn)數(shù)為n-1時(shí)無回路。當(dāng)頂點(diǎn)數(shù)為n時(shí)，m=n-1，故至少有一個(gè)頂點(diǎn)v，使d(v)=1，刪去v及其關(guān)連邊得圖T’

則由歸納假設(shè)T’無回路，再加回v及關(guān)聯(lián)邊得圖T，則T也無回路。

第三十一頁(yè)，共六十頁(yè)，編輯于2023年，星期日(b)在連通圖T中,任意取兩點(diǎn)vi，vj,因?yàn)門連通所以vi，vj存在一路經(jīng)，若增加新邊(vi,vj)，則得一回路，且該回路是唯一的。(否則，刪去新邊，路經(jīng)中必有回路。)第三十二頁(yè)，共六十頁(yè)，編輯于2023年，星期日(4)3=>4.即無回路，但增加任一新邊，得到且僅得到一個(gè)基本回路=>連通，但刪去任一邊，圖便不連通。(n>=2)

證明：若圖不連通，則存在vi,vj,,，使vi,vj之間沒有路，增加邊<vi,vj>不產(chǎn)生回路，與前提矛盾。因T無回路，故刪去任一邊，圖便不連通。第三十三頁(yè)，共六十頁(yè)，編輯于2023年，星期日(5)4=>5.即連通，但刪去任一邊，圖便不連通。(n>=2)=>每一對(duì)頂點(diǎn)間有唯一的一條通路。證明：因圖連通，故任二頂點(diǎn)間有一條通路，若二頂點(diǎn)間路徑不唯一，則T中有回路，刪去回路上任一條邊，圖仍連通，與假設(shè)矛盾，所以，每一對(duì)頂點(diǎn)間必有唯一的一條通路(6)5=>樹定義（無回路的連通無向圖）因每一對(duì)頂點(diǎn)有唯一的一條通路，故圖連通，若圖有回路，則任二頂點(diǎn)有兩條不同通路，與題設(shè)矛盾。第三十四頁(yè)，共六十頁(yè)，編輯于2023年，星期日證：若T中只有一片樹葉，則d（vi）≥2（n-1）+1=2n-1

若T中沒有樹葉，則d（vi）≥2n

均與d（vi）=2m=2（n-1）矛盾。3、Th2：結(jié)點(diǎn)數(shù)大于等于2的任意樹，至少有兩片樹葉。第三十五頁(yè)，共六十頁(yè)，編輯于2023年，星期日二、生成樹1、生成樹定義：

若無向圖的一個(gè)生成子圖T是樹，則稱T為G的生成樹，T中的邊稱為樹枝，E（G）-E（T）稱為樹T的補(bǔ)，其中的每一邊稱為樹T的弦。注：(1)由定義知，只有連通圖才有生成樹。(2)連通圖的生成樹不唯一，至少有一棵，因通過不斷地刪去圖G中的回路中的邊，總能得到一棵生成樹。第三十六頁(yè)，共六十頁(yè)，編輯于2023年，星期日

?e1?e2?e6e7e3?e5

?e4

?e8基本回路：生成樹{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}第三十七頁(yè)，共六十頁(yè)，編輯于2023年，星期日(3)設(shè)連通圖G有n個(gè)頂點(diǎn)，m條邊，則G的任一生成樹有n-1條邊，m-(n-1)條弦，m-n+1稱為連通圖的秩。2.圖G中任一條回路和任何一棵生成樹的補(bǔ)至少有一條公共邊。證明：若G中一條回路和一生成樹的補(bǔ)無公共邊，則表示該回路在該生成樹中。這與生成樹定義矛盾。3.圖G中任何一個(gè)邊割集和任何一棵生成樹至少有一條公共邊。證明：若G中一個(gè)邊割集和一生成樹無公共邊，則表示該邊割集所分離的結(jié)點(diǎn)不在生成樹中，這導(dǎo)致與生成樹的定義矛盾。第三十八頁(yè)，共六十頁(yè)，編輯于2023年，星期日三、最小生成樹1、最小生成樹定義：設(shè)圖G=<V，E，W>是賦權(quán)連通簡(jiǎn)單圖，其中每一邊的權(quán)W(i，j)是非負(fù)實(shí)數(shù)。生成樹T的權(quán)定義為W(T)=W（i，j），（i，j）T，使W(T）具有最小值的生成樹稱為G的最小生成樹。2、最小生成樹求法----kruskal算法。第三十九頁(yè)，共六十頁(yè)，編輯于2023年，星期日

設(shè)圖G有n個(gè)頂點(diǎn)，m條邊，w(e1)≤…≤w(em)k←1，A←

若A{ek}導(dǎo)出子圖不包含回路，則AA∪{ek}

kk+1N0

A=n-1Yes結(jié)束

第四十頁(yè)，共六十頁(yè)，編輯于2023年，星期日證明：因T是有n-1條邊，且無回路的圖。由樹的等價(jià)定義可知，它是樹。又∵T包含了n個(gè)頂點(diǎn)，故包含了G的全部頂點(diǎn)?！郥是G的生成樹。算法的正確性證明①證明邊集A最后所得子圖T是G的生成樹。第四十一頁(yè)，共六十頁(yè)，編輯于2023年，星期日②、T是最小生成樹注：當(dāng)G中的權(quán)相等時(shí)，仍可用本算法，只是所得之最小生成樹不唯一。第四十二頁(yè)，共六十頁(yè)，編輯于2023年，星期日③證明T是最小生成樹（證明方法：T逐步轉(zhuǎn)化T’

證明：設(shè)T是最小生成樹，T’是由krusal算法生成的樹，若T與T’不同，但有公共邊e1...ei(i>=0),則ei+1T’ei+1T,則在T{ei+1}中有一回路r,而T’是樹，因任一回路與生成樹的補(bǔ)必有一公共邊，所以在r中必存在一條邊f(xié)T’

對(duì)于樹T(邊集至少為e1...ei,f)，若用ei+1代換f，得一棵新樹T1(邊集至少為e1...eiei+1)

則T1的權(quán)W(T1)=W(T1)+W(ei+1)-W(f)第四十三頁(yè)，共六十頁(yè)，編輯于2023年，星期日因?yàn)門為最小生成樹∴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的最小生成樹。

第四十四頁(yè)，共六十頁(yè)，編輯于2023年，星期日一、有向樹定義:1.若一個(gè)有向圖T的底圖是無向樹，且恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)入度為1，稱T為有向樹。入度為0的結(jié)點(diǎn)稱為根，出度不為0的結(jié)點(diǎn)稱為分枝點(diǎn)或內(nèi)部結(jié)點(diǎn)，出度為0的結(jié)點(diǎn)稱為數(shù)葉或外部結(jié)點(diǎn)。注意：有向樹通常采用根在頂點(diǎn)上，所有邊方向向下的圖表示.(箭頭也可省略)

有向樹及應(yīng)用第四十五頁(yè)，共六十頁(yè)，編輯于2023年，星期日2.基本概念:設(shè)a和b是樹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的子樹.從樹根r到一結(jié)點(diǎn)a的路徑所含的邊數(shù)稱為a的路徑長(zhǎng)度。樹T中最長(zhǎng)的路徑稱為樹T的高度。例題:abc第四十六頁(yè)，共六十頁(yè)，編輯于2023年，星期日由有向樹的結(jié)構(gòu)可知，它還可以遞歸定義如下:3.有向樹有一個(gè)根，其余的結(jié)點(diǎn)劃分為m≥0個(gè)不相交的集合T1...Tm，且每個(gè)集合是子有向樹。第四十七頁(yè)，共六十頁(yè)，編輯于2023年，星期日4.有向樹的括號(hào)表示①若T中只有一個(gè)結(jié)點(diǎn)，則此結(jié)點(diǎn)就是它的括號(hào)表示。②若T由根v和子樹T1T2...Tn組成，則T的括號(hào)表示為v(T1T2...Tn）.

5.m元完全樹，正則樹的定義定義:在樹T中若每一結(jié)點(diǎn)的兒子個(gè)數(shù)小于或等于m,稱T為m元樹;在樹T中若每一結(jié)點(diǎn)的兒子個(gè)數(shù)等于m或者等于0，稱T為完全m元樹。若完全m元樹所有樹葉層次相同，稱為正則m元樹。第四十八頁(yè)，共六十頁(yè)，編輯于2023年，星期日5.有向森林定義

一個(gè)有向圖G，若它的每個(gè)連通分量是有向樹，稱G為(有向)森林，在森林中，若所有樹是有序樹，且給每棵樹指定次序，稱此森林為有序森林.bcbcabc完全3元樹完全2元樹正則2元樹第四十九頁(yè)，共六十頁(yè)，編輯于2023年，星期日

6、有序樹，有序森林與二元樹相互轉(zhuǎn)換①有序樹轉(zhuǎn)換為二元樹，轉(zhuǎn)換過程為：

a)在各兄弟結(jié)點(diǎn)之間加一連線。

b)對(duì)任何結(jié)點(diǎn)，除最左的兒子之外，擦掉該結(jié)點(diǎn)與其余兒子的聯(lián)線。

c)對(duì)新圖向下旋轉(zhuǎn)45度。bcbc------->第五十頁(yè)，共六十頁(yè)，編輯于2023年，星期日

2.有序森林轉(zhuǎn)換為二元樹轉(zhuǎn)換過程

a)設(shè)置一個(gè)總根，聯(lián)結(jié)各樹的根，得T`b)把T`轉(zhuǎn)換為二元樹

c)刪除總根第五十一頁(yè)，共六十頁(yè)，編輯于2023年，星期日

二.完全m元樹性質(zhì)

1.設(shè)完全m元樹，葉數(shù)為t，分枝數(shù)為i，則t=(m-1)i+1

解:i=[(t-1)/(m-1)]=[(10-1)/(3-1)]=5答:至少執(zhí)行5次加法指令.例：若t=i(m-1)+1計(jì)算機(jī)有一計(jì)算三數(shù)之和的加法器,現(xiàn)求十個(gè)數(shù)之和,問至少執(zhí)行多少次加法指令?證明:若把完全m元樹視為m個(gè)選手參加淘汰賽,則t表示選手總數(shù),i表示比賽場(chǎng)數(shù),每場(chǎng)比賽淘汰m-1人,共淘汰i(m-1)人,剩下一個(gè)冠軍,所以

t=(m-1)i+1第五十二頁(yè)，共六十頁(yè)，編輯于2023年，星期日2、內(nèi)部通數(shù)長(zhǎng)度I定義：各分枝點(diǎn)路徑長(zhǎng)度之和。內(nèi)部通數(shù)長(zhǎng)度E定義：各葉子路徑長(zhǎng)度之和.

性質(zhì)：完全二叉樹T有E=I+2n

其中:n為分枝點(diǎn)數(shù)第五十三頁(yè)，共六十頁(yè)，編輯于2023年，星期日證：對(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+l其關(guān)系為兄弟的葉子，得T`，T`與原樹比較，減少一個(gè)長(zhǎng)度為e的分枝點(diǎn)、二個(gè)長(zhǎng)度為e+1的葉子，增加一長(zhǎng)度為e的葉子，E`=I`+2（k-1）而I`=I-e.所以E`=E-2（e+1)+e,即E-2(e+1)+e=I-e+2(k-1)

所以E=I+2k.第五十四頁(yè)，共六十頁(yè)，編輯于2023年，星期日

三、前綴碼和最優(yōu)樹1、問題的引出：