離散數(shù)學(xué)第七章第四節(jié)

1、1第7-4講 歐拉圖與漢密爾頓圖 1. 歐拉圖2. 有向圖中的歐拉路3. 周游世界問題4. 漢密爾頓圖5. 標(biāo)識(shí)法6.課堂練習(xí)7. 第7-4講 作業(yè)21、歐拉圖（1） 定義1 設(shè)圖設(shè)圖G無孤立結(jié)點(diǎn)，若存在一條路無孤立結(jié)點(diǎn)，若存在一條路(回路回路)，經(jīng)過圖中每，經(jīng)過圖中每邊一次且僅一次，則稱該路邊一次且僅一次，則稱該路(回路回路)為為歐拉路(歐拉回路) 。 具有歐拉回路的圖叫具有歐拉回路的圖叫歐拉圖例如，下圖例如，下圖具有歐拉路，而沒有歐拉回路。具有歐拉路，而沒有歐拉回路。 從圖中從圖中v2出發(fā)出發(fā)經(jīng)過圖中每邊一經(jīng)過圖中每邊一次且僅一次到次且僅一次到v3可得歐拉路：可得歐拉路： v2 v1 v3

2、 v5 v4 v2 v3 但此圖不可能有但此圖不可能有歐拉回路，因歐拉回路，因而不是歐拉圖。而不是歐拉圖。31、歐拉圖（2）定理1 無向圖G有一條歐拉路，當(dāng)且僅當(dāng)G連通，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。證：必要性。設(shè)設(shè)圖圖G G有歐拉路有歐拉路v v0 0e e1 1v v1 1e e2 2v v2 2.e.ei iv vi ie ei+1i+1.e.ek kv vk k，其，其中結(jié)點(diǎn)可重復(fù)出現(xiàn)，但邊不重復(fù)，且每條邊都經(jīng)歷一次，因此，中結(jié)點(diǎn)可重復(fù)出現(xiàn)，但邊不重復(fù)，且每條邊都經(jīng)歷一次，因此，歐拉路遍歷歐拉路遍歷G G中所有結(jié)點(diǎn)，所以中所有結(jié)點(diǎn)，所以G G是連通的。是連通的。 其次，若其次，若v vi

3、i不是端點(diǎn)，則不是端點(diǎn)，則deg(vdeg(vi i) )必為偶數(shù)；而對(duì)端點(diǎn)必為偶數(shù)；而對(duì)端點(diǎn)v v0 0和和v vk k，如果如果v v0 0=v=vk k，則，則G G中無奇數(shù)度結(jié)點(diǎn)；如果中無奇數(shù)度結(jié)點(diǎn)；如果v v0 0 v vk k，則，則deg(vdeg(v0 0) )和和deg(vdeg(vk k) )必為奇數(shù)，故必為奇數(shù)，故G G中有一對(duì)奇數(shù)度結(jié)點(diǎn)。中有一對(duì)奇數(shù)度結(jié)點(diǎn)。 充分性。當(dāng)當(dāng)G G連通，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)?？砂慈缦逻B通，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)?？砂慈缦路椒?gòu)造一條歐拉路。方法構(gòu)造一條歐拉路。 (1)(1)若若G G有兩個(gè)奇數(shù)度結(jié)點(diǎn)有兩個(gè)奇數(shù)度結(jié)點(diǎn)v v0 0和和v

4、vk k，因，因G G連通，可構(gòu)造一條跡連通，可構(gòu)造一條跡 ( (無重復(fù)邊的路無重復(fù)邊的路)L)L1 1：v v0 0e e1 1v v1 1e e2 2.v.vk k；若；若G G無奇數(shù)度結(jié)點(diǎn)，則可從無奇數(shù)度結(jié)點(diǎn)，則可從任何結(jié)點(diǎn)任何結(jié)點(diǎn)v vi i出發(fā)構(gòu)造一條閉跡出發(fā)構(gòu)造一條閉跡L L1 1：v vi ie e1 1v v1 1e e2 2.v.vi i。41、歐拉圖（3）定理1 無向圖G有一條歐拉路，當(dāng)且僅當(dāng)G連通，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。證：充分性(續(xù))。(2)(2)如果如果L L1 1遍歷遍歷G G的所有邊，則的所有邊，則L L1 1就是一條歐拉路。就是一條歐拉路。(3)(3)如果如

