1、第第7章章 圖圖 論論習題課習題課離離 散散 數數 學學河南工業大學信息科學與工程學院信息科學與工程學院復復 習習 時時 注注 意意n準確掌握每個概念準確掌握每個概念n靈活應用所學定理靈活應用所學定理n注意解題思路清晰注意解題思路清晰n證明問題時，先用反向思維證明問題時，先用反向思維(從結論入手從結論入手)分析問分析問題，再按正向思維寫出證明過程。題，再按正向思維寫出證明過程。 圖圖 通路與回路通路與回路 圖的連通性圖的連通性 歐拉圖歐拉圖 漢密爾頓圖漢密爾頓圖 無向樹及其性質無向樹及其性質 平面圖的基本性質平面圖的基本性質 歐拉公式歐拉公式 平面圖的對偶圖平面圖的對偶圖 地圖著色與平地圖著色

2、與平面圖著色面圖著色 平面圖的判斷平面圖的判斷 圖的矩陣表示圖的矩陣表示 無向樹及其性質無向樹及其性質 根樹及其應用根樹及其應用 無向樹及其性質無向樹及其性質圖論的結構圖一、無向圖與有向圖n1、基本概念。、基本概念。n有向圖與無向圖的定義；有向邊有向圖與無向圖的定義；有向邊,無向邊無向邊,平行邊平行邊,環環, 孤立結點孤立結點n關聯與鄰接關聯與鄰接(相鄰相鄰)；n結點的度數；結點的度結點的度數；結點的度, 結點的出度結點的出度, 結點的入結點的入度度, 圖的最大度圖的最大度(G),最小度最小度(G),n零圖與平凡圖；簡單圖與多重圖；零圖與平凡圖；簡單圖與多重圖；n完全圖；子圖，生成子圖，補圖；

3、圖的同構。完全圖；子圖，生成子圖，補圖；圖的同構。n2、運用。、運用。n(1) 靈活運用握手定理及其推論，靈活運用握手定理及其推論，n(2) 判斷兩個圖是否同構，判斷兩個圖是否同構，n(3) 畫出滿足某些條件的子圖，補圖等。畫出滿足某些條件的子圖，補圖等。二、通路、回路、圖的連通性n1、基本概念、基本概念n路，回路，跡，路，回路，跡， 通路，圈通路，圈n無向圖和有向圖中結點之間的可達關系；連通無向圖和有向圖中結點之間的可達關系；連通圖，連通分支，連通分支數圖，連通分支，連通分支數W(G)n點割集，割點，點連通度點割集，割點，點連通度k(G)n邊割集，割邊邊割集，割邊(橋橋)，邊連通度，邊連通度

4、(G)n短程線，距離短程線，距離n有向圖連通的分類，強連通，單側連通，弱連有向圖連通的分類，強連通，單側連通，弱連通，通， 強分圖，單側分圖，弱分圖強分圖，單側分圖，弱分圖 2、運用、運用n(1) 判斷有向圖或無向圖中通路判斷有向圖或無向圖中通路(回路回路)的類型。的類型。n(2) 求短程線和距離。求短程線和距離。n(3) 判斷有向圖連通的類型。判斷有向圖連通的類型。三、圖的矩陣表示n1、基本概念。、基本概念。n無向圖的無向圖的鄰接矩陣鄰接矩陣An根據鄰接矩陣判斷根據鄰接矩陣判斷:各結點的度各結點的度, 有向圖結點有向圖結點出出,入度。入度。n由由Ak可以求一個結點到另一個結點長度為可以求一個

5、結點到另一個結點長度為k的路條數的路條數.n有向圖的有向圖的可達矩陣可達矩陣Pn用用P可以判定可以判定:各結點的度各結點的度. 有向圖的強分圖。有向圖的強分圖。n關聯矩陣關聯矩陣M:是結點與邊的關聯關系矩陣是結點與邊的關聯關系矩陣. 用用M判定判定:各結點的度各結點的度重要定理：重要定理：握手定理及其推論握手定理及其推論n推論推論 ： 任何圖任何圖(無向的或有向的無向的或有向的)中，奇度結點的中，奇度結點的個數是偶數。個數是偶數。無向圖：無向圖：有向圖：有向圖：且且( , ),( , ),( , ),( , )Ea bb cc da e(1)( , ),( , ),( , ),( , ),(

6、, )Ea bb ee ba ed e(2)( , ),( , ),( , ),( , )Ea bb ee dc c(3)多重圖不是典型題典型題設圖設圖G=，其中，其中V=a,b,c,d,e，E分別由下面給分別由下面給出。判斷哪些是簡單圖，哪些是多重圖？出。判斷哪些是簡單圖，哪些是多重圖？簡單圖下列各序列中，可以構成無向簡單圖的度數序列的下列各序列中，可以構成無向簡單圖的度數序列的有哪些？有哪些？(1) (2,2,2,2,2) 可以可以(2)(1,1,2,2,3) 不可以不可以(3)(1,1,2,2,2) 可以可以(4)(0,1,3,3,3) 不可以不可以(5)(1,3,4,4,5) 不可以不

