離散數(shù)學(xué) 歐拉圖與哈密爾頓圖

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1第四章第四章 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖主要內(nèi)容主要內(nèi)容一、歐拉圖與中國郵路問題一、歐拉圖與中國郵路問題二、哈密爾頓圖二、哈密爾頓圖三、最短路問題與貨郎擔(dān)問題三、最短路問題與貨郎擔(dān)問題教學(xué)時數(shù)教學(xué)時數(shù)安排安排8學(xué)時講授本章內(nèi)容學(xué)時講授本章內(nèi)容 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2本次課主要內(nèi)容本次課主要內(nèi)容(一一)、歐拉圖及其性質(zhì)、歐拉圖及其性質(zhì)(二二)、Fleury算法算法(三三)、中國郵路問題、中

2、國郵路問題歐拉圖與中國郵路問題歐拉圖與中國郵路問題 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 1、歐拉圖的概念、歐拉圖的概念(一一)、歐拉圖及其性質(zhì)、歐拉圖及其性質(zhì) (1)、問題背景、問題背景歐拉與哥尼斯堡七橋問題歐拉與哥尼斯堡七橋問題 結(jié)論：在一個點(diǎn)線連接的圖形中，如果每個頂點(diǎn)關(guān)聯(lián)結(jié)論：在一個點(diǎn)線連接的圖形中，如果每個頂點(diǎn)關(guān)聯(lián)偶數(shù)條邊，并且點(diǎn)與點(diǎn)之間有路可行，則從某點(diǎn)出發(fā)，偶數(shù)條邊，并且點(diǎn)與點(diǎn)之間有路可行，則從某點(diǎn)出發(fā)，經(jīng)過每條邊一次且僅一次，可以回到出發(fā)點(diǎn)。經(jīng)過每條邊一次且僅一次，可以回到出發(fā)點(diǎn)。 0.8 1 0.6 0

3、.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 哥尼斯堡城哥尼斯堡城(位于德國北部位于德國北部), 在歐拉的生活與圖論歷在歐拉的生活與圖論歷史中扮演著非常重要角色。因?yàn)樗?，產(chǎn)生了著名的歐拉史中扮演著非常重要角色。因?yàn)樗a(chǎn)生了著名的歐拉圖定理，因?yàn)樗?，產(chǎn)生了圖論。圖定理，因?yàn)樗a(chǎn)生了圖論。 注：注：一筆畫一筆畫-中國中國古老的古老的民間游戲民間游戲 要求：對于一個圖要求：對于一個圖G, G, 筆不離紙筆不離紙, , 一筆畫成一筆畫成. . (2)、歐拉圖概念、歐拉圖概念 定義定義1 對于連通圖對于連通圖G，如果，如果G中存在經(jīng)過每條邊的閉中存在經(jīng)過每

4、條邊的閉跡，則稱跡，則稱G為歐拉圖，簡稱為歐拉圖，簡稱G為為E圖。歐拉閉跡又稱為圖。歐拉閉跡又稱為歐拉環(huán)游，或歐拉回路。歐拉環(huán)游，或歐拉回路。歐拉圖歐拉圖41324132非歐拉圖非歐拉圖有歐拉跡有歐拉跡非歐拉圖非歐拉圖無歐拉跡無歐拉跡1234 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 2、歐拉圖的性質(zhì)、歐拉圖的性質(zhì) 定理定理1 下列陳述對于非平凡連通圖下列陳述對于非平凡連通圖G是等價的：是等價的： (1) G是歐拉圖；是歐拉圖； (2) G的頂點(diǎn)度數(shù)為偶數(shù)；的頂點(diǎn)度數(shù)為偶數(shù)； (3) G的邊集合能劃分為圈。的邊集合能劃分為圈