5、果L L1 1未遍歷未遍歷G G的所有邊，則刪除的所有邊，則刪除L L1 1的所有邊及由此產(chǎn)生的的所有邊及由此產(chǎn)生的孤立結(jié)點(diǎn)得子圖孤立結(jié)點(diǎn)得子圖G G，G G中每個(gè)結(jié)點(diǎn)的度數(shù)應(yīng)為偶數(shù)。因中每個(gè)結(jié)點(diǎn)的度數(shù)應(yīng)為偶數(shù)。因G G連通，連通，所以所以L L1 1與與G G至少有一個(gè)結(jié)點(diǎn)至少有一個(gè)結(jié)點(diǎn)v vj j重合，在重合，在G G中從結(jié)點(diǎn)中從結(jié)點(diǎn)v vj j出發(fā)可構(gòu)造出發(fā)可構(gòu)造閉跡閉跡L L2 2。(4)(4)如果如果L L1 1和和L L2 2組合在一起恰為組合在一起恰為G G，則得一條歐拉路，否則重復(fù)，則得一條歐拉路，否則重復(fù)第第3 3步，如此下去，必可得到一條經(jīng)過圖步，如此下去，必可得到一條經(jīng)過

6、圖G G所有邊的歐拉路。所有邊的歐拉路。證明過程示意圖：51、歐拉圖（4）推論 無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G連通，且所有結(jié)點(diǎn)度數(shù)皆為偶數(shù)。 由推論可知，七橋問題無解：右圖中既無歐拉回路，又無歐拉路。62、有向圖中的歐拉路 定義2 經(jīng)過有向圖中每邊一次且僅一次的單向路經(jīng)過有向圖中每邊一次且僅一次的單向路(回路回路)稱為稱為單向歐拉路(回路) 。 歐拉路可推廣到有向圖。歐拉路可推廣到有向圖。定理2 有向圖G具有一條單向歐拉回路，當(dāng)且僅當(dāng)G連通，且每個(gè)結(jié)點(diǎn)的入度等于出度。有向圖G具有一條單向歐拉路，當(dāng)且僅當(dāng)G連通，且除兩個(gè)結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的入度等于出度。而這兩個(gè)結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)的入度比出度大

7、1，另一個(gè)結(jié)點(diǎn)的入度比出度小1。（證明與定理1類似，從略）73、周游世界問題（1） 1859年，Willian Hamilton給友人的信中首先談到了關(guān)于12面體的數(shù)學(xué)游戲：將正12面體的每個(gè)頂點(diǎn)看作一個(gè)城市，兩個(gè)頂點(diǎn)間的連線視為旅行線，能否找到一條旅行線，經(jīng)過每個(gè)城市恰好一次，再回到出發(fā)地？ 按右圖中各頂點(diǎn)的數(shù)字標(biāo)定的順序給出了周游世界問題按右圖中各頂點(diǎn)的數(shù)字標(biāo)定的順序給出了周游世界問題的一個(gè)解。的一個(gè)解。83、周游世界問題（2） 周游世界問題可視為在一個(gè)平面圖中，從任一結(jié)點(diǎn)出發(fā)，找一條路，經(jīng)過每個(gè)結(jié)點(diǎn)恰好一次，再回到出發(fā)點(diǎn)？ 遺憾的是，周游世界問題不象七橋問題那樣有一個(gè)完滿遺憾的是，周游世

8、界問題不象七橋問題那樣有一個(gè)完滿的結(jié)局，判定此類問題是否有解至今還未找到一個(gè)方便的的結(jié)局，判定此類問題是否有解至今還未找到一個(gè)方便的充分必要條件。充分必要條件。94、漢密爾頓圖（1） 定義3 經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的路經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的路(回路回路) 稱為稱為漢密爾頓路(漢密爾頓回路)。具有漢密爾頓回路的圖叫。具有漢密爾頓回路的圖叫漢密爾頓圖 例如，判斷下面各圖例如，判斷下面各圖 是否為漢密爾頓圖是否為漢密爾頓圖。 圖圖(1)中有漢密爾頓路，但不存在漢密爾頓中有漢密爾頓路，但不存在漢密爾頓回回路，所以它不路，所以它不是漢密爾頓圖；圖是漢密爾頓圖；圖(2)中有漢密爾頓中有漢密爾

