課件代數(shù)結(jié)構(gòu)第十一章

1、離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院3Tree凱萊( Arthur Cayley)(1821-1895)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院4主要內(nèi)容主要內(nèi)容 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院51 樹(shù)及其性質(zhì)樹(shù)及其性質(zhì)樹(shù)樹(shù)（Tree）:無(wú)環(huán)的連通圖無(wú)環(huán)的連通圖森林森林（Forest）平凡樹(shù)平凡樹(shù)（Trivial Tree）樹(shù)葉樹(shù)葉（Leaf），），外部結(jié)點(diǎn)外部結(jié)點(diǎn) (度數(shù)為度數(shù)

2、為1)分支結(jié)點(diǎn)分支結(jié)點(diǎn)（Branched Vertex），），內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)（除樹(shù)葉結(jié)點(diǎn)之外的結(jié)點(diǎn)）（除樹(shù)葉結(jié)點(diǎn)之外的結(jié)點(diǎn)）離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院6離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院71 樹(shù)及其性質(zhì)樹(shù)及其性質(zhì)性質(zhì)性質(zhì)設(shè)圖設(shè)圖G=（n,m），如果），如果G滿足如下三個(gè)屬性中的兩個(gè)，則滿足如下三個(gè)屬性中的兩個(gè)，則G就是一棵樹(shù)，就是一棵樹(shù)，且可以推導(dǎo)出另一個(gè)屬性：且可以推導(dǎo)出另一個(gè)屬性：1) G連通；連通； 2) G中不存在環(huán)；中不存在環(huán)； 3) m=n-1離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院81

3、樹(shù)及其性質(zhì)樹(shù)及其性質(zhì)思考思考 下列命題是否為真？下列命題是否為真？1)在樹(shù)在樹(shù)T的任意二結(jié)點(diǎn)間添加一條邊后，將構(gòu)成包含該二結(jié)點(diǎn)的閉通的任意二結(jié)點(diǎn)間添加一條邊后，將構(gòu)成包含該二結(jié)點(diǎn)的閉通路，即存在環(huán)路，即存在環(huán)2)刪除樹(shù)刪除樹(shù)T的任意一條邊后，的任意一條邊后，T就不連通，即樹(shù)就不連通，即樹(shù)T的每一條邊均為的每一條邊均為T的的割邊割邊3)樹(shù)樹(shù)T的每一對(duì)結(jié)點(diǎn)間存在惟一一條路徑的每一對(duì)結(jié)點(diǎn)間存在惟一一條路徑4)結(jié)點(diǎn)數(shù)大于等于結(jié)點(diǎn)數(shù)大于等于2的任意樹(shù)，至少有兩片樹(shù)葉的任意樹(shù)，至少有兩片樹(shù)葉5)圖圖G為為n個(gè)結(jié)點(diǎn)、個(gè)結(jié)點(diǎn)、w個(gè)分圖的森林，則個(gè)分圖的森林，則G邊數(shù)為邊數(shù)為n-w離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)

4、中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院91 樹(shù)及其性質(zhì)樹(shù)及其性質(zhì) 示例示例 樹(shù)樹(shù)T具有具有ni個(gè)度數(shù)為個(gè)度數(shù)為i的結(jié)點(diǎn)，的結(jié)點(diǎn)，i=2，3，,k,其余為葉子結(jié)其余為葉子結(jié)點(diǎn)，問(wèn)該樹(shù)有多少葉子結(jié)點(diǎn)？點(diǎn)，問(wèn)該樹(shù)有多少葉子結(jié)點(diǎn)？離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院10相關(guān)知識(shí)點(diǎn)的回顧 無(wú)向圖G的生成子圖設(shè)G =,G =是兩個(gè)圖.若G G且 V V,則稱 G 是G的生成子圖.離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院112 生成樹(shù)生成樹(shù)(Spanning Tree)什么是生成樹(shù)? 若無(wú)向圖若無(wú)向圖G的一個(gè)生成子圖的一個(gè)生成子圖T是樹(shù)，則稱是樹(shù)，則稱T為為G