5、。 證明證明: (1)(2) 由由(1)，設(shè)，設(shè) C是歐拉圖是歐拉圖G的任一歐拉回路，的任一歐拉回路，v是是G中任中任意頂點(diǎn)，意頂點(diǎn)，v在環(huán)游中每出現(xiàn)一次，意味在在環(huán)游中每出現(xiàn)一次，意味在G中有兩條不中有兩條不同邊與同邊與v關(guān)聯(lián)，所以，在關(guān)聯(lián)，所以，在G中與中與v關(guān)聯(lián)的邊數(shù)為偶數(shù)，即關(guān)聯(lián)的邊數(shù)為偶數(shù)，即v的度數(shù)為偶數(shù)，由的度數(shù)為偶數(shù)，由v的任意性，即證明的任意性，即證明(2)。 (2)(3) 由于由于G是連通非平凡的且每個頂點(diǎn)度數(shù)為偶數(shù)，所以是連通非平凡的且每個頂點(diǎn)度數(shù)為偶數(shù)，所以G中至少存在圈中至少存在圈C1,從從G中去掉中去掉C1中的邊，得到中的邊，得到G的生成的生成 0.8 1 0.6

6、0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6子圖子圖G1,若若G1沒有邊，則沒有邊，則(3)成立。否則，成立。否則，G1的每個非平的每個非平凡分支是度數(shù)為偶數(shù)的連通圖，于是又可以抽取一個圈。凡分支是度數(shù)為偶數(shù)的連通圖，于是又可以抽取一個圈。反復(fù)這樣抽取，反復(fù)這樣抽取，E(G)最終劃分為若干圈。最終劃分為若干圈。 (3)(1) 設(shè)設(shè)C1是是G的邊劃分中的一個圈。若的邊劃分中的一個圈。若G僅由此圈組成，僅由此圈組成，則則G顯然是歐拉圖。顯然是歐拉圖。 否則，由于否則，由于G連通，所以，必然存在圈連通，所以，必然存在圈C2,它和它和C1有有公共頂點(diǎn)。于是

7、，公共頂點(diǎn)。于是，C1CC2 2是一條含有是一條含有C C1 1與與C C2 2的邊的歐拉的邊的歐拉閉跡，如此拼接下去，得到包含閉跡，如此拼接下去，得到包含G G的所有邊的一條歐拉的所有邊的一條歐拉閉跡。即證閉跡。即證G G是歐拉圖。是歐拉圖。 推論推論1 連通圖連通圖G是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)G的頂點(diǎn)度數(shù)為偶。的頂點(diǎn)度數(shù)為偶。 推論推論2 連通非歐拉圖連通非歐拉圖G存在歐拉跡當(dāng)且僅當(dāng)存在歐拉跡當(dāng)且僅當(dāng)G中只有兩中只有兩個頂點(diǎn)度數(shù)為奇數(shù)。個頂點(diǎn)度數(shù)為奇數(shù)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 例例1 下面圖中誰

8、是歐拉圖？誰是非歐拉圖但存在歐拉下面圖中誰是歐拉圖？誰是非歐拉圖但存在歐拉跡？誰是非歐拉圖且不存在歐拉跡？跡？誰是非歐拉圖且不存在歐拉跡？G1G2G3 解：解：G1是歐拉圖；是歐拉圖；G2是非歐拉圖，但存在歐拉跡；是非歐拉圖，但存在歐拉跡；G3中中不存在歐拉跡。不存在歐拉跡。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8(二二)、Fleury算法算法 該算法解決了在歐拉圖中求出一條具體歐拉環(huán)游的方該算法解決了在歐拉圖中求出一條具體歐拉環(huán)游的方法。方法是盡可能避割邊行走。法。方法是盡可能避割邊行走。 1、 算法算法 (1)、 任意

9、選擇一個頂點(diǎn)任意選擇一個頂點(diǎn)v0,置置w0=v0; 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 (2)、 假設(shè)跡假設(shè)跡wi=v0e1v1eivi已經(jīng)選定，那么按下述方已經(jīng)選定，那么按下述方法從法從E-e1,e2,ei中選取邊中選取邊ei+1: 1)、 ei+1與與vi+1相關(guān)聯(lián)；相關(guān)聯(lián)； 2)、除非沒有別的邊可選擇，否則、除非沒有別的邊可選擇，否則 ei+1不能是不能是 Gi=G-e1,e2,ei的割邊。的割邊。 (3)、 當(dāng)當(dāng)(2)不能執(zhí)行時，算法停止。不能執(zhí)行時，算法停止。 例例3 在下面歐拉圖在下面歐拉圖G中求一條歐拉回

