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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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