離散數(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)容一、歐拉圖與中國(guó)郵路問(wèn)題一、歐拉圖與中國(guó)郵路問(wèn)題二、哈密爾頓圖二、哈密爾頓圖三、最短路問(wèn)題與貨郎擔(dān)問(wèn)題三、最短路問(wèn)題與貨郎擔(dān)問(wèn)題教學(xué)時(shí)數(shù)教學(xué)時(shí)數(shù)安排安排8學(xué)時(shí)講授本章內(nèi)容學(xué)時(shí)講授本章內(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算法算法(三三)、中國(guó)郵路問(wèn)題、中

2、國(guó)郵路問(wèn)題歐拉圖與中國(guó)郵路問(wèn)題歐拉圖與中國(guó)郵路問(wè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 3 1、歐拉圖的概念、歐拉圖的概念(一一)、歐拉圖及其性質(zhì)、歐拉圖及其性質(zhì) (1)、問(wèn)題背景、問(wèn)題背景歐拉與哥尼斯堡七橋問(wèn)題歐拉與哥尼斯堡七橋問(wèn)題 結(jié)論：在一個(gè)點(diǎn)線連接的圖形中，如果每個(gè)頂點(diǎn)關(guān)聯(lián)結(jié)論：在一個(gè)點(diǎn)線連接的圖形中，如果每個(gè)頂點(diǎn)關(guān)聯(lián)偶數(shù)條邊，并且點(diǎn)與點(diǎn)之間有路可行，則從某點(diǎn)出發(fā)，偶數(shù)條邊，并且點(diǎn)與點(diǎn)之間有路可行，則從某點(diǎn)出發(fā)，經(jīng)過(guò)每條邊一次且僅一次，可以回到出發(fā)點(diǎn)。經(jīng)過(guò)每條邊一次且僅一次，可以回到出發(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 哥尼斯堡城哥尼斯堡城(位于德國(guó)北部位于德國(guó)北部), 在歐拉的生活與圖論歷在歐拉的生活與圖論歷史中扮演著非常重要角色。因?yàn)樗?，產(chǎn)生了著名的歐拉史中扮演著非常重要角色。因?yàn)樗?，產(chǎn)生了著名的歐拉圖定理，因?yàn)樗?，產(chǎn)生了圖論。圖定理，因?yàn)樗?，產(chǎn)生了圖論。 注：注：一筆畫一筆畫-中國(guó)中國(guó)古老的古老的民間游戲民間游戲 要求：對(duì)于一個(gè)圖要求：對(duì)于一個(gè)圖G, G, 筆不離紙筆不離紙, , 一筆畫成一筆畫成. . (2)、歐拉圖概念、歐拉圖概念 定義定義1 對(duì)于連通圖對(duì)于連通圖G，如果，如果G中存在經(jīng)過(guò)每條邊的閉中存在經(jīng)過(guò)每