10、路。中求一條歐拉回路。dcbafeg圖圖Ghji 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 解：解：dcbafeg圖圖Ghji 例例4 某博物館的一層布置如下圖，其中邊代表走廊，某博物館的一層布置如下圖，其中邊代表走廊，結(jié)點(diǎn)結(jié)點(diǎn)e是入口，結(jié)點(diǎn)是入口，結(jié)點(diǎn)g是禮品店，通過是禮品店，通過g我們可以離開博物我們可以離開博物館。請找出從博物館館。請找出從博物館e進(jìn)入，經(jīng)過每個走廊恰好一次，最進(jìn)入，經(jīng)過每個走廊恰好一次，最后從后從g處離開的路線。處離開的路線。afedcbihgj 0.8 1 0.6 0.4 0.2 0 x t 0

11、0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 解：圖中只有兩個奇度頂點(diǎn)解：圖中只有兩個奇度頂點(diǎn)e和和g,因此存在起點(diǎn)為因此存在起點(diǎn)為e,終終點(diǎn)為點(diǎn)為g的歐拉跡。的歐拉跡。 為了在為了在G中求出一條起點(diǎn)為中求出一條起點(diǎn)為e,終點(diǎn)為終點(diǎn)為g的歐拉跡，在的歐拉跡，在e和和g間添加一條平行邊間添加一條平行邊mafedcbihgjm 用用Fleury算法求出歐拉環(huán)游為：算法求出歐拉環(huán)游為： emgcfabchbdhgdjiejge 所以：解為：所以：解為：egjeijdghdbhcbafcg 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.

12、5 1 n 12 例例4 證明：若證明：若G有有2k0個奇數(shù)頂點(diǎn)，則存在個奇數(shù)頂點(diǎn)，則存在k條邊不重條邊不重的跡的跡Q1,Q2,Qk，使得：，使得：12( )()()()kE GE QE QE Q 證明：不失一般性，只就證明：不失一般性，只就G是連通圖進(jìn)行證明。是連通圖進(jìn)行證明。 設(shè)設(shè)G=(n, m)是連通圖。令是連通圖。令vl，v2，,vk,vk+1,v2k是是G的所的所有奇度點(diǎn)。有奇度點(diǎn)。 在在vi與與vi+k間連新邊間連新邊ei得圖得圖G*（1ik).ik).則則G G* *是歐拉圖，是歐拉圖，因此，由因此，由FleuryFleury算法得歐拉環(huán)游算法得歐拉環(huán)游C.C. 在在C中刪去中刪

13、去ei （1ik).得得k條邊不重的跡條邊不重的跡Qi （1ik):12( )()()()kE GE QE QE Q 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 例例5 設(shè)設(shè)G是非平凡的歐拉圖，且是非平凡的歐拉圖，且v V(G)。證明：。證明：G的每條具有起點(diǎn)的每條具有起點(diǎn)v的跡都能擴(kuò)展成的跡都能擴(kuò)展成G的歐拉環(huán)游當(dāng)且僅當(dāng)?shù)臍W拉環(huán)游當(dāng)且僅當(dāng)G-v是森林。是森林。 證明：證明：“必要性必要性” 若不然，則若不然，則G-v有圈有圈C。 考慮考慮G1=G-E(G)的含有頂點(diǎn)的含有頂點(diǎn)v的分支的分支H。 由于由于G是非平凡歐拉圖，所

