離散數(shù)學(xué)圖論學(xué)習(xí)教案

1、會計學(xué)1離散數(shù)學(xué)圖論離散數(shù)學(xué)圖論第一頁，編輯于星期二：十一點 六分。第1頁/共237頁第二頁，編輯于星期二：十一點 六分。 圖圖 10.1.1哥尼斯堡七橋問題第2頁/共237頁第三頁，編輯于星期二：十一點 六分。之為邊。這樣利用一個圖形使之為邊。這樣利用一個圖形使各隊之間的比賽情況一目了然。各隊之間的比賽情況一目了然。1.圖的定義圖的定義 10.1 圖的基本概念圖的基本概念 第3頁/共237頁第四頁，編輯于星期二：十一點 六分。 圖圖 10.1.1如果圖如果圖 10.1.1中的中的個結(jié)點個結(jié)點a， b， c， d分別表示個人，當(dāng)某分別表示個人，當(dāng)某兩個人互相認(rèn)識時，兩個人互相認(rèn)識時， 則則將其

2、對應(yīng)點之間用邊連將其對應(yīng)點之間用邊連接起來。接起來。 這時的圖又反這時的圖又反映了這個人之間的認(rèn)映了這個人之間的認(rèn)識關(guān)系。識關(guān)系。第4頁/共237頁第五頁，編輯于星期二：十一點 六分。第5頁/共237頁第六頁，編輯于星期二：十一點 六分。我們將結(jié)點我們將結(jié)點a、b的無序結(jié)點對記為的無序結(jié)點對記為(a，b），）， 有序結(jié)有序結(jié)點對記為點對記為a，b。 一個圖一個圖G可用一個圖形來表示且表示是不唯一的?？捎靡粋€圖形來表示且表示是不唯一的。 第6頁/共237頁第七頁，編輯于星期二：十一點 六分。圖圖 10.1.2 第7頁/共237頁第八頁，編輯于星期二：十一點 六分。圖 10.1.2 第8頁/共23

3、7頁第九頁，編輯于星期二：十一點 六分。第9頁/共237頁第十頁，編輯于星期二：十一點 六分。第10頁/共237頁第十一頁，編輯于星期二：十一點 六分。圖圖 10 .1. 3第11頁/共237頁第十二頁，編輯于星期二：十一點 六分。第12頁/共237頁第十三頁，編輯于星期二：十一點 六分。G1、G2是多重圖是多重圖G3是線圖是線圖G4是簡單圖是簡單圖第13頁/共237頁第十四頁，編輯于星期二：十一點 六分。第14頁/共237頁第十五頁，編輯于星期二：十一點 六分。圖圖 10 .1. 4(5)按按G的任意兩個結(jié)點間是否有邊分為的任意兩個結(jié)點間是否有邊分為完全圖完全圖Kn (如圖如圖 10.1.5

4、)和和不完全圖不完全圖(如圖如圖 10.1.6)。第15頁/共237頁第十六頁，編輯于星期二：十一點 六分。完全圖完全圖：任意兩個不同的結(jié)點都鄰接的簡單圖稱為完全圖：任意兩個不同的結(jié)點都鄰接的簡單圖稱為完全圖。n 個結(jié)點的無向完全圖記為個結(jié)點的無向完全圖記為Kn。 圖圖10.1.5給出了給出了K3和和K4。從圖中可以看出。從圖中可以看出K3有有條邊，條邊，K4有條邊。有條邊。 容易證明容易證明Kn有有 條邊。條邊。(1)2n n 圖圖 10 .1. 6圖圖 10.1.5 K3與與K4示意圖示意圖第16頁/共237頁第十七頁，編輯于星期二：十一點 六分。例例213213有向完全圖有向完全圖無向完

5、全圖無向完全圖第17頁/共237頁第十八頁，編輯于星期二：十一點 六分。G第18頁/共237頁第十九頁，編輯于星期二：十一點 六分。G相對于相對于Kn的補圖是下圖中的的補圖是下圖中的G第19頁/共237頁第二十頁，編輯于星期二：十一點 六分。第20頁/共237頁第二十一頁，編輯于星期二：十一點 六分?；檠a圖互為補圖互為補圖互為補圖互為補圖互為補圖第21頁/共237頁第二十二頁，編輯于星期二：十一點 六分。一個有個結(jié)點的圖一個有個結(jié)點的圖G，G或或中含有一個三角形（即中含有一個三角形（即K3）。）。G第22頁/共237頁第二十三頁，編輯于星期二：十一點 六分。中任意兩個在中任意兩個在G中均不鄰

6、接，中均不鄰接，則則v1，v2，v3就是就是中一個中一個三角形的個頂點。三角形的個頂點。GG第23頁/共237頁第二十四頁，編輯于星期二：十一點 六分。 定義定義: 在有向圖中在有向圖中, 以以v為終點的邊數(shù)稱為結(jié)點為終點的邊數(shù)稱為結(jié)點v 的入度，的入度， 記為記為 ;以以v為始點的邊數(shù)稱為結(jié)點為始點的邊數(shù)稱為結(jié)點v 的出度，的出度， 記記為為 。結(jié)點。結(jié)點v的入度與出度之和稱為結(jié)點的入度與出度之和稱為結(jié)點v的度數(shù)，的度數(shù)，記為記為 d(v)或或deg(v)。 ( )dv( )dv第24頁/共237頁第二十五頁，編輯于星期二：十一點 六分。| )(min)( | )(max)( VvvdGVv

7、vdG最小度最大度第25頁/共237頁第二十六頁，編輯于星期二：十一點 六分。例例245136G1頂點頂點2入度：入度：1 出度：出度：3頂點頂點4入度：入度：1 出度：出度：0例例157324G26頂點頂點5的度：的度：3頂點頂點2的度：的度：4第26頁/共237頁第二十七頁，編輯于星期二：十一點 六分。d( )2VE第27頁/共237頁第二十八頁，編輯于星期二：十一點 六分。1deg( )VEvvVvVv2)deg()deg(212)deg(Vvv第28頁/共237頁第二十九頁，編輯于星期二：十一點 六分。 定理定理 10.1.2 在任何有向圖在任何有向圖GV ,E中，中， 有有( )(

8、)v Vv VdvdvE圖圖10.1.4第29頁/共237頁第三十頁，編輯于星期二：十一點 六分。第30頁/共237頁第三十一頁，編輯于星期二：十一點 六分。356例例245136圖與子圖圖與子圖第31頁/共237頁第三十二頁，編輯于星期二：十一點 六分。圖圖10.1.7 圖圖G以及其真子圖以及其真子圖G 1和生成子圖和生成子圖G2第32頁/共237頁第三十三頁，編輯于星期二：十一點 六分。例例 畫出畫出K4的所有非同構(gòu)的生成子圖。的所有非同構(gòu)的生成子圖。第33頁/共237頁第三十四頁，編輯于星期二：十一點 六分。2221112222222222222 , , GV EGV Euvu vEGV

9、GVG VGEGEEEGV結(jié)點定義： 設(shè)圖是圖的子圖。若對任意結(jié)點 和 ，如果，則由唯一地確定，并稱是，記為或。如果無孤立結(jié)點，且集合的誘導(dǎo)子圖邊集的誘導(dǎo)子圖由所唯一確定，則稱是，記為或。第34頁/共237頁第三十五頁，編輯于星期二：十一點 六分。試觀察下面各圖有何異同？試觀察下面各圖有何異同？第35頁/共237頁第三十六頁，編輯于星期二：十一點 六分。 圖圖 10.1.8 同構(gòu)的圖同構(gòu)的圖 圖圖 10.1.9第36頁/共237頁第三十七頁，編輯于星期二：十一點 六分。第37頁/共237頁第三十八頁，編輯于星期二：十一點 六分。圖圖 10.1.9第38頁/共237頁第三十九頁，編輯于星期二：十

10、一點 六分。第39頁/共237頁第四十頁，編輯于星期二：十一點 六分。第40頁/共237頁第四十一頁，編輯于星期二：十一點 六分。第41頁/共237頁第四十二頁，編輯于星期二：十一點 六分。第42頁/共237頁第四十三頁，編輯于星期二：十一點 六分。第43頁/共237頁第四十四頁，編輯于星期二：十一點 六分。第44頁/共237頁第四十五頁，編輯于星期二：十一點 六分。第45頁/共237頁第四十六頁，編輯于星期二：十一點 六分。第46頁/共237頁第四十七頁，編輯于星期二：十一點 六分。第47頁/共237頁第四十八頁，編輯于星期二：十一點 六分。結(jié)點重復(fù)情況結(jié)點重復(fù)情況邊重復(fù)情況邊重復(fù)情況路路

11、允許允許 允許允許簡單路簡單路 允許允許不允許不允許 基本路基本路 不允許不允許 不允許不允許 回路回路允許允許允許允許簡單圈簡單圈允許允許不允許不允許基本圈基本圈不允許不允許不允許不允許第48頁/共237頁第四十九頁，編輯于星期二：十一點 六分。第49頁/共237頁第五十頁，編輯于星期二：十一點 六分。例例157324G26例例245136G1路徑：路徑：1，2，3，5，6，3路徑長度：路徑長度：5簡單路徑：簡單路徑：1，2，3，5回路：回路：1，2，3，5，6，3，1簡單回路：簡單回路：3，5，6，3路徑：路徑：1，2，5，7，6，5，2，3路徑長度：路徑長度：7簡單路徑：簡單路徑：1，2

12、，5，7，6回路：回路：1，2，5，7，6，5，2，1簡單回路：簡單回路：1，2，3，1第50頁/共237頁第五十一頁，編輯于星期二：十一點 六分。圖圖 10.2.1 第51頁/共237頁第五十二頁，編輯于星期二：十一點 六分。第52頁/共237頁第五十三頁，編輯于星期二：十一點 六分。圖圖 10.2.1 第53頁/共237頁第五十四頁，編輯于星期二：十一點 六分。第54頁/共237頁第五十五頁，編輯于星期二：十一點 六分。第55頁/共237頁第五十六頁，編輯于星期二：十一點 六分。10.2.2 圖的連通性圖的連通性(The Connectivity of Graphs)第56頁/共237頁第

13、五十七頁，編輯于星期二：十一點 六分。圖圖 10.2.3 圖圖G與與G 在圖在圖10.2.3中，中， G是不連通的，是不連通的， （G），）， 而而G是是連通的，連通的， （G）。）。 任何一個圖都可劃分為若干個連通分支。任何一個圖都可劃分為若干個連通分支。 顯然，顯然， 僅當(dāng)僅當(dāng)圖圖G的連通分支數(shù)的連通分支數(shù)（G）時，）時， 圖圖G是連通的。是連通的。10.2.2 圖的連通性圖的連通性第57頁/共237頁第五十八頁，編輯于星期二：十一點 六分。第58頁/共237頁第五十九頁，編輯于星期二：十一點 六分。第59頁/共237頁第六十頁，編輯于星期二：十一點 六分。第60頁/共237頁第六十一頁，

14、編輯于星期二：十一點 六分。VSmin第61頁/共237頁第六十二頁，編輯于星期二：十一點 六分。ETmin第62頁/共237頁第六十三頁，編輯于星期二：十一點 六分。第63頁/共237頁第六十四頁，編輯于星期二：十一點 六分。第64頁/共237頁第六十五頁，編輯于星期二：十一點 六分。10.2.2 圖的連通性圖的連通性第65頁/共237頁第六十六頁，編輯于星期二：十一點 六分。 從定義可知：從定義可知： 若圖若圖G是單向連通的，是單向連通的， 則必是弱連通的；若圖則必是弱連通的；若圖G是強連通的，是強連通的， 則則必是單向連通的，必是單向連通的， 且也是弱連通的。且也是弱連通的。 但反之但反

15、之不真。不真。 第66頁/共237頁第六十七頁，編輯于星期二：十一點 六分。第67頁/共237頁第六十八頁，編輯于星期二：十一點 六分。10.2.2 圖的連通性圖的連通性第68頁/共237頁第六十九頁，編輯于星期二：十一點 六分。10.2.2 圖的連通性圖的連通性第69頁/共237頁第七十頁，編輯于星期二：十一點 六分。連通圖連通圖例例245136強連通圖強連通圖356例例非連通圖非連通圖連通分圖連通分圖例例245136第70頁/共237頁第七十一頁，編輯于星期二：十一點 六分。圖圖 10.2.5 10.2.2 圖的連通性圖的連通性(The Connectivity of Graphs)第71

16、頁/共237頁第七十二頁，編輯于星期二：十一點 六分。10.2.2 圖的連通性圖的連通性第72頁/共237頁第七十三頁，編輯于星期二：十一點 六分。第73頁/共237頁第七十四頁，編輯于星期二：十一點 六分。第74頁/共237頁第七十五頁，編輯于星期二：十一點 六分。第75頁/共237頁第七十六頁，編輯于星期二：十一點 六分。第76頁/共237頁第七十七頁，編輯于星期二：十一點 六分。第77頁/共237頁第七十八頁，編輯于星期二：十一點 六分。第78頁/共237頁第七十九頁，編輯于星期二：十一點 六分。第79頁/共237頁第八十頁，編輯于星期二：十一點 六分。第80頁/共237頁第八十一頁，編

17、輯于星期二：十一點 六分。1( ,)0ijijEa 否則否則 如圖如圖10.3.1所示的圖所示的圖G， 其鄰接矩陣其鄰接矩陣A為為第81頁/共237頁第八十二頁，編輯于星期二：十一點 六分。0111110100110101010110010A 顯然無向圖的鄰接矩陣必是對稱的。顯然無向圖的鄰接矩陣必是對稱的。 下面的定理說明，下面的定理說明， 在鄰接矩陣在鄰接矩陣A的冪的冪A2， A3， 等矩陣中，等矩陣中， 每個元素有特定的含義。每個元素有特定的含義。 圖圖10.3.1 G 第82頁/共237頁第八十三頁，編輯于星期二：十一點 六分。圖圖10.3.1 圖圖G 第83頁/共237頁第八十四頁，編

18、輯于星期二：十一點 六分。所以所以 rjnrlirlijaaa1)()1(第84頁/共237頁第八十五頁，編輯于星期二：十一點 六分。第85頁/共237頁第八十六頁，編輯于星期二：十一點 六分。第86頁/共237頁第八十七頁，編輯于星期二：十一點 六分。3) Al的（的（i， i）項元素）項元素a(l)ii表示開始并結(jié)束于表示開始并結(jié)束于vi長度為長度為l的回路的數(shù)目。的回路的數(shù)目。第87頁/共237頁第八十八頁，編輯于星期二：十一點 六分。 圖圖 10.3.2第88頁/共237頁第八十九頁，編輯于星期二：十一點 六分。0100010000000100010100010A第89頁/共237頁第