7、可以圖圖G如右圖所示，以下說法正確的是如右圖所示，以下說法正確的是 ( ) A(a, d)是割邊是割邊B(a, d)是邊割集是邊割集C(d, e)是邊割集是邊割集D(a, d) ,(a, c)是邊割集是邊割集n正確答案是：正確答案是：C。n對割邊、邊割集的概念理解到位。對割邊、邊割集的概念理解到位。n定義定義 設無向圖設無向圖G=為連通圖，若有邊集為連通圖，若有邊集E1 E，使圖使圖G刪除了刪除了E1的所有邊后，所得的子圖是不連通的所有邊后，所得的子圖是不連通圖，而刪除了圖，而刪除了E1的任何真子集后，所得的子圖是連的任何真子集后，所得的子圖是連通圖，則稱通圖，則稱E1是是G的一個邊割集若某個

8、邊構成一的一個邊割集若某個邊構成一個邊割集，則稱該邊為割邊（或橋）個邊割集，則稱該邊為割邊（或橋）n如果答案如果答案A正確，即刪除邊正確，即刪除邊(a, d)后，得到的圖是不后，得到的圖是不連通圖，但事實上它還是連通的。因此連通圖，但事實上它還是連通的。因此答案答案A是錯是錯誤的。誤的。設給定圖設給定圖G(如由圖所示如由圖所示)，則圖，則圖G的點割集的點割集是是 應該填寫：應該填寫：f，c，e。n定義定義 設無向圖設無向圖G=為連通圖，若有點集為連通圖，若有點集V1 V，使圖，使圖G刪除了刪除了V1的所有結點后，所得的子的所有結點后，所得的子圖是不連通圖，而刪除了圖是不連通圖，而刪除了V1的任

9、何真子集后，所的任何真子集后，所得的子圖是連通圖，則稱得的子圖是連通圖，則稱V1是是G的一個點割的一個點割集若某個結點構成一個點割集，則稱該結點為集若某個結點構成一個點割集，則稱該結點為割點。割點。nf，c是不滿定義的，因為是不滿定義的，因為f是是f，c的真子集，的真子集，而刪除而刪除f后，圖是不連通的。后，圖是不連通的。單向連通單向連通強連通強連通強連通強連通下圖所示的六個圖中，強連通，單向連通，弱連通下圖所示的六個圖中，強連通，單向連通，弱連通的分別有哪些？的分別有哪些？強連通強連通單向連通單向連通弱連通弱連通設圖設圖G的鄰接矩陣為的鄰接矩陣為則則G的邊數為的邊數為( )A5 B6 C3

10、D4n正確答案是：正確答案是：D。n當給定的簡單圖是無向圖時，當給定的簡單圖是無向圖時，鄰接矩陣為對稱的即當結鄰接矩陣為對稱的即當結點點vi與與vj相鄰時，結點相鄰時，結點vj與與vi也也相鄰，所以連接結點相鄰，所以連接結點vi與與vj的的一條邊在鄰接矩陣的第一條邊在鄰接矩陣的第i行第行第j列處和第列處和第j行第行第i列處各有一個列處各有一個1，題中給出的鄰接矩陣中共，題中給出的鄰接矩陣中共有有8個個1，故有，故有8 2=4條邊。度條邊。度數之和等于數之和等于2倍的邊數。倍的邊數。n(1) D是哪類連通圖是哪類連通圖?n(2) D中中v1到到v4長度為長度為1,2,3,4的通路各多的通路各多少