5、的的生成樹(shù)生成樹(shù) 樹(shù)枝樹(shù)枝、弦弦定理定理11.2 G是連通圖當(dāng)且僅當(dāng)是連通圖當(dāng)且僅當(dāng)G中存在生成樹(shù)。中存在生成樹(shù)。 請(qǐng)你思考請(qǐng)你思考 1) 只有連通圖才有生成樹(shù)? 2) 連通圖的至少有一棵生成樹(shù)？ 3) 設(shè)G為連通無(wú)向圖，那么G的任一回路與G T(任一生成樹(shù)T的相對(duì)G的補(bǔ))至少有一條公共邊。生成樹(shù)的構(gòu)造方法？生成樹(shù)的構(gòu)造方法？ “破圈破圈”法法離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院122 生成樹(shù)生成樹(shù)(Spanning Tree)求解生成樹(shù)算法(1)DFS算法 (2) BFS算法213214321543216543217654321876543217654321197

6、65432176543212132143215432165432111棧棧(stack)、隊(duì)列隊(duì)列(queue)教材示例教材示例11.2123478956離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院13生成樹(shù)生成樹(shù)(Spanning Tree)Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)(難點(diǎn)) 一個(gè)連通圖的生成樹(shù)不唯一。那么一個(gè)有一個(gè)連通圖的生成樹(shù)不唯一。那么一個(gè)有n個(gè)個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖頂點(diǎn)的標(biāo)號(hào)完全圖Kn有多少棵生成樹(shù)有多少棵生成樹(shù)尋找一個(gè)與之同構(gòu)的數(shù)學(xué)模型尋找一個(gè)與之同構(gòu)的數(shù)學(xué)模型由由n個(gè)元素構(gòu)成的長(zhǎng)為個(gè)元素構(gòu)成的長(zhǎng)為n-2的序列與之同構(gòu)。的序列與之同

7、構(gòu)。下面建立序列集合下面建立序列集合(t1,t2,tn-2)與生成樹(shù)集合之間的雙射關(guān)系。與生成樹(shù)集合之間的雙射關(guān)系。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院142 生成樹(shù)生成樹(shù)(Spanning Tree)由一棵生成樹(shù)可以得到一個(gè)與之對(duì)應(yīng)的序列。12845367(8，3，4，3，8，4)(1，2，5，6，3，7)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院15生成樹(shù)生成樹(shù)(Spanning Tree)Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)12845367(1)(8)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院

8、16Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)2845367(1，2)(8，3)生成樹(shù)生成樹(shù)(Spanning Tree)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院17 生成樹(shù)生成樹(shù)(Spanning Tree)Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)845367(1，2，5)(8，3，4)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院18 生成樹(shù)生成樹(shù)(Spanning Tree)Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)84367(1，2，5，6)(8，3，4，3)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)

9、中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院19生成樹(shù)生成樹(shù)(Spanning Tree)Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)8437(1，2，5，6，3)(8，3，4，3，8)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院20生成樹(shù)生成樹(shù)(Spanning Tree)Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)847(1，2，5，6，3，7)(8，3，4，3，8，4)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院21生成樹(shù)生成樹(shù)(Spanning Tree)Cayley定理：n個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖Kn有nn-2棵生成樹(shù)84(1，

10、2，5，6，3，7)(8，3，4，3，8，4)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院22生成樹(shù)生成樹(shù)(Spanning Tree)(3，2，2，3，4，1)(5，6，7，2，3，4)51326487反之，任給定由結(jié)點(diǎn)集合反之，任給定由結(jié)點(diǎn)集合V中的元素構(gòu)成的長(zhǎng)為中的元素構(gòu)成的長(zhǎng)為n-2的一個(gè)的一個(gè)序列序列(t1,t2,tn-2) ，可以如下地畫一棵生成樹(shù)。，可以如下地畫一棵生成樹(shù)。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院23生成樹(shù)生成樹(shù)(Spanning Tree)(3，2，2，3，4，1)(5)V=1,2,3,4,5,6,7,8 V- t1,