9、頓回回路，它是漢密爾頓圖；路，它是漢密爾頓圖；圖圖(3)中既無漢密爾頓中既無漢密爾頓回回路，也不存在漢密爾頓路。路，也不存在漢密爾頓路。104、漢密爾頓圖（2） 定理3 若無向圖無向圖G=是漢密爾頓圖，任意是漢密爾頓圖，任意S V，則，則 W(G-S) |S|其中其中W(G-S)表示表示G中刪除中刪除S后所得子圖的連通分支數(shù)。后所得子圖的連通分支數(shù)。 證明：設(shè)設(shè)c是是G中的一條中的一條漢密爾頓回路漢密爾頓回路。 (1) 如果如果S中的結(jié)點(diǎn)在中的結(jié)點(diǎn)在c上兩兩相鄰，則上兩兩相鄰，則W(c-S)=1 |S|。 (2) 如果如果S中的結(jié)點(diǎn)在中的結(jié)點(diǎn)在c上存在上存在 r (2 r |S|)個(gè)互不相鄰的

10、部分，個(gè)互不相鄰的部分，則則W(c-S)=r |S|。 一般說來，一般說來，S中的結(jié)點(diǎn)在中的結(jié)點(diǎn)在c上既有相鄰的，又有不相鄰的，上既有相鄰的，又有不相鄰的，所以總有所以總有W(c-S) |S|。 注意到注意到c-S 是是G-S的生成子圖，故的生成子圖，故W(G-S) W(c-S) |S|。114、漢密爾頓圖（3）定理3 若無向圖無向圖G=是漢密爾頓圖，任意是漢密爾頓圖，任意S V，則，則 W(G-S) |S|，其其中中W(G-S)表示表示G中刪除中刪除S后所得子圖的連通分支數(shù)。后所得子圖的連通分支數(shù)。 定理定理3只是漢密爾頓圖的必要條件。如果圖只是漢密爾頓圖的必要條件。如果圖G不滿足這個(gè)條不滿

11、足這個(gè)條件，則件，則G肯定不是漢密爾頓圖。肯定不是漢密爾頓圖?？衫枚ɡ?來判斷一個(gè)圖不是漢密爾頓圖。因?yàn)橐驗(yàn)?W(G-a,b,c,d,e,f,g) =9| a,b,c,d,e,f,g |=7，所以圖所以圖G不是漢密爾頓圖。漢密爾頓圖。124、漢密爾頓圖（4）定理3 若無向圖無向圖G=是漢密爾頓圖，任意是漢密爾頓圖，任意S V，則，則 W(G-S) |S|，其其中中W(G-S)表示表示G中刪除中刪除S后所得子圖的連通分支數(shù)。后所得子圖的連通分支數(shù)。4 即使圖即使圖G滿足定理滿足定理3的條件，也不能肯定的條件，也不能肯定G是漢密爾頓圖。是漢密爾頓圖。如著名的彼德森圖就是一例，它滿足定理如著名的彼

12、德森圖就是一例，它滿足定理3的條件，但它不是的條件，但它不是漢密爾頓圖。漢密爾頓圖。 (1)刪除刪除1個(gè)或個(gè)或2個(gè)結(jié)點(diǎn)仍是連通圖。個(gè)結(jié)點(diǎn)仍是連通圖。 (2)刪除刪除3個(gè)結(jié)點(diǎn)，最多得個(gè)結(jié)點(diǎn)，最多得2個(gè)連通分個(gè)連通分支的子圖。支的子圖。 (3)刪除刪除4個(gè)結(jié)點(diǎn)，最多得個(gè)結(jié)點(diǎn)，最多得3個(gè)連通分個(gè)連通分支的子圖。支的子圖。 (4)刪除刪除5個(gè)或個(gè)或5個(gè)結(jié)點(diǎn)，則所得子圖個(gè)結(jié)點(diǎn)，則所得子圖的結(jié)點(diǎn)數(shù)已不大于的結(jié)點(diǎn)數(shù)已不大于5，從而排除了出現(xiàn)，從而排除了出現(xiàn)5個(gè)以上連通分支的可能性。個(gè)以上連通分支的可能性。134、漢密爾頓圖（5） 定理4 設(shè)G是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，如果圖中每對(duì)結(jié)點(diǎn)度數(shù)之和大于或等于n-1，