11、條？少條？n(3) D中長度為中長度為4的通路（不含回路）有的通路（不含回路）有多少條？多少條？n(4)D中長度為中長度為4的回路有多少條？的回路有多少條？n(5) D中長度中長度4的通路有多少條？其中的通路有多少條？其中有幾條是回路？有幾條是回路？n(6) 寫出寫出D的可達矩陣。的可達矩陣。有向圖有向圖D如圖所示，回答下列問題：如圖所示，回答下列問題：有向圖有向圖D如圖所示，回答下列諸問：如圖所示，回答下列諸問：n(1) D是哪類連通圖是哪類連通圖?nD是強連通圖。是強連通圖。n解答為解解答為解(2)(6)，只需先求，只需先求D的鄰的鄰接矩陣的前接矩陣的前4次冪。次冪。 1222234412

12、222465012112220121222310010121100102210100100101000021432AAAAn(2) D中中v1到到v1長度為長度為1,2,3,4的回路各多少條？的回路各多少條？n答：答： v1到到v1長度為長度為1,2,3,4的回路數分別為的回路數分別為1,1,3,5。n(3) D中長度為中長度為4的通路（不含回路）有多少條？的通路（不含回路）有多少條？n答：長度為答：長度為4的通路的通路(不含回路不含回路)為為33條條.n(4) D中長度為中長度為4的回路有多少條？的回路有多少條？n答：答： 長度為長度為4的回路為的回路為11條。條。n(5) D中長度中長度

13、4的通路有多少條？其中有幾條是回路？的通路有多少條？其中有幾條是回路？n答：長度答：長度 4的通路的通路88條，其中條，其中22條為回路。條為回路。n(6) 寫出寫出D的可達矩陣。的可達矩陣。n4 4的全的全1矩陣。矩陣。簡單無向圖簡單無向圖 G 必有必有2結點同度數。結點同度數。證證: 令令 G=v1,vn，n若若 G 中中沒有孤立點沒有孤立點,則則 G 中中 n個結點的度只取個結點的度只取 n-1 個個可能值：可能值：1,2,n-1，從而，從而 G 中至少有兩個結點的度中至少有兩個結點的度數相同。數相同。n否則否則，G中有孤立點，不妨設中有孤立點，不妨設 vk,vn為全部孤立點為全部孤立點

14、,則則 v1,vk-1的度只取的度只取 k-2個可能值個可能值: 1,2,k-2，從而，從而此此 k-1個結點中至少有兩個同度數點。個結點中至少有兩個同度數點。握手定理及其推論的應用握手定理及其推論的應用n設無向圖設無向圖G有有10條邊，條邊，3度與度與4度結點各度結點各2個，其余個，其余結點的度數均小于結點的度數均小于3，問，問G中至少有幾個結點？在中至少有幾個結點？在最少結點的情況下，寫出最少結點的情況下，寫出G的度數列的度數列(G)、(G)。 n設設G的階數為的階數為n，4個結點的度數分別為個結點的度數分別為3，3，4，4,其余其余n-4個結點的度數均小于或等于個結點的度數均小于或等于2

15、，由握手定理，由握手定理可得可得n2(3+4)+(n-4)2=14+2n-8 deg(vi) = 2m=20n解此不等式可得解此不等式可得n7，即，即G中至少有中至少有7個結點，個結點，7個結點時，其度數列為個結點時，其度數列為2,2,2,3,3,4,4，=4,=2。 (1)設設n階圖階圖G中有中有m條邊，證明：條邊，證明：(G)2m/n(G)(2)n階非連通的簡單圖的邊數最多可為多少？最少呢？階非連通的簡單圖的邊數最多可為多少？最少呢？ n(1)證明中關鍵步驟是握手定理：證明中關鍵步驟是握手定理：2m=deg(vi) (G)deg(vi)(G)，于是得，于是得n n(G)2mn(G) (G)

16、2m/n(G)n易知易知2m/n為為G的平均度數，因而它大于或等于的平均度數，因而它大于或等于最小度最小度(G)，小于或等于最大度，小于或等于最大度(G)。n(2) n階非連通的簡單圖的邊數最多可為階非連通的簡單圖的邊數最多可為n-1階連通圖階連通圖加上一個孤立點，所以邊數為加上一個孤立點，所以邊數為(n-1)(n-2)/2，最少為，最少為0。 一個圖如果同構于它的補圖，則該圖稱為自補圖。一個圖如果同構于它的補圖，則該圖稱為自補圖。1)一個圖是自補圖，其對應的完全圖的邊數必為偶數一個圖是自補圖，其對應的完全圖的邊數必為偶數2)證明：若證明：若n階無向簡單圖是自補圖，則階無向簡單圖是自補圖，則n