11、t2,t6 =5, 6,7,853離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院24生成樹(shù)生成樹(shù)(Spanning Tree)(3，2，2，3，4，1)S:(5)V=1,2,3,4,5,6,7,8 V- S-t2,t6 =6,7,8532S:(5，6)6離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院25生成樹(shù)生成樹(shù)(Spanning Tree)(3，2，2，3，4，1)S:(5，6)V=1,2,3,4,5,6,7,8 V- S-t3,t6 =7,8532S:(5，6，7)67離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院26生成樹(shù)生成樹(shù)(S

12、panning Tree)(3，2，2，3，4，1)S:(5，6，7)V=1,2,3,4,5,6,7,8 V- S-t4,t6 =2,8532S:(5，6，7，2)67離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院27生成樹(shù)生成樹(shù)(Spanning Tree)(3，2，2，3，4，1)S:(5，6，7，2)V=1,2,3,4,5,6,7,8 V- S-t5,t6 =3,8532S:(5，6，7，2，3)674離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院28生成樹(shù)生成樹(shù)(Spanning Tree)(3，2，2，3，4，1)S:(5，6，7，2，3)V=1,

13、2,3,4,5,6,7,8 V- S-t6 =4，8532S:(5，6，7，2，3，4)6741離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院29生成樹(shù)生成樹(shù)(Spanning Tree)(3，2，2，3，4，1)V=1,2,3,4,5,6,7,8 V- S=1，853S:(5，6，7，2，3，4)267418因此，序列集合因此，序列集合t1,t2,tn與與Kn的生成樹(shù)集合存在雙射關(guān)系。的生成樹(shù)集合存在雙射關(guān)系。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院302 生成樹(shù)生成樹(shù)(Spanning Tree)最小生成樹(shù)(minimum spanning tre

14、e) 算法？ Kruskal算法算法證明？1 6 2 11 3 7 84 52 3 1 3 3 29 10 1 2 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院312 生成樹(shù)生成樹(shù)(Spanning Tree)算法正確性證明算法正確性證明設(shè)設(shè)T不是最小生成樹(shù)，則存在另一棵樹(shù)不是最小生成樹(shù)，則存在另一棵樹(shù)T*，為最小生成樹(shù)。，為最小生成樹(shù)。下面證明下面證明T*=T。首先設(shè)。首先設(shè)T的所有邊升序序列為的所有邊升序序列為e1e2e3em(對(duì)對(duì)T而言邊的升序序列即是按而言邊的升序序列即是按kruskal算法選擇邊算法選擇邊的順序的順序)：可以證明可以將可以證明可以將e1加入加入T*

15、中得到生成樹(shù)中得到生成樹(shù)T1,且滿足條件且滿足條件w(T1)=w(T*):將將e1加入加入T*中將形成環(huán)，此環(huán)中必然然存在邊中將形成環(huán)，此環(huán)中必然然存在邊e1在在T*中而不在中而不在T中中,于是于是,刪除刪除e1，則得到生成樹(shù)，則得到生成樹(shù)T1，按，按kruskal算法選擇邊的順序知算法選擇邊的順序知w(e1)=w(e1)，從而，從而w(T1)=w(T*)。依此進(jìn)行依此進(jìn)行，可以將，可以將ek加入到加入到Tk-1中，將形成環(huán)，此環(huán)中必然然存在邊中，將形成環(huán)，此環(huán)中必然然存在邊ek在在T*中而不在中而不在T中，于是，刪除中，于是，刪除ek，則得到生成樹(shù)則得到生成樹(shù)Tk。而顯然，兩邊序列。而顯然，