19、九十頁，編輯于星期二：十一點 六分。第90頁/共237頁第九十一頁，編輯于星期二：十一點 六分。, 0)4(34)3(34)2(34)1(34aaaa第91頁/共237頁第九十二頁，編輯于星期二：十一點 六分。但注意這里但注意這里A不一定是對稱的。不一定是對稱的。01ija否則Evvji,第92頁/共237頁第九十三頁，編輯于星期二：十一點 六分。10ijp (vi到到vj可達(dá)可達(dá)) (否則否則) 第93頁/共237頁第九十四頁，編輯于星期二：十一點 六分。 根據(jù)可達(dá)性矩陣，根據(jù)可達(dá)性矩陣， 可知圖中任意兩個結(jié)點可知圖中任意兩個結(jié)點之間是否至少存在一條路以及是否存在回路。之間是否至少存在一條路

20、以及是否存在回路。 根據(jù)根據(jù)n個結(jié)點的圖中，基本路的長度不大個結(jié)點的圖中，基本路的長度不大于于n-1，基本圈的長度不大于，基本圈的長度不大于n。因此，。因此， 分以分以下兩步可得到可達(dá)性矩陣。下兩步可得到可達(dá)性矩陣。 第94頁/共237頁第九十五頁，編輯于星期二：十一點 六分。第95頁/共237頁第九十六頁，編輯于星期二：十一點 六分。第96頁/共237頁第九十七頁，編輯于星期二：十一點 六分。第97頁/共237頁第九十八頁，編輯于星期二：十一點 六分。nk1nk1第98頁/共237頁第九十九頁，編輯于星期二：十一點 六分。nk1arijarij)(arij)(arij)(arijrija()

21、rija()rija()rija第99頁/共237頁第一百頁，編輯于星期二：十一點 六分。圖圖 10.3.3第100頁/共237頁第一百零一頁，編輯于星期二：十一點 六分。0100001011001110A(2)010001000010001000101100110011000110111011101110A第101頁/共237頁第一百零二頁，編輯于星期二：十一點 六分。(3)(4)(1)(2)(3)(4)110001 10011011 10111011 10111011 101 1 101 1 101 1 101 1 10AAPAAAA故故 第102頁/共237頁第一百零三頁，編輯于星期二：

22、十一點 六分。第103頁/共237頁第一百零四頁，編輯于星期二：十一點 六分。nk1nk1第104頁/共237頁第一百零五頁，編輯于星期二：十一點 六分。第105頁/共237頁第一百零六頁，編輯于星期二：十一點 六分。第106頁/共237頁第一百零七頁，編輯于星期二：十一點 六分。第107頁/共237頁第一百零八頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第108頁/共237頁第一百零九頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第109頁/共237頁第一百一十頁，編輯于星期二：十一點 六分。圖 10.4.1哥尼斯堡七橋問題示

23、圖 10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第110頁/共237頁第一百一十一頁，編輯于星期二：十一點 六分。 圖圖 10.4.2哥尼斯保七橋問題簡化圖哥尼斯保七橋問題簡化圖 10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第111頁/共237頁第一百一十二頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第112頁/共237頁第一百一十三頁，編輯于星期二：十一點 六分。 圖圖 10.4.310.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第113頁/共237頁第一百一十四頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第114頁/共2

24、37頁第一百一十五頁，編輯于星期二：十一點 六分。 圖圖 10.4.4 圖圖G 10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第115頁/共237頁第一百一十六頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第116頁/共237頁第一百一十七頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第117頁/共237頁第一百一十八頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第118頁/共237頁第一百一十九頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第119頁/共237頁第一

25、百二十頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第120頁/共237頁第一百二十一頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第121頁/共237頁第一百二十二頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第122頁/共237頁第一百二十三頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第123頁/共237頁第一百二十四頁，編輯于星期二：十一點 六分。圖圖 10.4.510.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第124頁/共237頁第一百二十五頁，編輯于星期二

26、：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第125頁/共237頁第一百二十六頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第126頁/共237頁第一百二十七頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第127頁/共237頁第一百二十八頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第128頁/共237頁第一百二十九頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第129頁/共237頁第一百三十頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓

27、圖歐拉圖與哈密爾頓圖第130頁/共237頁第一百三十一頁，編輯于星期二：十一點 六分。圖圖 10.4.610.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第131頁/共237頁第一百三十二頁，編輯于星期二：十一點 六分。 圖圖 10.4.7 歐拉有向路示圖歐拉有向路示圖 10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第132頁/共237頁第一百三十三頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第133頁/共237頁第一百三十四頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第134頁/共237頁第一百三十五頁，編輯于星期二：十一點 六

28、分。 圖圖 10.4.8 具有具有 8 個結(jié)點的有向圖個結(jié)點的有向圖G 第135頁/共237頁第一百三十六頁，編輯于星期二：十一點 六分。第136頁/共237頁第一百三十七頁，編輯于星期二：十一點 六分。圖圖 10.4.9 12 面體游戲示圖面體游戲示圖 10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第137頁/共237頁第一百三十八頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第138頁/共237頁第一百三十九頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第139頁/共237頁第一百四十頁，編輯于星期二：十一點 六分。10.4

29、歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第140頁/共237頁第一百四十一頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第141頁/共237頁第一百四十二頁，編輯于星期二：十一點 六分。圖圖10.4.1010.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第142頁/共237頁第一百四十三頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第143頁/共237頁第一百四十四頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第144頁/共237頁第一百四十五頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉

30、圖與哈密爾頓圖第145頁/共237頁第一百四十六頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第146頁/共237頁第一百四十七頁，編輯于星期二：十一點 六分。圖圖10.4.1110.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第147頁/共237頁第一百四十八頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第148頁/共237頁第一百四十九頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第149頁/共237頁第一百五十頁，編輯于星期二：十一點 六分。圖圖 10.4.1210.4 歐拉圖與哈密爾頓圖歐拉圖與

31、哈密爾頓圖第150頁/共237頁第一百五十一頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第151頁/共237頁第一百五十二頁，編輯于星期二：十一點 六分。10.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第152頁/共237頁第一百五十三頁，編輯于星期二：十一點 六分。 圖 10.4.1310.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖第153頁/共237頁第一百五十四頁，編輯于星期二：十一點 六分。第154頁/共237頁第一百五十五頁，編輯于星期二：十一點 六分。第155頁/共237頁第一百五十六頁，編輯于星期二：十一點 六分。第156頁/共237頁第一百五十七頁

32、，編輯于星期二：十一點 六分。圖圖 10.5.1第157頁/共237頁第一百五十八頁，編輯于星期二：十一點 六分。第158頁/共237頁第一百五十九頁，編輯于星期二：十一點 六分。 圖圖 10.5.2 平面圖示例平面圖示例 第159頁/共237頁第一百六十頁，編輯于星期二：十一點 六分。第160頁/共237頁第一百六十一頁，編輯于星期二：十一點 六分。第161頁/共237頁第一百六十二頁，編輯于星期二：十一點 六分。第162頁/共237頁第一百六十三頁，編輯于星期二：十一點 六分。第163頁/共237頁第一百六十四頁，編輯于星期二：十一點 六分。圖圖 10.5.3 有限面和無限面示例有限面和無

33、限面示例 第164頁/共237頁第一百六十五頁，編輯于星期二：十一點 六分。第165頁/共237頁第一百六十六頁，編輯于星期二：十一點 六分。31deg( )16iir1deg()2riiRm第166頁/共237頁第一百六十七頁，編輯于星期二：十一點 六分。第167頁/共237頁第一百六十八頁，編輯于星期二：十一點 六分。第168頁/共237頁第一百六十九頁，編輯于星期二：十一點 六分。第169頁/共237頁第一百七十頁，編輯于星期二：十一點 六分。第170頁/共237頁第一百七十一頁，編輯于星期二：十一點 六分。1deg()3kiiRk 由定理由定理10.5.4知，知，2m3k，即，即23k

34、m第171頁/共237頁第一百七十二頁，編輯于星期二：十一點 六分。22312336nmknmmnmmn即即 整理得整理得 代入歐拉公式有代入歐拉公式有第172頁/共237頁第一百七十三頁，編輯于星期二：十一點 六分。第173頁/共237頁第一百七十四頁，編輯于星期二：十一點 六分。圖圖 10.5.4 圖圖K5 第174頁/共237頁第一百七十五頁，編輯于星期二：十一點 六分。1deg()4kiiRk第175頁/共237頁第一百七十六頁，編輯于星期二：十一點 六分。22mnmknm整理得整理得 m2n4 .所以所以2m4k， 即即 ， 代入歐拉公式有代入歐拉公式有2mk 第176頁/共237頁

35、第一百七十七頁，編輯于星期二：十一點 六分。第177頁/共237頁第一百七十八頁，編輯于星期二：十一點 六分。圖圖 10.5.1第178頁/共237頁第一百七十九頁，編輯于星期二：十一點 六分。第179頁/共237頁第一百八十頁，編輯于星期二：十一點 六分。 圖圖 10.5.5 同胚圖同胚圖 第180頁/共237頁第一百八十一頁，編輯于星期二：十一點 六分。 圖圖 10.5.6 示例圖示例圖G 第181頁/共237頁第一百八十二頁，編輯于星期二：十一點 六分。第182頁/共237頁第一百八十三頁，編輯于星期二：十一點 六分。第183頁/共237頁第一百八十四頁，編輯于星期二：十一點 六分。第1

36、84頁/共237頁第一百八十五頁，編輯于星期二：十一點 六分。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第185頁/共237頁第一百八十六頁，編輯于星期二：十一點 六分。圖圖 10.6.1 樹和森林示意圖樹和森林示意圖 10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第186頁/共237頁第一百八十七頁，編輯于星期二：十一點 六分。圖圖 10.6.210.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第187頁/共237頁第一百八十八頁，編輯于星期二：十一點 六分。1deg()22(1)22

37、niimnn若若T中的無樹葉，中的無樹葉， 則則T中每個頂點的度數(shù)中每個頂點的度數(shù)2,則則 deg(vi)2n, （2）(1) 定理定理10.6.1 任一樹任一樹T中中,至少有兩片樹葉至少有兩片樹葉(n2時時)。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第188頁/共237頁第一百八十九頁，編輯于星期二：十一點 六分。若若T中只有一片樹葉，則中只有一片樹葉，則T中只有一個結(jié)點度數(shù)為中只有一個結(jié)點度數(shù)為1,其其它結(jié)點度數(shù)它結(jié)點度數(shù)2, 所以所以 1deg()2(1)22niinn(3) (2),(3)都與都與(1)矛盾。所以矛盾。所以T中至少有兩片樹葉。中

38、至少有兩片樹葉。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第189頁/共237頁第一百九十頁，編輯于星期二：十一點 六分。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第190頁/共237頁第一百九十一頁，編輯于星期二：十一點 六分。k由歸納假設(shè)它有由歸納假設(shè)它有k-1條邊。再條邊。再將頂點將頂點v及其關(guān)聯(lián)邊加回得到及其關(guān)聯(lián)邊加回得到原圖原圖T,所以所以T中含有中含有k+1個頂個頂點和點和k條邊條邊,符合公式符合公式m=n-1。n所以樹是無圈且所以樹是無圈且m=n-1的圖。的圖。10.6 樹與生成樹樹與生成樹(Tree

39、s and Spanning Trees)第191頁/共237頁第一百九十二頁，編輯于星期二：十一點 六分。11,kkiiiinnmm于是于是11(1)1kkiiiimmnnkn得出矛盾。所以得出矛盾。所以T是連通且是連通且m=n-1的圖。的圖。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第192頁/共237頁第一百九十三頁，編輯于星期二：十一點 六分。無圈無圈,再加回再加回v及其關(guān)聯(lián)邊又得到及其關(guān)聯(lián)邊又得到圖圖T,則則T也無圈。也無圈。n其次其次,若在連通圖若在連通圖T中增加一中增加一條新邊條新邊(vi, vj ),則由于則由于T中由中由vi到到vj存在

40、一條通路存在一條通路,故必有一個圈通故必有一個圈通過過vi, vj 。若這樣的圈有兩個，則。若這樣的圈有兩個，則去掉去掉(vi, vj ), T中必存在通過中必存在通過vi, vj的圈，與的圈，與T無圈矛盾。故加上邊無圈矛盾。故加上邊(vi, vj )得到一個切僅一個圈。得到一個切僅一個圈。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第193頁/共237頁第一百九十四頁，編輯于星期二：十一點 六分。n,一條路徑一條路徑,于是有一條通路。若于是有一條通路。若此通路不唯一此通路不唯一,則則T中含有簡單中含有簡單回路回路,刪去此回路上任一邊刪去此回路上任一邊,圖

41、仍圖仍連通連通,這與假設(shè)不符這與假設(shè)不符,所以通路是所以通路是唯一的。唯一的。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第194頁/共237頁第一百九十五頁，編輯于星期二：十一點 六分。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第195頁/共237頁第一百九十六頁，編輯于星期二：十一點 六分。n得得2 （5+x）=22+31+43+xn所以所以x=9，即樹，即樹T有有9片片樹葉。樹葉。niivm1)deg(210.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第196頁/共237頁第一

42、百九十七頁，編輯于星期二：十一點 六分。第197頁/共237頁第一百九十八頁，編輯于星期二：十一點 六分。 圖圖 10.6.3考慮生成樹考慮生成樹T1，可知，可知e1，e2，e3，e4是是T1的樹枝，的樹枝，e5，e6，e7是是T1的弦，集合的弦，集合e5，e6，e7是是T1的補的補。生成樹有其一定的實際意義。生成樹有其一定的實際意義。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第198頁/共237頁第一百九十九頁，編輯于星期二：十一點 六分。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第199頁/共237頁第二百頁，

43、編輯于星期二：十一點 六分。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第200頁/共237頁第二百零一頁，編輯于星期二：十一點 六分。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第201頁/共237頁第二百零二頁，編輯于星期二：十一點 六分。10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第202頁/共237頁第二百零三頁，編輯于星期二：十一點 六分。 圖 10.6.410.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第203頁/共237頁第二百零四頁

44、，編輯于星期二：十一點 六分。圖 10.6.510.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第204頁/共237頁第二百零五頁，編輯于星期二：十一點 六分。圖圖10.6.610.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第205頁/共237頁第二百零六頁，編輯于星期二：十一點 六分。 10.6 樹與生成樹樹與生成樹(Trees and Spanning Trees)第206頁/共237頁第二百零七頁，編輯于星期二：十一點 六分。第207頁/共237頁第二百零八頁，編輯于星期二：十一點 六分。圖圖 10.7.1第208頁/共237頁第二百零九頁，編輯于星期二：十一點 六分。第209頁/共237頁第二百一十頁，編輯于星期二：十一點 六分。