4、條邊的閉跡，則稱跡，則稱G為歐拉圖，簡(jiǎn)稱為歐拉圖，簡(jiǎn)稱G為為E圖。歐拉閉跡又稱為圖。歐拉閉跡又稱為歐拉環(huán)游，或歐拉回路。歐拉環(huán)游，或歐拉回路。歐拉圖歐拉圖41324132非歐拉圖非歐拉圖有歐拉跡有歐拉跡非歐拉圖非歐拉圖無(wú)歐拉跡無(wú)歐拉跡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 下列陳述對(duì)于非平凡連通圖下列陳述對(duì)于非平凡連通圖G是等價(jià)的：是等價(jià)的： (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是連通非平凡的且每個(gè)頂點(diǎn)度數(shù)為偶數(shù)，所以是連通非平凡的且每個(gè)頂點(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沒(méi)有邊，則沒(méi)有邊，則(3)成立。否則，成立。否則，G1的每個(gè)非平的每個(gè)非平凡分支是度數(shù)為偶數(shù)的連通圖，于是又可以抽取一個(gè)圈。凡分支是度數(shù)為偶數(shù)的連通圖，于是又可以抽取一個(gè)圈。反復(fù)這樣抽取，反復(fù)這樣抽取，E(G)最終劃分為若干圈。最終劃分為若干圈。 (3)(1) 設(shè)設(shè)C1是是G的邊劃分中的一個(gè)圈。若的邊劃分中的一個(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中只有兩中只有兩個(gè)頂點(diǎn)度數(shù)為奇數(shù)。個(gè)頂點(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 下面圖中誰(shuí)

8、是歐拉圖？誰(shuí)是非歐拉圖但存在歐拉下面圖中誰(shuí)是歐拉圖？誰(shuí)是非歐拉圖但存在歐拉跡？誰(shuí)是非歐拉圖且不存在歐拉跡？跡？誰(shuí)是非歐拉圖且不存在歐拉跡？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、選擇一個(gè)頂點(diǎn)任意選擇一個(gè)頂點(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)、除非沒(méi)有別的邊可選擇，否則、除非沒(méi)有別的邊可選擇，否則 ei+1不能是不能是 Gi=G-e1,e2,ei的割邊。的割邊。 (3)、 當(dāng)當(dāng)(2)不能執(zhí)行時(shí)，算法停止。不能執(zhí)行時(shí)，算法停止。 例例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是禮品店，通過(guò)是禮品店，通過(guò)g我們可以離開(kāi)博物我們可以離開(kāi)博物館。請(qǐng)找出從博物館館。請(qǐng)找出從博物館e進(jìn)入，經(jīng)過(guò)每個(gè)走廊恰好一次，最進(jìn)入，經(jīng)過(guò)每個(gè)走廊恰好一次，最后從后從g處離開(kāi)的路線。處離開(kāi)的路線。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 解：圖中只有兩個(gè)奇度頂點(diǎn)解：圖中只有兩個(gè)奇度頂點(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個(gè)奇數(shù)頂點(diǎn)，則存在個(gè)奇數(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的每個(gè)頂點(diǎn)度數(shù)為偶數(shù)，的每個(gè)頂點(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. 對(duì)于對(duì)于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)游的最長(zhǎng)跡，顯然的最長(zhǎng)跡，顯然v = w

15、,且且Q包含了與包含了與v關(guān)聯(lián)的所有邊。即關(guān)聯(lián)的所有邊。即Q是一是一條閉跡。條閉跡。 于是，于是，G-v包含包含G-Q且且G-Q的每個(gè)頂點(diǎn)度數(shù)為偶數(shù)的每個(gè)頂點(diǎn)度數(shù)為偶數(shù). 于是，于是，G-Q的非平凡分支是歐拉圖，說(shuō)明有圈，即的非平凡分支是歐拉圖，說(shuō)明有圈，即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(三三)、中國(guó)郵路問(wèn)題、中國(guó)郵路問(wèn)題 1962年，中國(guó)數(shù)學(xué)家管梅谷提出并解決了年，中國(guó)數(shù)學(xué)家管梅谷提出

18、并解決了“中國(guó)郵路問(wèn)題中國(guó)郵路問(wèn)題” 1、問(wèn)題、問(wèn)題 郵遞員派信的街道是邊賦權(quán)連通圖。從郵局出發(fā)，每條街道郵遞員派信的街道是邊賦權(quán)連通圖。從郵局出發(fā)，每條街道至少行走一次，再回郵局。如何行走，使其行走的環(huán)游路程最至少行走一次，再回郵局。如何行走，使其行走的環(huán)游路程最小？??？ 如果郵路圖本身是歐拉圖，那么由如果郵路圖本身是歐拉圖，那么由Fleury算法，可得到他的算法，可得到他的行走路線。行走路線。 如果郵路圖本身是非歐拉圖，那么為得到行走環(huán)游，必須重如果郵路圖本身是非歐拉圖，那么為得到行走環(huán)游，必須重復(fù)行走一些街道。于是問(wèn)題轉(zhuǎn)化為如何重復(fù)行走街道？復(fù)行走一些街道。于是問(wèn)題轉(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在在這樣的閉途徑中具有最短的長(zhǎng)度當(dāng)且僅當(dāng)下列兩個(gè)條件被這樣的閉途徑中具有最短的長(zhǎng)度當(dāng)且僅當(dāng)下列兩個(gè)條件被滿足：滿足： (1) 每一條邊最多重復(fù)經(jīng)過(guò)一次；每一條邊最多重復(fù)經(jīng)過(guò)一次； (2) 在在G的每一個(gè)圈上，重復(fù)經(jīng)過(guò)的邊的條數(shù)不超過(guò)圈長(zhǎng)的每一個(gè)圈上，重復(fù)經(jīng)過(guò)的邊的條數(shù)不超過(guò)圈長(zhǎng)的一半。的一半。 證明：證明：“必要性必要性” 首先，設(shè)首先，設(shè)G是連通非歐拉圖，是連

20、通非歐拉圖，u與與v是是G的兩個(gè)奇度頂點(diǎn)，的兩個(gè)奇度頂點(diǎn)，把連接把連接u與與v的路上的邊改為的路上的邊改為2重邊，則路中的點(diǎn)的度數(shù)奇偶重邊，則路中的點(diǎn)的度數(shù)奇偶性沒(méi)有改變，仍然為偶數(shù)，但性沒(méi)有改變，仍然為偶數(shù)，但u與與v的度數(shù)由奇數(shù)變成了偶數(shù)。的度數(shù)由奇數(shù)變成了偶數(shù)。如果對(duì)如果對(duì)G中每對(duì)奇度點(diǎn)都如此處理，則最終得到的圖為歐拉中每對(duì)奇度點(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 其次，對(duì)其次，對(duì)G1作修改：作修改： 如果在如果在G1中，邊中，邊e重復(fù)數(shù)大于重復(fù)數(shù)

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

22、把該圈中平行邊改為非平行超過(guò)該圈長(zhǎng)度的一半，那么可以把該圈中平行邊改為非平行邊，而把非平行邊改為平行邊，如此修改，得到的圖仍然是邊，而把非平行邊改為平行邊，如此修改，得到的圖仍然是包含包含G的歐拉圖，但對(duì)應(yīng)的歐拉環(huán)游長(zhǎng)度減小了。的歐拉圖，但對(duì)應(yīng)的歐拉環(huán)游長(zhǎng)度減小了。 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 這就是說(shuō)，只要對(duì)這就是說(shuō)，只要對(duì)G2的每個(gè)圈都作上面的修改，最后得到的每個(gè)圈都作上面的修改，最后得到的圖仍然為包含的圖仍然為包含G的歐拉圖，而最后的圖正好滿足的歐拉圖，而最后的圖正好滿足(2). “充分性充分性” 我們

23、證明：任何兩條包含我們證明：任何兩條包含G中所有邊的閉途徑中所有邊的閉途徑W1與與W2,如果滿足定理如果滿足定理2的兩個(gè)條件，則它們有相同的長(zhǎng)度。的兩個(gè)條件，則它們有相同的長(zhǎng)度。 設(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的每個(gè)頂點(diǎn)度數(shù)必然為偶數(shù)。的每個(gè)頂點(diǎn)度數(shù)必然為偶數(shù)。 令：令：Y= (Y1-Y2) (Y2-Y1) 首先：對(duì)于首先：對(duì)于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ù)，說(shuō)

25、明關(guān)聯(lián)的邊數(shù)為偶數(shù)，說(shuō)明 GY的每個(gè)頂?shù)拿總€(gè)頂點(diǎn)度數(shù)必然為偶數(shù)。點(diǎn)度數(shù)必然為偶數(shù)。 斷言斷言2： |Y1-Y2|=|Y2-Y1| 由于由于GY的每個(gè)頂點(diǎn)度數(shù)為偶數(shù)。所以，它的每個(gè)分支的每個(gè)頂點(diǎn)度數(shù)為偶數(shù)。所以，它的每個(gè)分支是歐拉圖。因此，是歐拉圖。因此， 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ù)不能超過(guò)圈長(zhǎng)的在圈中的邊數(shù)不能超過(guò)圈長(zhǎng)的一半，但圈中邊不是屬于一半，但圈中邊不是屬于Y1就是屬于就是屬于Y2,所以，在每個(gè)圈中，

26、所以，在每個(gè)圈中，Y1-Y2與與Y2-Y1中邊各占一半，即：中邊各占一半，即：122112YYYYY 由此，證明了定理的充分性。由此，證明了定理的充分性。 注注: (1)定理定理2的必要性證明過(guò)程實(shí)際上給出了求中國(guó)郵路的必要性證明過(guò)程實(shí)際上給出了求中國(guó)郵路問(wèn)題的方法問(wèn)題的方法.下面看一個(gè)例題。下面看一個(gè)例題。 例例5 求包含下圖求包含下圖G的一個(gè)最優(yōu)歐拉環(huán)游。的一個(gè)最優(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 對(duì)于一般的具有非負(fù)權(quán)值的賦權(quán)圖對(duì)于一般的具有非負(fù)權(quán)值的

28、賦權(quán)圖G來(lái)說(shuō)，如何求一條來(lái)說(shuō)，如何求一條包含包含G的邊的最優(yōu)歐拉環(huán)游？的邊的最優(yōu)歐拉環(huán)游？ 其實(shí)，可以證明：一般問(wèn)題和中國(guó)郵路問(wèn)題的特殊情況其實(shí)，可以證明：一般問(wèn)題和中國(guó)郵路問(wèn)題的特殊情況是等價(jià)的是等價(jià)的(定理定理2).也就是說(shuō)：可以通過(guò)定理也就是說(shuō)：可以通過(guò)定理2的求最優(yōu)歐拉的求最優(yōu)歐拉環(huán)游的方法來(lái)求一般情況下的最優(yōu)歐拉環(huán)游。環(huán)游的方法來(lái)求一般情況下的最優(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的一個(gè)賦權(quán)母圖的一個(gè)賦權(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 注：步驟注：步