16、兩邊序列e1e2e3ek 與與 e1e2e3ek均不構(gòu)成環(huán)，而按均不構(gòu)成環(huán)，而按kruskal算法，必然有算法，必然有 w(ek)=w(ek)，從而從而 w(Tk)= w(Tk-1)=w(T*) ，最后可以將最后可以將em加入到加入到Tm-1中，得到生成樹(shù)中，得到生成樹(shù)Tm，且，且w(Tm)=w(Tk)= w(Tk-1)= =w(T1)=w(T*)。而此時(shí)，而此時(shí)， T所有邊都加入到所有邊都加入到Tm中，即中，即Tm=T。故。故w(T)=w(T*)因此，因此，T為最小生成樹(shù)。為最小生成樹(shù)。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院323 有序樹(shù)有序樹(shù)(Order tree

17、)有關(guān)術(shù)語(yǔ) 有向樹(shù) 根樹(shù), 樹(shù)高度 有序樹(shù): (完全)m分樹(shù)、 (完全)二叉樹(shù) 父結(jié)點(diǎn)父結(jié)點(diǎn)/孩子結(jié)點(diǎn)；孩子結(jié)點(diǎn)； 分支結(jié)點(diǎn)分支結(jié)點(diǎn)/葉子結(jié)點(diǎn)葉子結(jié)點(diǎn), 內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)/外部結(jié)點(diǎn)；外部結(jié)點(diǎn)；孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)/非孩子結(jié)點(diǎn)非孩子結(jié)點(diǎn)v v1 1v v8 8v v4 4v v3 3 v v7 7v v6 6 v v2 2 v v5 5離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院333 有序樹(shù)有序樹(shù)(Order tree) 若若T T是一棵根樹(shù)。存在一個(gè)從是一棵根樹(shù)。存在一個(gè)從T T的邊集的邊集E E到自然數(shù)集到自然數(shù)集N N的映射的映射f f，當(dāng)，當(dāng)f(uf(u，v)=nv)=

18、n時(shí)，稱時(shí)，稱v v是是u u的第的第n n個(gè)個(gè)后繼后繼，并稱，并稱T T為一棵為一棵有序樹(shù)有序樹(shù)。 若有序樹(shù)若有序樹(shù)T T的每一結(jié)點(diǎn)的每一結(jié)點(diǎn)u u，degdeg+ +(u)m(u)m時(shí)，對(duì)任一邊時(shí)，對(duì)任一邊x x，有有f(x)mf(x)m，則稱，則稱T T為為m m分樹(shù)分樹(shù)； 若若m m分樹(shù)中每一結(jié)點(diǎn)分樹(shù)中每一結(jié)點(diǎn)u u，有，有degdeg+ +(u)=m(u)=m或或degdeg+ +(u)=0(u)=0，則，則T T稱為稱為完全完全m m分樹(shù)分樹(shù)( (完全完全m m叉樹(shù)叉樹(shù)) )； 若完全若完全m m分樹(shù)分樹(shù)T T的所有葉結(jié)點(diǎn)到根的距離相等，則稱的所有葉結(jié)點(diǎn)到根的距離相等，則稱T T為

19、為正則正則m m分樹(shù)分樹(shù)。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院343 有序樹(shù)有序樹(shù)(Order tree) 例11.6 證明：存在一棵有n片葉的完全兩分樹(shù)。 證明 用數(shù)學(xué)歸納法：當(dāng)n=1時(shí)，是平凡樹(shù)，結(jié)論是顯見(jiàn)。 設(shè)n=k-1時(shí)，存在完全兩分樹(shù)Tk-1，Tk-1有k-1片葉子。 取Tk-1中任意一片葉子v，加上兩個(gè)點(diǎn)u、w作為v的后繼，得到樹(shù)Tk，Tk仍是完全兩分樹(shù)，Tk恰好有k片葉。綜上命題得證。 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院353 有序樹(shù)有序樹(shù)(Order tree)定理11.5 證明 對(duì)i施歸納法：當(dāng)i=0，1時(shí)，結(jié)論顯見(jiàn)。