17、=4k或或n=4k+1（k為正整數）。為正整數）。解：解： n1)設圖設圖G 是自補圖，是自補圖，G 有有 e 條邊，條邊，G 對應的完全圖的對應的完全圖的邊數為邊數為 A。G 的補圖的補圖 G的邊數應為的邊數應為 A 一一 e。因為。因為 GG， 故邊數相等，故邊數相等，e=A 一一 e，A2e，因此，因此 G 對對應的完全圖的邊數應的完全圖的邊數 A 為偶數。為偶數。n2)由由 1)可知，自補圖對應的完全圖的邊數為偶數?？芍?，自補圖對應的完全圖的邊數為偶數。n 個結點的完全圖個結點的完全圖 Kn 的邊數為的邊數為n(n-1)/2 ， 所以所以 n(n-1)/2=2m ，即，即n(n-1)=

18、4m，因而，因而nn為為4的倍數，即的倍數，即n=4k，n或或n-1為為4的倍數，即的倍數，即n=4k+1，n即即n=0,1 (mod 4)。對于任何一個具有對于任何一個具有6個結點的簡單圖，要么它包含個結點的簡單圖，要么它包含一個三角形，要么它的補圖包含一個三角形。一個三角形，要么它的補圖包含一個三角形。 解：解：n設設6個結點的簡單圖為個結點的簡單圖為G。考察?？疾霨中的任意一個結點中的任意一個結點a， 那么，另外那么，另外6個結點中的任何一個結點，要么在個結點中的任何一個結點，要么在G中與中與a鄰接，要么在鄰接，要么在G的補圖的補圖G中與中與a鄰接。這樣，鄰接。這樣，就可把就可把5個結點

19、分成兩類，將那些在個結點分成兩類，將那些在G中與中與a鄰接的鄰接的結點歸成一類，而將那些在結點歸成一類，而將那些在G中與中與a鄰接的結點歸鄰接的結點歸在另一類。于是必有一類至少含有三個結點，不妨在另一類。于是必有一類至少含有三個結點，不妨假設其中的三個結點為假設其中的三個結點為b，c，d，如圖所示。若邊，如圖所示。若邊(b，c)，(c，d)，(b，d)中有一條在中有一條在G中，那么這條邊所中，那么這條邊所關聯的兩個結點都與關聯的兩個結點都與a鄰接形成一個三角形；若邊鄰接形成一個三角形；若邊(b，c)，(c，d)，(b, d)都不在都不在G中，則中，則(b，c)，(c，d)，(b, d)形成一個

20、三角形。形成一個三角形。abcdbcdbcdbcd推論推論:任何任何6人的人群中，或者有人的人群中，或者有3人互相認識，或者有人互相認識，或者有3人彼此陌生。人彼此陌生。(當二人當二人x,y互相認識，邊互相認識，邊(x,y)著紅色，著紅色，否則著蘭色。則否則著蘭色。則6人認識情況對應于人認識情況對應于K6邊有紅邊有紅K3或者或者有蘭有蘭K3。)aaa證明簡單圖的最大度小于結點數。證明簡單圖的最大度小于結點數。證明：證明： n設簡單圖設簡單圖G有有n個結點。對任一結點個結點。對任一結點u，由于，由于G沒沒有環和平行邊，有環和平行邊，u至多與其余至多與其余n-1個結點中每一個個結點中每一個有一條邊

21、相連接，即有一條邊相連接，即deg(u)n-1，因此，因此， (G) maxdeg(u)n-1。 設設G是一個是一個n階無向簡單圖，階無向簡單圖，n是大于等于是大于等于3的的奇數。證明圖奇數。證明圖G與它的補圖中度數為奇數的結與它的補圖中度數為奇數的結點個數相等。點個數相等。證明：證明：n因為因為G是是n階無向簡單圖，且階無向簡單圖，且n是大于等于是大于等于3的奇數，的奇數，故無向圖的結點數為奇數，則所對應的故無向圖的結點數為奇數，則所對應的n階完全階完全圖中每個結點的度數為圖中每個結點的度數為n-1即為偶數，即為偶數，n利用奇數利用奇數+奇數奇數=偶數，偶數偶數，偶數+偶數偶數=偶數，所以，