14、以是非平凡歐拉圖，所以G1的每個頂點(diǎn)度數(shù)為偶數(shù)，的每個頂點(diǎn)度數(shù)為偶數(shù)，從而，從而，H是歐拉圖。是歐拉圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 H是歐拉圖，所以存在歐拉環(huán)游是歐拉圖，所以存在歐拉環(huán)游T. 對于對于T，把它看成，把它看成v為起點(diǎn)和終點(diǎn)的一條歐拉跡，顯然不能擴(kuò)充為為起點(diǎn)和終點(diǎn)的一條歐拉跡，顯然不能擴(kuò)充為G的歐拉的歐拉環(huán)游。這與條件矛盾！環(huán)游。這與條件矛盾！ “充分性充分性” 若不然，設(shè)若不然，設(shè)Q=(v, w)是是G的一條不能擴(kuò)充為的一條不能擴(kuò)充為G的歐拉環(huán)游的歐拉環(huán)游的最長跡，顯然的最長跡，顯然v = w

15、,且且Q包含了與包含了與v關(guān)聯(lián)的所有邊。即關(guān)聯(lián)的所有邊。即Q是一是一條閉跡。條閉跡。 于是，于是，G-v包含包含G-Q且且G-Q的每個頂點(diǎn)度數(shù)為偶數(shù)的每個頂點(diǎn)度數(shù)為偶數(shù). 于是，于是，G-Q的非平凡分支是歐拉圖，說明有圈，即的非平凡分支是歐拉圖，說明有圈，即G-v有有圈，這與條件矛盾圈，這與條件矛盾. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.

16、5 2 1 0.5 0 0.5 1 n 17 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5

17、 1 n 22 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24l定理15.7l定理15.8 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26(三三)、中國郵路問題、中國郵路問題 1962年，中國數(shù)學(xué)家管梅谷提出并解決了年，中國數(shù)學(xué)家管梅谷提出

18、并解決了“中國郵路問題中國郵路問題” 1、問題、問題 郵遞員派信的街道是邊賦權(quán)連通圖。從郵局出發(fā)，每條街道郵遞員派信的街道是邊賦權(quán)連通圖。從郵局出發(fā)，每條街道至少行走一次，再回郵局。如何行走，使其行走的環(huán)游路程最至少行走一次，再回郵局。如何行走，使其行走的環(huán)游路程最?。啃?？ 如果郵路圖本身是歐拉圖，那么由如果郵路圖本身是歐拉圖，那么由Fleury算法，可得到他的算法，可得到他的行走路線。行走路線。 如果郵路圖本身是非歐拉圖，那么為得到行走環(huán)游，必須重如果郵路圖本身是非歐拉圖，那么為得到行走環(huán)游，必須重復(fù)行走一些街道。于是問題轉(zhuǎn)化為如何重復(fù)行走街道？復(fù)行走一些街道。于是問題轉(zhuǎn)化為如何重復(fù)行走街道

19、？ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27 2、管梅谷的結(jié)論、管梅谷的結(jié)論 定理定理2 若若W是圖是圖G中一條包含所有邊的閉途徑，則中一條包含所有邊的閉途徑，則W在在這樣的閉途徑中具有最短的長度當(dāng)且僅當(dāng)下列兩個條件被這樣的閉途徑中具有最短的長度當(dāng)且僅當(dāng)下列兩個條件被滿足：滿足： (1) 每一條邊最多重復(fù)經(jīng)過一次；每一條邊最多重復(fù)經(jīng)過一次； (2) 在在G的每一個圈上，重復(fù)經(jīng)過的邊的條數(shù)不超過圈長的每一個圈上，重復(fù)經(jīng)過的邊的條數(shù)不超過圈長的一半。的一半。 證明：證明：“必要性必要性” 首先，設(shè)首先，設(shè)G是連通非歐拉圖，是連

20、通非歐拉圖，u與與v是是G的兩個奇度頂點(diǎn)，的兩個奇度頂點(diǎn)，把連接把連接u與與v的路上的邊改為的路上的邊改為2重邊，則路中的點(diǎn)的度數(shù)奇偶重邊，則路中的點(diǎn)的度數(shù)奇偶性沒有改變，仍然為偶數(shù)，但性沒有改變，仍然為偶數(shù)，但u與與v的度數(shù)由奇數(shù)變成了偶數(shù)。的度數(shù)由奇數(shù)變成了偶數(shù)。如果對如果對G中每對奇度點(diǎn)都如此處理，則最終得到的圖為歐拉中每對奇度點(diǎn)都如此處理，則最終得到的圖為歐拉圖。設(shè)該圖為圖。設(shè)該圖為G1. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 其次，對其次，對G1作修改：作修改： 如果在如果在G1中，邊中，邊e重復(fù)數(shù)大于重復(fù)數(shù)