20、 設(shè)i=k時(shí)，(m-1)k=t-1成立。 考慮i=k+1時(shí)，設(shè)T是具有k+1個(gè)分枝點(diǎn)，t片葉的完全m分樹(shù)。從T中找到一個(gè)具有m片葉的分枝點(diǎn)v，去掉v的m片葉，得到樹(shù)T。T仍是一個(gè)m分樹(shù)，且具有t-(m-1)片葉，k個(gè)分枝點(diǎn)。由歸納假設(shè)，對(duì)于T有：(m-1)k=(t-(m-1)-1，即有(m-1)(k+1)=t-1，亦即對(duì)于i=k+1時(shí)，結(jié)論仍成立。 由歸納原理，定理得證。 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院363 有序樹(shù)有序樹(shù)(Order tree)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院373 有序樹(shù)有序樹(shù)(Order tree)問(wèn)題探討

21、(1)若T是有n個(gè)結(jié)點(diǎn)的完全二分樹(shù)，則T有(n+1)/2片樹(shù)葉。(2)T為有t片葉的完全兩分樹(shù)，則T有2(t-1)條邊離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院383 有序樹(shù)有序樹(shù)(Order tree)應(yīng)用（1）二叉樹(shù)，樹(shù)的遍歷，逆波蘭式（2）前綴碼最優(yōu)二分樹(shù)Huffman算法求帶權(quán)為2,3,5,7,8,9的最優(yōu)二分樹(shù)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院393 有序樹(shù)有序樹(shù)(Order tree)應(yīng)用 二叉查找樹(shù) 決策樹(shù)， 平衡樹(shù) 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院403 有序樹(shù)有序樹(shù)(Order tree) 有

22、8枚硬幣，其中恰有1枚是假幣，假幣比真幣輕。試用一架天平稱出假幣，使稱量的次數(shù)盡可能地少。 11，2 2，3 63 6，7 7，88 左盤輕左盤輕 水平水平 右盤輕右盤輕 1 3 4 5 6 81 3 4 5 6 8 左盤輕左盤輕 水平水平 右盤輕右盤輕 左盤輕左盤輕 右盤輕右盤輕 左盤輕左盤輕 水平水平 右盤輕右盤輕1 2 3 4 5 6 7 8決策樹(shù)決策樹(shù)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院413 有序樹(shù)有序樹(shù)(Order tree)應(yīng)用平衡樹(shù)：若一棵高度為h的m元樹(shù)的所有結(jié)點(diǎn)都在h或h-1層。1 高度為h的m元樹(shù)：樹(shù)葉數(shù)t= ,若m元樹(shù)為完全的平衡的，則h=

23、.離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院42小結(jié)與作業(yè)小結(jié)小結(jié)作業(yè)作業(yè)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院4311.2平面圖與圖的著色離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院441平面圖的概念離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院451什么是平面圖 示例示例4 4平面圖的應(yīng)用平面圖的應(yīng)用：要在三座房屋和三個(gè)設(shè)施（水、電、氣）之：要在三座房屋和三個(gè)設(shè)施（水、電、氣）之間建立管線鏈接，問(wèn)是否可能使這些線路互不相交？這個(gè)問(wèn)間建立管線鏈接，問(wèn)是否可能使這些線路互不相交？這個(gè)問(wèn)題其實(shí)是判斷題其實(shí)是判斷

24、K3,3是否為平面圖的問(wèn)題。是否為平面圖的問(wèn)題。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院46平面圖平面圖 G(6，9，5)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院471什么是平面圖 示例示例1 1 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院48什么是平面圖 示例示例2 2 (a) (b)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院49示例3 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院501什么是平面圖 示例示例4 4K3,3是邊數(shù)最少的非平面圖，是邊數(shù)最少的非平面圖，K5是結(jié)點(diǎn)數(shù)最少

25、的非平面圖。是結(jié)點(diǎn)數(shù)最少的非平面圖。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院512平面圖性質(zhì)1 定理1：一個(gè)有限平面圖，面的次數(shù)之和等于其邊數(shù) 的兩倍。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院522平面圖性質(zhì)歐拉定理的證明：歐拉定理的證明：證明：證明： 對(duì)面數(shù)對(duì)面數(shù)f進(jìn)行歸納。進(jìn)行歸納。當(dāng)當(dāng)f=1時(shí)，時(shí)，G中無(wú)回路，因而中無(wú)回路，因而G是一課樹(shù)，故有是一課樹(shù)，故有n=m+1，即，即。假設(shè)假設(shè)f=k-1時(shí)，定理成立。時(shí)，定理成立?？疾炜疾靎=k時(shí)，設(shè)圖時(shí)，設(shè)圖G有有n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，m條邊。因?yàn)闂l邊。因?yàn)閗=2，所以，所以G這至少有一個(gè)環(huán)將這至少有