22、偶數，所以，在在G中結點度數為奇數的結點，在其補圖中的度中結點度數為奇數的結點，在其補圖中的度數也應為奇數，故數也應為奇數，故G和其補圖的奇數結點個數也和其補圖的奇數結點個數也是相同的。是相同的。P2861、在無向圖、在無向圖G中，從結點中，從結點u到結點到結點v有一條長度為有一條長度為偶數的通路，從結點偶數的通路，從結點u到結點到結點v又有一條長度為奇又有一條長度為奇數的通路，則在數的通路，則在G中必有一條長度為奇數的回路。中必有一條長度為奇數的回路。證明證明 ：n設從結點設從結點u到結點到結點v長度為偶數的通路是長度為偶數的通路是ue1u1e2u2e2kv，n長度為奇數的通路是長度為奇數的

23、通路是ue11u11e12u12e12h-1v，n那么路那么路ue1u1e2u2e2kve12h-1u12e12u11e11u就是一條回就是一條回路，它的邊數路，它的邊數2k+(2h-1)2(h+k)-1，是奇數，故，是奇數，故這條回路的長度是奇數。這條回路的長度是奇數。 P286 2、無向圖、無向圖 G恰有的恰有的2個奇數度數的結點可個奇數度數的結點可達。達。解解1：令令u,w為為G恰有的恰有的2個奇度結點?？疾靷€奇度結點?？疾靧所在的連通所在的連通分支分支G。因圖。因圖G的奇度點為偶數，故的奇度點為偶數，故G至少還有另至少還有另一奇度點一奇度點w，但，但v在在G和和G中有相同的度，所以中有

24、相同的度，所以G恰恰有有2個奇度點而且就是個奇度點而且就是u和和w。再由。再由G的連通性推出的連通性推出u到到w可達?？蛇_。解解2：反證法反證法n設設G中的兩個奇度結點為中的兩個奇度結點為u與與v，若，若u與與v不連通，即不連通，即它們之間無路，因而它們之間無路，因而u與與v處于處于G中恰有不同連通分中恰有不同連通分支中，設支中，設u在在 G1中，中，v在在G2中，中， G1與與 G2是是G的連的連通分支，由于通分支，由于G中恰有兩個奇度結點，因而當作為中恰有兩個奇度結點，因而當作為獨立的圖時，均有一個奇度結點，這與握手定理獨立的圖時，均有一個奇度結點，這與握手定理的推論相矛盾。的推論相矛盾。

25、3、若圖、若圖G是不連通的，則是不連通的，則G的補圖的補圖G是連通的。是連通的。證明：證明：n若圖若圖G是不連通的，可設圖是不連通的，可設圖G的連通分支是的連通分支是G(V1)，G(V2)，G(Vm)(m2)。由于任意兩個連通。由于任意兩個連通分支分支G(Vi)與與G(Vj)(ij)之間不連通，因此兩個結點子之間不連通，因此兩個結點子集集Vi與與Vj之間的所有連線都在圖之間的所有連線都在圖G的補圖的補圖G中。任取中。任取兩個結點兩個結點u和和v，有兩種情形：，有兩種情形： na)u和和v分別屬于兩個不同結點子集分別屬于兩個不同結點子集Vi與與Vj。由上可。由上可知知G 包含邊包含邊(u，v)，

26、故，故u和和v在在G中是連通的。中是連通的。 nb)u和和v屬于同屬于同個結點子集個結點子集Vi?？稍诹硪粋€結點子?？稍诹硪粋€結點子集集Vj中取一個結點中取一個結點w，由上可知邊，由上可知邊(u,w)及邊及邊(v,w)均均在在G 中，故鄰接邊中，故鄰接邊(u,w)和和(w,v)組成的路連接結點組成的路連接結點u和和v，即，即u和和v在在G中也是連通的。中也是連通的。 n由此可知，當圖由此可知，當圖G不是連通圖時，不是連通圖時，G必是連通圖。必是連通圖。 在具有在具有n個結點的個結點的無向簡單圖無向簡單圖G中中，若任意若任意2 個個不同結點的度數之和大于等于不同結點的度數之和大于等于n - 1

27、，則圖，則圖G是是連通圖。連通圖。證明：證明：反證法反證法n設圖設圖G不是連通圖，不妨設圖不是連通圖，不妨設圖G有有2 個連通分支個連通分支G1 和和G2，其中，其中G1有有k ( k 1) 個結點，個結點，G2有有n - k個結個結點。在點。在G1中任取一點中任取一點vi，G2中任取一點中任取一點vj ，則，則:ndeg ( vi ) k - 1 ndeg ( vj ) ( n - k) - 1n由此可得由此可得:ndeg ( vi ) + deg ( vj ) ( k - 1) + ( n - k) - 1 = n - 2 與題設矛盾，故圖與題設矛盾，故圖G是連通圖。是連通圖。證明證明n個