21、大于2，則在則在G G1 1中刪掉中刪掉2 2條重復(fù)的條重復(fù)的e e邊后，所得之圖仍然是包含邊后，所得之圖仍然是包含G G的歐拉圖。的歐拉圖。 在在G1中，對每組平行邊都做上面的處理，最后得到一個重中，對每組平行邊都做上面的處理，最后得到一個重復(fù)邊數(shù)最多為復(fù)邊數(shù)最多為1的包含的包含G的歐拉圖的歐拉圖G2。 這說明，若這說明，若W是包含是包含G的所有邊的歐拉環(huán)游，則的所有邊的歐拉環(huán)游，則G中每條中每條邊至多在邊至多在W里出現(xiàn)兩次。這就證明了里出現(xiàn)兩次。這就證明了(1). 又設(shè)又設(shè)C是是G2中任意一個圈，在該圈中，如果有平行邊條數(shù)中任意一個圈，在該圈中，如果有平行邊條數(shù)超過該圈長度的一半，那么可以

22、把該圈中平行邊改為非平行超過該圈長度的一半，那么可以把該圈中平行邊改為非平行邊，而把非平行邊改為平行邊，如此修改，得到的圖仍然是邊，而把非平行邊改為平行邊，如此修改，得到的圖仍然是包含包含G的歐拉圖，但對應(yīng)的歐拉環(huán)游長度減小了。的歐拉圖，但對應(yīng)的歐拉環(huán)游長度減小了。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 這就是說，只要對這就是說，只要對G2的每個圈都作上面的修改，最后得到的每個圈都作上面的修改，最后得到的圖仍然為包含的圖仍然為包含G的歐拉圖，而最后的圖正好滿足的歐拉圖，而最后的圖正好滿足(2). “充分性充分性” 我們

23、證明：任何兩條包含我們證明：任何兩條包含G中所有邊的閉途徑中所有邊的閉途徑W1與與W2,如果滿足定理如果滿足定理2的兩個條件，則它們有相同的長度。的兩個條件，則它們有相同的長度。 設(shè)設(shè)Y1與與Y2分別表示分別表示W(wǎng)1與與W2中重復(fù)出現(xiàn)的邊集合。中重復(fù)出現(xiàn)的邊集合。 如果能夠證明：如果能夠證明：|Y1-Y2|=|Y2-Y1|, 那么那么d(W1)=d(W2). 斷言斷言1：GY的每個頂點(diǎn)度數(shù)必然為偶數(shù)。的每個頂點(diǎn)度數(shù)必然為偶數(shù)。 令：令：Y= (Y1-Y2) (Y2-Y1) 首先：對于首先：對于G中任意點(diǎn)中任意點(diǎn)v, 如果如果d G (v)是奇數(shù)，那么是奇數(shù)，那么Y1與與Y2中與中與v關(guān)聯(lián)的邊數(shù)

24、均為奇數(shù)；關(guān)聯(lián)的邊數(shù)均為奇數(shù)； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 如果如果d G (v)是偶數(shù)，那么是偶數(shù)，那么Y1與與Y2中與中與v關(guān)聯(lián)的邊數(shù)均為偶關(guān)聯(lián)的邊數(shù)均為偶數(shù)。數(shù)。 所以所以Y1與與Y2中與中與G中任意點(diǎn)關(guān)聯(lián)的邊數(shù)奇偶性相同。中任意點(diǎn)關(guān)聯(lián)的邊數(shù)奇偶性相同。 其次，設(shè)其次，設(shè)Y1與與Y2中與中與v關(guān)聯(lián)的邊數(shù)分別為關(guān)聯(lián)的邊數(shù)分別為y1與與y2,其中相其中相同的邊數(shù)為同的邊數(shù)為y0，那么，那么，Y中與中與v關(guān)聯(lián)的邊數(shù)為：關(guān)聯(lián)的邊數(shù)為： 10201202yyyyyyy 所以，所以，Y中與中與v關(guān)聯(lián)的邊數(shù)為偶數(shù)，說