13、則G中存在一條漢密爾頓路（證明略）（證明略） 到目前為止，判斷一個(gè)圖是否為到目前為止，判斷一個(gè)圖是否為漢密爾頓圖還只能依據(jù)定漢密爾頓圖還只能依據(jù)定義。只有部分滿足特定條件的圖才能用判別法（充分條件）義。只有部分滿足特定條件的圖才能用判別法（充分條件）推論 設(shè)G是具有n個(gè)結(jié)點(diǎn)的無向簡(jiǎn)單圖，如果G中任一對(duì)結(jié)點(diǎn)度數(shù)之和都大于等于n，則G是漢密爾頓圖 （證明從略）（證明從略） 注意：注意：本推論與定理本推論與定理4一樣，它只不過是充分條件，而非一樣，它只不過是充分條件，而非必要條件。不滿足定理中條件的圖，也可能是漢密爾頓圖。必要條件。不滿足定理中條件的圖，也可能是漢密爾頓圖。 例如，例如，下面的圖是具

14、有下面的圖是具有6 6個(gè)結(jié)點(diǎn)的無向簡(jiǎn)單圖，它顯然是個(gè)結(jié)點(diǎn)的無向簡(jiǎn)單圖，它顯然是漢密爾頓圖漢密爾頓圖，但該圖中任一對(duì)結(jié)點(diǎn)度數(shù)之和等于，但該圖中任一對(duì)結(jié)點(diǎn)度數(shù)之和等于4，并不大，并不大于等于圖中結(jié)點(diǎn)總數(shù)于等于圖中結(jié)點(diǎn)總數(shù)6！145、標(biāo)識(shí)法（1） 判斷圖G中是否存在漢密爾頓路或漢密爾頓回路，除按定義來判斷之外，沒有一個(gè)充分必要條件可以依從，也就是說，沒有確定的判斷方法。下面的標(biāo)識(shí)法是一個(gè)可作參照的方法，但它既不是必要條件，也不是充分條件。標(biāo)識(shí)法的步驟如下: (1)先用字母先用字母A標(biāo)識(shí)圖中任一結(jié)點(diǎn)標(biāo)識(shí)圖中任一結(jié)點(diǎn),接著用接著用B標(biāo)識(shí)圖中與標(biāo)識(shí)圖中與A鄰接鄰接的結(jié)點(diǎn)。然后再用字母的結(jié)點(diǎn)。然后再用字母A

15、標(biāo)識(shí)圖中與標(biāo)識(shí)圖中與B鄰接的結(jié)點(diǎn)，如此下去，鄰接的結(jié)點(diǎn)，如此下去，直到圖中所有結(jié)點(diǎn)標(biāo)識(shí)完畢。直到圖中所有結(jié)點(diǎn)標(biāo)識(shí)完畢。 (2)在標(biāo)識(shí)過程中，當(dāng)無法實(shí)現(xiàn)在標(biāo)識(shí)過程中，當(dāng)無法實(shí)現(xiàn)A、B相間時(shí)，可在某些邊上相間時(shí)，可在某些邊上增加二度結(jié)點(diǎn)。增加二度結(jié)點(diǎn)。 (3)標(biāo)識(shí)完畢后，如果若標(biāo)識(shí)完畢后，如果若A、B數(shù)目差一個(gè)以上，則該圖不存數(shù)目差一個(gè)以上，則該圖不存在漢密爾頓回路。在漢密爾頓回路。 155、標(biāo)識(shí)法（2） 標(biāo)識(shí)法舉例： 左經(jīng)標(biāo)識(shí)后，用左經(jīng)標(biāo)識(shí)后，用7個(gè)個(gè)A，8個(gè)個(gè)B，故該圖沒有漢密爾頓回，故該圖沒有漢密爾頓回路，它不是漢密爾頓圖。但它有漢密爾頓路。路，它不是漢密爾頓圖。但它有漢密爾頓路。166、課堂練習(xí)練習(xí)：(1)(1)畫一個(gè)既有歐拉回路又有漢密爾頓回路的圖。畫一個(gè)既有歐拉回路又有漢密爾頓回路的圖。 (2)(2)畫一個(gè)有歐拉回路但沒有漢密爾頓回路的圖。畫一個(gè)有歐拉回路但沒有漢密爾頓回