定理霍夫曼算法市公開課一等獎省賽課獲獎課件

定理7.13:霍夫曼算法得到帶權w1,w2,,wn二分樹是最優(yōu)樹。分析:采取歸納法。n=2,結論成立假設n=k-1,結論成立。即用霍夫曼算法得到帶權w1,w2,,wk-1二分樹是最優(yōu)樹。對于n=k，用霍夫曼算法得到帶權w1,w2,,wk二分樹是最優(yōu)樹由歸納假設，用霍夫曼算法得到帶權w1+w2,w3,,wk二分樹是最優(yōu)樹。關鍵證實對于帶權w1+w2,w3,,wk最優(yōu)樹，用子樹代替帶權w1+w2樹葉，就是w1,w2,w3,,wk最優(yōu)樹

定理霍夫曼算法第1頁引理1：設有一棵帶權w1w2w3wk最優(yōu)樹，則必存在帶權為w1,w2樹葉為弟兄最優(yōu)樹。

引理2：若用霍夫曼算法可得到帶權w1+w2,,wn最優(yōu)樹T’,則用子樹代替帶權w1+w2樹葉，就是w1,w2,w3,,wk最優(yōu)樹?，F(xiàn)在證實該定理。定理霍夫曼算法第2頁證實:采取歸納法。n=2,結論成立假設n=k-1,結論成立。即用霍夫曼算法得到帶權w1,w2,,wk-1二分樹是最優(yōu)樹。對于n=k，由歸納假設，用霍夫曼算法得到帶權w1+w2,w3,,wk二分樹是最優(yōu)樹。由引理2得：對于帶權w1+w2,w3,,wk最優(yōu)樹，用子樹代替帶權w1+w2樹葉，就是w1,w2,w3,,wk最優(yōu)樹

定理霍夫曼算法第3頁樹是最小連通圖，刪去任何一條邊，必定不連通。定理霍夫曼算法第4頁第八章連通度，運輸網(wǎng)絡，匹配8.1連通度與塊為了衡量一個圖連通程度,定義圖兩個不變量:點連通度和邊連通度。定理霍夫曼算法第5頁一、點連通度與邊連通度1.點連通度定義8.1：設圖G頂點子集V'，若(G-V')>(G)，則稱V'為G一個點割。|V'|=1時,V'中頂點稱為割點。點割是集合，割點是頂點。G2中，v就是割點，{v}就是點割。定理霍夫曼算法第6頁定義8.2：設有圖G，為產(chǎn)生一個不連通圖或平凡圖需要從G中刪去最少頂點數(shù)稱為G點連通度，記為(G)，簡稱G連通度。顯然，G是不連通圖或平凡圖時,(G)=0;連通圖G有割點時,(G)=1;G是完全圖Kn時,(Kn)=n-1。必須說明是(G)=1,G并不一定有割點定理霍夫曼算法第7頁2.邊連通度定義8.3：設有圖G,為產(chǎn)生一個不連通圖或平凡圖需要從G中刪去最少邊數(shù)稱為G邊連通度，記為λ(G)。顯然,G是不連通圖或平凡圖時，λ(G)=0;；連通圖G有一橋時，λ(G)=1；G是完全圖Kn時，λ(Kn)=n-1。定理霍夫曼算法第8頁圖連通度有它實際應用。設n個頂點表示n個站,用e條邊連接起來,邊表示通信線,所謂連接好是指不易被破壞:(1)使之含有最大點連通度，這么當<κ(G)點(結點)被炸毀時，其余各點依然能夠通信(2)使之含有最大邊連通度,這么當λ(G)邊(線路)被炸毀時，各點依然能夠通信定理霍夫曼算法第9頁3.點連通度,邊連通度與最小頂點度數(shù)聯(lián)絡。定理8.1:對任何一個圖G，有κ(G)≤λ(G)≤δ(G)。證實：(1)λ(G)≤δ(G)若G是不連通圖或平凡圖，則λ(G)=0≤δ(G)，結論成立。下面考慮G是;連通圖情況。(2)κ(G)≤λ(G)若G是不連通圖或平凡圖，則κ(G)=0=λ(G)，結論成立。下面考慮G是連通圖情況。定理霍夫曼算法第10頁定義8.4:若圖Gκ(G)≥k，稱G是k-連通比如圖G3點連通度是2，所以它是2-連通,也是1-連通,但不是3-連通。非平凡連通圖是1-連通。定義8.5：若圖G邊連通度λ(G)≥k$,稱G是k-邊連通。比如圖G3邊連通度是2,所以它是2-邊連通,也是1-邊連通；但不是3-邊連通。定理霍夫曼算法第11頁二、割點與塊首先討論2-連通圖特征。為此,先討論一下割點。由定義8.4可知,有割點連通圖是1-連通,但不是2-連通,反之亦然。割點有以下幾個等價條件:定理8.2：設v是連通圖G一個頂點,以下論斷是等價:(1)v是G一個割點。(2)對于頂點v,存在兩個不一樣頂點u和w,使頂點v在每一條從u到w路上。(3)存在V-{v}一個分成U和W劃分,使對任意兩頂點uU和wW，頂點v在每一條從u到w路上。定理霍夫曼算法第12頁定理8.3：設G是頂點數(shù)n≥3連通圖,以下論斷是等價:(1)G中沒有割點。(2)G任意兩個頂點在同一條回路上。(3)G任意一個頂點和任意一條邊在同一條回路上。(4)G任意兩條邊在同一條回路上。