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

1、1第7-4講 歐拉圖與漢密爾頓圖 1. 歐拉圖2. 有向圖中的歐拉路3. 周游世界問題4. 漢密爾頓圖5. 標(biāo)識法6.課堂練習(xí)7. 第7-4講 作業(yè)21、歐拉圖（1） 定義1 設(shè)圖設(shè)圖G無孤立結(jié)點，若存在一條路無孤立結(jié)點，若存在一條路(回路回路)，經(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連通，且有零個或兩個奇數(shù)度結(jié)點。證：必要性。設(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é)點可重復(fù)出現(xiàn)，但邊不重復(fù)，且每條邊都經(jīng)歷一次，因此，中結(jié)點可重復(fù)出現(xiàn)，但邊不重復(fù)，且每條邊都經(jīng)歷一次，因此，歐拉路遍歷歐拉路遍歷G G中所有結(jié)點，所以中所有結(jié)點，所以G G是連通的。是連通的。 其次，若其次，若v vi

3、i不是端點，則不是端點，則deg(vdeg(vi i) )必為偶數(shù)；而對端點必為偶數(shù)；而對端點v v0 0和和v vk k，如果如果v v0 0=v=vk k，則，則G G中無奇數(shù)度結(jié)點；如果中無奇數(shù)度結(jié)點；如果v v0 0 v vk k，則，則deg(vdeg(v0 0) )和和deg(vdeg(vk k) )必為奇數(shù)，故必為奇數(shù)，故G G中有一對奇數(shù)度結(jié)點。中有一對奇數(shù)度結(jié)點。 充分性。當(dāng)當(dāng)G G連通，且有零個或兩個奇數(shù)度結(jié)點。可按如下連通，且有零個或兩個奇數(shù)度結(jié)點?？砂慈缦路椒?gòu)造一條歐拉路。方法構(gòu)造一條歐拉路。 (1)(1)若若G G有兩個奇數(shù)度結(jié)點有兩個奇數(shù)度結(jié)點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é)點，則可從無奇數(shù)度結(jié)點，則可從任何結(jié)點任何結(jié)點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連通，且有零個或兩個奇數(shù)度結(jié)點。證：充分性(續(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é)點得子圖孤立結(jié)點得子圖GG，GG中每個結(jié)點的度數(shù)應(yīng)為偶數(shù)。因中每個結(jié)點的度數(shù)應(yīng)為偶數(shù)。因G G連連通，所以通，所以L L1 1與與GG至少有一個結(jié)點至少有一個結(jié)點v vj j重合，在重合，在GG中從結(jié)點中從結(jié)點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)過圖G G

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

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

8、象七橋問題那樣有一個完滿的結(jié)局，判定此類問題是否有解至今還未找到一個方便的的結(jié)局，判定此類問題是否有解至今還未找到一個方便的充分必要條件。充分必要條件。94、漢密爾頓圖（1） 定義3 經(jīng)過圖中每個結(jié)點一次且僅一次的路經(jīng)過圖中每個結(jié)點一次且僅一次的路(回路回路) 稱為稱為漢密爾頓路(漢密爾頓回路)。具有漢密爾頓回路的圖叫。具有漢密爾頓回路的圖叫漢密爾頓圖 例如，判斷下面各圖例如，判斷下面各圖 是否為漢密爾頓圖是否為漢密爾頓圖。 圖圖(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é)點在中的結(jié)點在c上兩兩相鄰，則上兩兩相鄰，則W(c-S)=1 |S|。 (2) 如果如果S中的結(jié)點在中的結(jié)點在c上存在上存在 r (2 r |S|)個互不相鄰的部分，個

10、互不相鄰的部分，則則W(c-S)=r |S|。 一般說來，一般說來，S中的結(jié)點在中的結(jié)點在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不滿足這個條不滿足這個條

11、件，則件，則G肯定不是漢密爾頓圖?？隙ú皇菨h密爾頓圖?？衫枚ɡ?來判斷一個圖不是漢密爾頓圖。因為因為 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個或個或2個結(jié)點仍是連通圖。個結(jié)點仍是連通圖。 (2)刪除刪除3個結(jié)點，最多得個結(jié)點，最多得2個連通分個連通分支的子圖。支的子圖。 (3)刪除刪除4個結(jié)點，最多得個結(jié)點，最多得3個連通分個連通分支的子圖。支的子圖。 (4)刪除刪除5個或個或5個結(jié)點，則所得子圖個結(jié)點，則所得子圖的結(jié)點數(shù)已不大于的結(jié)點數(shù)已不大于5，從而排除了出現(xiàn)，從而排除了出現(xiàn)5個以上連通分支的可能性。個以上連通分支的可能性。134、漢密爾頓圖（5） 定理4 設(shè)G是具有n個結(jié)點的簡單圖，如果圖中每對結(jié)點度數(shù)之和大于或等于n-1，則G中存

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

14、圖是具有6 6個結(jié)點的無向簡單圖，它顯然是個結(jié)點的無向簡單圖，它顯然是漢密爾頓圖漢密爾頓圖，但該圖中任一對結(jié)點度數(shù)之和等于，但該圖中任一對結(jié)點度數(shù)之和等于4，并不大，并不大于等于圖中結(jié)點總數(shù)于等于圖中結(jié)點總數(shù)6！145、標(biāo)識法（1） 判斷圖G中是否存在漢密爾頓路或漢密爾頓回路，除按定義來判斷之外，沒有一個充分必要條件可以依從，也就是說，沒有確定的判斷方法。下面的標(biāo)識法是一個可作參照的方法，但它既不是必要條件，也不是充分條件。標(biāo)識法的步驟如下: (1)先用字母先用字母A標(biāo)識圖中任一結(jié)點標(biāo)識圖中任一結(jié)點,接著用接著用B標(biāo)識圖中與標(biāo)識圖中與A鄰接鄰接的結(jié)點。然后再用字母的結(jié)點。然后再用字母A標(biāo)識圖中與標(biāo)識圖中與B鄰接的結(jié)點，如此下去，鄰接的結(jié)點，如此下去，直到圖中所有結(jié)點標(biāo)識完畢。直到圖中所有結(jié)點標(biāo)識完畢。 (2)在標(biāo)識過程中，當(dāng)無法實現(xiàn)在標(biāo)識過程中，當(dāng)無法實現(xiàn)A、B相間時，可在某些邊上相間時，可在某些邊上增加二度結(jié)點。增加二度結(jié)點。 (3)標(biāo)識完畢后，如果若標(biāo)識完畢后，如果若A、B數(shù)目差一個以上，則該圖不存數(shù)目差一個以上，則該圖不存在漢密爾頓回路。在漢密爾頓回路。 155、標(biāo)識法（2） 標(biāo)識法舉例： 左經(jīng)標(biāo)識后，用左經(jīng)標(biāo)識后，用7個個A，8個個B，故該圖沒