28、結點個結點k條邊的簡單圖條邊的簡單圖G，若，若k (n-1)(n-2)/2，則圖，則圖G是連通圖。是連通圖。 證明：證明：反證法反證法設設G的補圖為的補圖為G，邊數記為，邊數記為kG，則則kG+ kG =n(n-1)/2，假設假設G不連通，則不連通，則G的補圖是連通，的補圖是連通， kG n-1 kG+ kG kG+n-1， 利用利用kG+ kG =n(n-1)/2；推出推出kG (n-1)(n-2)/2， 和題設矛盾；和題設矛盾； 故圖故圖 G 是連通圖。是連通圖。n（渡河問題）（渡河問題） 一個擺渡人，一個擺渡人， 要把一只狼、要把一只狼、 一只羊和一捆干一只羊和一捆干草運過河去，草運過河

29、去， 河上有一只木船，河上有一只木船， 每次除了人以外，每次除了人以外， 只能帶只能帶一樣東西。一樣東西。 另外，另外， 如果人不在旁時，如果人不在旁時， 狼就要吃羊，狼就要吃羊， 羊就要羊就要吃干草。吃干草。 問這人怎樣才能把它們運過河去？問這人怎樣才能把它們運過河去？解解: 用用F表示擺渡人，表示擺渡人， W表示狼，表示狼， S表示羊，表示羊， H表示干草。表示干草。 n 若用若用FWSH表示人和其它表示人和其它3樣東西在河的左岸的狀態。這樣樣東西在河的左岸的狀態。這樣在左岸全部可能出現的狀態為以下在左岸全部可能出現的狀態為以下16種：種： n FWSH FWS FWH FSHn WSH

30、FW FS FHn WS WH SH Fn W S H n 這里這里表示左岸是空集，表示左岸是空集， 即人、即人、 狼、狼、 羊、羊、 干草都已運到右干草都已運到右岸去了。岸去了。 利用通路的概念解決一個古老的著名問題。利用通路的概念解決一個古老的著名問題。n根據題意檢查一下就可以知道，根據題意檢查一下就可以知道， nFWSH FWS FWH FSH WSH FW n FS FH WS WH SH F W S H n這這16種情況中有種情況中有6種情況是不允許出現的。種情況是不允許出現的。 n它們是：它們是： WSH、 FW、 FH、 WS、 SH、 F。 如如FH表示人和干草在左岸，表示人和

31、干草在左岸， 而狼和羊在右岸，而狼和羊在右岸， 這當這當然是不行的。然是不行的。 因此，因此， 允許出現的情況只有允許出現的情況只有10種。種。 n我們構造一個圖，我們構造一個圖， 它的結點就是這它的結點就是這10種狀態。種狀態。 若一若一種狀態可以轉移到另一種狀態，種狀態可以轉移到另一種狀態， 就在表示它們的兩就在表示它們的兩結點間連一條邊，結點間連一條邊， 這樣就畫出圖。這樣就畫出圖。 本題就轉化為找本題就轉化為找結點結點FWSH到結點到結點的通路。的通路。 從圖中得到兩條這樣從圖中得到兩條這樣的通路，的通路， 即有兩種渡河方案。即有兩種渡河方案。FWSH WHFWHHWFSHFSWSFS

