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

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

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

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

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

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

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

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

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

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

10、2，5，6，3，7)(8，3，4，3，8，4)離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院22生成樹生成樹(Spanning Tree)(3，2，2，3，4，1)(5，6，7，2，3，4)51326487反之，任給定由結(jié)點集合反之，任給定由結(jié)點集合V中的元素構(gòu)成的長為中的元素構(gòu)成的長為n-2的一個的一個序列序列(t1,t2,tn-2) ，可以如下地畫一棵生成樹。，可以如下地畫一棵生成樹。離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院23生成樹生成樹(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é) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院24生成樹生成樹(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é) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院25生成樹生成樹(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é) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院26生成樹生成樹(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é) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院27生成樹生成樹(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é) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院28生成樹生成樹(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é) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院29生成樹生成樹(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的生成樹集合存在雙射關(guān)系。的生成樹集合存在雙射關(guān)系。離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院302 生成樹生成樹(Spanning Tree)最小生成樹(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é) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院312 生成樹生成樹(Spanning Tree)算法正確性證明算法正確性證明設(shè)設(shè)T不是最小生成樹，則存在另一棵樹不是最小生成樹，則存在另一棵樹T*，為最小生成樹。，為最小生成樹。下面證明下面證明T*=T。首先設(shè)。首先設(shè)T的所有邊升序序列為的所有邊升序序列為e1e2e3em(對對T而言邊的升序序列即是按而言邊的升序序列即是按kruskal算法選擇邊算法選擇邊的順序的順序)：可以證明可以將可以證明可以將e1加入加入T*

15、中得到生成樹中得到生成樹T1,且滿足條件且滿足條件w(T1)=w(T*):將將e1加入加入T*中將形成環(huán)，此環(huán)中必然然存在邊中將形成環(huán)，此環(huán)中必然然存在邊e1在在T*中而不在中而不在T中中,于是于是,刪除刪除e1，則得到生成樹，則得到生成樹T1，按，按kruskal算法選擇邊的順序知算法選擇邊的順序知w(e1)=w(e1)，從而，從而w(T1)=w(T*)。依此進行依此進行，可以將，可以將ek加入到加入到Tk-1中，將形成環(huán)，此環(huán)中必然然存在邊中，將形成環(huán)，此環(huán)中必然然存在邊ek在在T*中而不在中而不在T中，于是，刪除中，于是，刪除ek，則得到生成樹則得到生成樹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中，得到生成樹中，得到生成樹Tm，且，且w(Tm)=w(Tk)= w(Tk-1)= =w(T1)=w(T*)。而此時，而此時， T所有邊都加入到所有邊都加入到Tm中，即中，即Tm=T。故。故w(T)=w(T*)因此，因此，T為最小生成樹。為最小生成樹。離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院323 有序樹有序樹(Order tree

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

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

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

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

21、(1)若T是有n個結(jié)點的完全二分樹，則T有(n+1)/2片樹葉。(2)T為有t片葉的完全兩分樹，則T有2(t-1)條邊離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院383 有序樹有序樹(Order tree)應(yīng)用（1）二叉樹，樹的遍歷，逆波蘭式（2）前綴碼最優(yōu)二分樹Huffman算法求帶權(quán)為2,3,5,7,8,9的最優(yōu)二分樹離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院393 有序樹有序樹(Order tree)應(yīng)用 二叉查找樹 決策樹， 平衡樹 離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院403 有序樹有序樹(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ù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院413 有序樹有序樹(Order tree)應(yīng)用平衡樹：若一棵高度為h的m元樹的所有結(jié)點都在h或h-1層。1 高度為h的m元樹：樹葉數(shù)t= ,若m元樹為完全的平衡的，則h=

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

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

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

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

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

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

29、質(zhì)大學(xué) 計算機學(xué)院計算機學(xué)院628圖的著色v v1 1v v4 4v v2 2v v3 3v v6 6v v8 8v v5 5v v7 7 解 (1) 根據(jù)遞減順序排列各結(jié)點： v5，v3，v7，v1，v2，v4，v6，v8。 (2) 對第一個點v5著第一種顏色，并對與之不相鄰的點v1著第一種顏色。 (3) 對v3著第二種顏色，并對與之不相鄰的點v4，v8著第二種顏色。 (4) 對v7和與之不相鄰的點v2，v6著第三種顏色。因此，右圖是三色圖。 離散數(shù)學(xué)離散數(shù)學(xué) 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計算機學(xué)院計算機學(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é)