26、一個(gè)環(huán)將外部面與內(nèi)部面分開(kāi)。外部面與內(nèi)部面分開(kāi)。從任一環(huán)中去掉一條邊，得到從任一環(huán)中去掉一條邊，得到G(G仍連通仍連通)，因?yàn)槿サ舻倪呍谶€中，一定是兩，因?yàn)槿サ舻倪呍谶€中，一定是兩個(gè)面的公共邊。將其去掉后這兩個(gè)面就連成了一個(gè)面，圖個(gè)面的公共邊。將其去掉后這兩個(gè)面就連成了一個(gè)面，圖G的面數(shù)為的面數(shù)為k-1，邊數(shù)為邊數(shù)為m-1，結(jié)點(diǎn)數(shù)為，結(jié)點(diǎn)數(shù)為n。由歸納假設(shè)，對(duì)圖。由歸納假設(shè)，對(duì)圖G n-(m-1)+(k-1)=2 即即。即即f=k時(shí)，定理成立。由歸納法得歐拉定理成立。時(shí)，定理成立。由歸納法得歐拉定理成立。離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院532平面圖性質(zhì)離散數(shù)學(xué)離

27、散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院542平面圖性質(zhì)離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院553平面圖的判定 如下圖所示，G1、G2均為G的細(xì)分，當(dāng)然也可以認(rèn)為G也是自身的細(xì)分。 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院563平面圖的判定 平面圖的判定定理：圖G是平面圖，當(dāng)且僅當(dāng)K5與K3,3的任何細(xì)分圖都不是G的子圖。 Peterson圖離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院574四色定理 四色猜想四色定理 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院585著色問(wèn)題離散數(shù)學(xué)離散數(shù)

28、學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院598圖的著色離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院608圖的著色離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院618圖的著色 至今還沒(méi)有一個(gè)簡(jiǎn)單方法可以確定任一圖G是否是k色的。通?？捎肞owell方法對(duì)圖進(jìn)行著色，其過(guò)程如下： 將圖G的結(jié)點(diǎn)按度數(shù)遞減的次序排列(這種排列不一定惟一)。 用第一種顏色對(duì)第一點(diǎn)著色，并按排列次序，對(duì)與前面著色點(diǎn)不鄰接的每一點(diǎn)著上同樣的顏色。 用第二種顏色對(duì)尚未著色的點(diǎn)重復(fù)(2)，用第三種顏色繼續(xù)這種做法，直到所有的點(diǎn)全部著上色為止。 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地

29、質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院628圖的著色v v1 1v v4 4v v2 2v v3 3v v6 6v v8 8v v5 5v v7 7 解 (1) 根據(jù)遞減順序排列各結(jié)點(diǎn)： v5，v3，v7，v1，v2，v4，v6，v8。 (2) 對(duì)第一個(gè)點(diǎn)v5著第一種顏色，并對(duì)與之不相鄰的點(diǎn)v1著第一種顏色。 (3) 對(duì)v3著第二種顏色，并對(duì)與之不相鄰的點(diǎn)v4，v8著第二種顏色。 (4) 對(duì)v7和與之不相鄰的點(diǎn)v2，v6著第三種顏色。因此，右圖是三色圖。 離散數(shù)學(xué)離散數(shù)學(xué) 中國(guó)地質(zhì)大學(xué)中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院638圖的著色教授教授所授課程所授課程AgnesiAgnesi132,136,211132,136,211BernoulliBernoulli127,131,153127,131,153CauchyCauchy131,132,211131,132,211DescartesDescartes127,131,205127,131,205EulerEuler131,138,154131,138,154FrobeniusFrobenius132,136,201132,136,201GaussGauss127,131,138127,131,138HamiltonHamilton153,154,205153,154,205離散數(shù)學(xué)