32、歐拉路，歐拉回路，歐拉圖。歐拉路，歐拉回路，歐拉圖。判定判定:n有歐拉路的充要條件：有歐拉路的充要條件：無或有兩個奇數度的結無或有兩個奇數度的結點。點。n有歐拉回路的充要條件：有歐拉回路的充要條件：所有結點度數均為偶所有結點度數均為偶數。數。漢密爾頓路，漢密爾頓回路，漢密爾頓圖漢密爾頓路，漢密爾頓回路，漢密爾頓圖漢密爾頓圖的判定漢密爾頓圖的判定:n必要條件：設無向圖必要條件：設無向圖G=是漢密爾頓圖，是漢密爾頓圖，則對于任意非空子集則對于任意非空子集S，有，有W(G-S)|S|。n推論推論 設無向圖設無向圖G=是半漢密爾頓圖，則對是半漢密爾頓圖，則對于任意非空子集于任意非空子集S，有，有W(G

33、-S)|S|+1。n充分條件：若簡單圖充分條件：若簡單圖G中每對結點的度數和中每對結點的度數和|V| =n，則，則G是漢密爾頓圖。是漢密爾頓圖。n半漢密爾頓圖，若簡單圖半漢密爾頓圖，若簡單圖G中每對結點的度數和中每對結點的度數和|V| -1，則，則G是半漢密爾頓圖。是半漢密爾頓圖。四、歐拉圖與漢密爾頓圖四、歐拉圖與漢密爾頓圖( (會判定會判定) )P311 2試構造一個歐拉圖，其結點數試構造一個歐拉圖，其結點數 v 和邊數和邊數 e 滿足下滿足下述條件述條件 (1) v 和和 e 的奇偶性相同；的奇偶性相同；(2) v 和和 e 的奇偶性相反。的奇偶性相反。n解：解：(1)(2)說明：歐拉圖中

34、，結點數和邊數的奇偶性說明：歐拉圖中，結點數和邊數的奇偶性既可以相同也可以相反。既可以相同也可以相反。 nn個結點的有向完全圖，哪些是有向歐拉圖，為什么？個結點的有向完全圖，哪些是有向歐拉圖，為什么？解：解： nn個結點的有向完全圖是有向歐拉圖，對于個結點的有向完全圖是有向歐拉圖，對于n個結點個結點的有向完全圖，每個結點的度數均相等，都是偶數的有向完全圖，每個結點的度數均相等，都是偶數2(n-1)，且每個結點的入度，且每個結點的入度=出度，所以出度，所以n個結點的個結點的有向完全圖是有向歐拉圖。有向完全圖是有向歐拉圖。n無向完全圖無向完全圖Kn是幾筆畫圖？為什么？是幾筆畫圖？為什么？n(1)當

35、當n=1時，時， Kn為平凡圖；為平凡圖；n(2)當當n=奇數時，奇數時， Kn中每個結點度數中每個結點度數=n-1為偶數，為偶數，所以所以Kn 為歐拉圖，可以一筆畫出；為歐拉圖，可以一筆畫出；n(3)當當n=偶數時，偶數時， Kn中每個結點度數中每個結點度數=n-1為奇數，為奇數，對應的有對應的有n/2對奇數度結點，因此可以對奇數度結點，因此可以n/2筆畫出。筆畫出。n刪除刪除A和和B后，形成后，形成3個連通分支，個連通分支，n即即W(G-S)=3|S|=2因此，圖因此，圖G不是漢密爾頓圖。不是漢密爾頓圖。圖圖G是否是漢密爾頓圖。是否是漢密爾頓圖。AB7位客人入席，位客人入席，A只會講英語，

36、只會講英語，B會講英，漢語，會講英，漢語，C會講英，意大利，俄語，會講英，意大利，俄語，D會講日，漢語，會講日，漢語，E會講德，意大利語，會講德，意大利語，F會講法，日，俄語，會講法，日，俄語，G會講法，德語。能否安排圓桌席位使每位客人與會講法，德語。能否安排圓桌席位使每位客人與其左右鄰不用翻譯便可交談其左右鄰不用翻譯便可交談?解：解：建立無向圖模型建立無向圖模型:結點為客人；結點為客人；會共同語言的會共同語言的2結點相鄰接。結點相鄰接。則問題則問題歸結為歸結為求此圖的一條求此圖的一條漢密爾頓回路漢密爾頓回路。不難驗證，此圖有一條漢密爾頓不難驗證，此圖有一條漢密爾頓回路是回路是:(A,B,D,

37、F,G,E,C,A)。按此回路安排席位可按此回路安排席位可以以使得每個人都可以和它兩邊的人直接交談使得每個人都可以和它兩邊的人直接交談。漢密爾頓圖漢密爾頓圖的應用的應用BCDEFGA英英英英法法德德俄俄意意日日漢漢某地有某地有5個風景點，若每個風景點均有個風景點，若每個風景點均有2條道路與其條道路與其他點相通。問游人可否經過每個風景點恰好一次而他點相通。問游人可否經過每個風景點恰好一次而游完這游完這5處？處？解：解：n 將將5個風景點看成是有個風景點看成是有5個結點的無向圖，兩風景個結點的無向圖，兩風景點間的道路看成是無向圖的邊點間的道路看成是無向圖的邊，n因為每處均有兩條道路與其他結點相通，