25、明關(guān)聯(lián)的邊數(shù)為偶數(shù)，說明 GY的每個頂?shù)拿總€頂點(diǎn)度數(shù)必然為偶數(shù)。點(diǎn)度數(shù)必然為偶數(shù)。 斷言斷言2： |Y1-Y2|=|Y2-Y1| 由于由于GY的每個頂點(diǎn)度數(shù)為偶數(shù)。所以，它的每個分支的每個頂點(diǎn)度數(shù)為偶數(shù)。所以，它的每個分支是歐拉圖。因此，是歐拉圖。因此， GY可以作不重圈分解。可以作不重圈分解。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 由定理由定理2的條件的條件(2), Y1與與Y2在圈中的邊數(shù)不能超過圈長的在圈中的邊數(shù)不能超過圈長的一半，但圈中邊不是屬于一半，但圈中邊不是屬于Y1就是屬于就是屬于Y2,所以，在每個圈中，

26、所以，在每個圈中，Y1-Y2與與Y2-Y1中邊各占一半，即：中邊各占一半，即：122112YYYYY 由此，證明了定理的充分性。由此，證明了定理的充分性。 注注: (1)定理定理2的必要性證明過程實(shí)際上給出了求中國郵路的必要性證明過程實(shí)際上給出了求中國郵路問題的方法問題的方法.下面看一個例題。下面看一個例題。 例例5 求包含下圖求包含下圖G的一個最優(yōu)歐拉環(huán)游。的一個最優(yōu)歐拉環(huán)游。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 32 解：由定理解：由定理2：v8v7v6v5v4v3v2v1v12v11v10v9Gv15v14v13v8

27、v7v6v5v4v3v2v1v12v11v10v9Gv15v14v13 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 33 修改后得：修改后得：v8v7v6v5v4v3v2v1v12v11v10v9Gv15v14v13 由由Fleury算法得可得到具體的最優(yōu)歐拉環(huán)游。算法得可得到具體的最優(yōu)歐拉環(huán)游。 3、非負(fù)權(quán)值的賦權(quán)圖的最優(yōu)歐拉環(huán)游、非負(fù)權(quán)值的賦權(quán)圖的最優(yōu)歐拉環(huán)游 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 34 對于一般的具有非負(fù)權(quán)值的賦權(quán)圖對于一般的具有非負(fù)權(quán)值的

28、賦權(quán)圖G來說，如何求一條來說，如何求一條包含包含G的邊的最優(yōu)歐拉環(huán)游？的邊的最優(yōu)歐拉環(huán)游？ 其實(shí)，可以證明：一般問題和中國郵路問題的特殊情況其實(shí)，可以證明：一般問題和中國郵路問題的特殊情況是等價的是等價的(定理定理2).也就是說：可以通過定理也就是說：可以通過定理2的求最優(yōu)歐拉的求最優(yōu)歐拉環(huán)游的方法來求一般情況下的最優(yōu)歐拉環(huán)游。環(huán)游的方法來求一般情況下的最優(yōu)歐拉環(huán)游。 所以，求一般非負(fù)權(quán)賦權(quán)圖的最優(yōu)歐拉環(huán)游步驟為：所以，求一般非負(fù)權(quán)賦權(quán)圖的最優(yōu)歐拉環(huán)游步驟為： (1)、用添加重復(fù)邊的方法求、用添加重復(fù)邊的方法求G的一個賦權(quán)母圖的一個賦權(quán)母圖G*，使：，使：(*)()( )e E GE Gw e盡可能小 (2)、用、用Fleury算法在算法在G*中求出歐拉環(huán)游。中求出歐拉環(huán)游。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 35 注：步驟注：步