38、故每個因為每處均有兩條道路與其他結點相通，故每個結點的度數均為結點的度數均為2，n從而任意兩個不相鄰的結點的度數之和等于從而任意兩個不相鄰的結點的度數之和等于4，正，正好為總結點數減好為總結點數減1。n故此圖中存在一條故此圖中存在一條漢密爾頓路漢密爾頓路，因此游人可以經，因此游人可以經過每個風景點恰好一次而游完這過每個風景點恰好一次而游完這5處。處。設圖設圖G 有有n 個結點，個結點，e 條邊，證明：若條邊，證明：若 ，則則G 為漢密爾頓圖。為漢密爾頓圖。證明：證明：反證法反證法n假設假設G 不是漢密爾頓圖，則根據漢密爾頓圖的判定不是漢密爾頓圖，則根據漢密爾頓圖的判定定理，知至少存在兩個結點的

39、度數之和小于定理，知至少存在兩個結點的度數之和小于n，則，則該兩個結點所關聯的邊的數目該兩個結點所關聯的邊的數目m1 小于小于n，即，即m1n-1，而當其余而當其余n-2 個結點構成完全圖時，其所關聯的邊個結點構成完全圖時，其所關聯的邊數目數目m2 為最大值，即為最大值，即m2(n-2)(n-3)/2。nG 的總的邊數為的總的邊數為m1+m2，從而，從而n與題設與題設 矛盾。矛盾。n所以，圖所以，圖G 為漢密爾頓圖。為漢密爾頓圖。將將6 個人分成個人分成3 組（每組組（每組2 個人）去完成個人）去完成3 項任務。已項任務。已知每個人至少與其余知每個人至少與其余5 個人中的個人中的3 個人能互相

40、合作。問：個人能互相合作。問：能否使得每組的能否使得每組的2 個人都能相互合作？請說明理由。個人都能相互合作？請說明理由。解：解：n用用v1,v2,v6 代表代表6 個人，若個人，若vi,vj 能相互合作，就能相互合作，就在在vi 與與vj 之間連無向邊，得無向圖之間連無向邊，得無向圖G=(V,E)。n由已知條件可知，對于任意的由已知條件可知，對于任意的viV, deg(vi)n/2，因此因此deg(vi)+deg(vj)n，由定理可知，由定理可知G 是漢密爾頓是漢密爾頓圖，圖，n因而因而G 中存在漢密爾頓回路，不妨設中存在漢密爾頓回路，不妨設C=vi1vi2vi3vi4vi5vi6vi1 為

41、其中一條，在這種回路上相為其中一條，在這種回路上相鄰兩個結點代表的二人能相互合作。鄰兩個結點代表的二人能相互合作。某工廠生產由某工廠生產由6 種不同顏色的紗織成的雙色布，已知在種不同顏色的紗織成的雙色布，已知在品種中，每種顏色至少分別和其他品種中，每種顏色至少分別和其他5 種顏色中的種顏色中的3 種顏種顏色搭配，證明可以挑出色搭配，證明可以挑出3 種雙色布，它們恰有種雙色布，它們恰有6 種不同種不同的顏色。的顏色。解：解：n用用vi 表示顏色表示顏色(i=1,26)，作無向圖，作無向圖G(V,E)，其中，其中V=v1,v2,v6，E=(u,v)|u,vV 且且uv 并且并且u 與與v 搭配搭配

42、nu,vV, deg(u)+deg(v)6, 所以所以G 是漢密爾頓圖，是漢密爾頓圖，因而因而G 中存在漢密爾頓回路，不妨設中存在漢密爾頓回路，不妨設v1v2v3v4v5v6v1 為其中一條，在這種回路上每個結為其中一條，在這種回路上每個結點代表的顏色都能與它相鄰結點代表的顏色相搭點代表的顏色都能與它相鄰結點代表的顏色相搭配，于是讓配，于是讓v1 與與v2,v3 與與v4,v5 與與v6 搭配，織成搭配，織成3 種種雙色布，包含了雙色布，包含了6 種顏色。種顏色。 n下列命題中下列命題中( )是正確的是正確的.n1.歐拉圖的子圖一定是歐拉圖歐拉圖的子圖一定是歐拉圖n2.漢密爾頓圖的子圖一定是漢密爾頓圖漢密爾頓圖的子圖一定是漢密爾頓圖反證法在圖論