1、陳瑜陳瑜Email：2022年年7月月5日星期二日星期二 第第1313章章 歐拉圖與哈密頓圖歐拉圖與哈密頓圖7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2/98/98主要內(nèi)容主要內(nèi)容(1)EulerEuler圖及其應(yīng)用圖及其應(yīng)用 1)1)歐拉道路（回路）的定義歐拉道路（回路）的定義 2)2)如何判別歐拉圖如何判別歐拉圖 3)3)一個(gè)圖含有歐拉道路的條件一個(gè)圖含有歐拉道路的條件 4)4)連通有向圖連通有向圖G G中含有有向歐拉道路和回路的中含有有向歐拉道路和回路的充要條件充要條件 5)Fleury5)Fleury算法算法 6)Euler6)Euler圖的應(yīng)用圖的應(yīng)用( (中國(guó)郵遞員問(wèn)題算法中國(guó)郵遞員問(wèn)題

2、算法) )7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院3/98/98主要內(nèi)容主要內(nèi)容(2)哈密頓圖及其應(yīng)用：哈密頓圖及其應(yīng)用：哈密頓道路（圈哈密頓道路（圈 ）的）的定義定義連通圖連通圖G G是哈密頓圖的是哈密頓圖的必要條件必要條件連通圖連通圖G G是哈密頓圖的是哈密頓圖的充分條件充分條件連通圖連通圖G G是哈密頓圖的是哈密頓圖的充要條件充要條件 哈密頓圖的應(yīng)用哈密頓圖的應(yīng)用( (推銷商問(wèn)題推銷商問(wèn)題) )7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院4/98/98哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題 哥尼斯堡城市有一條橫貫全城的普雷格爾哥尼斯堡城市有一條橫貫全城的普雷格爾(Pregel)(Pregel)河，城的各部

3、分用七座橋聯(lián)接，每逢假日，城中居民進(jìn)河，城的各部分用七座橋聯(lián)接，每逢假日，城中居民進(jìn)行環(huán)城逛游，這樣就產(chǎn)生了一個(gè)行環(huán)城逛游，這樣就產(chǎn)生了一個(gè)問(wèn)題：?jiǎn)栴}：能不能設(shè)計(jì)一次能不能設(shè)計(jì)一次“遍游遍游”，使得從某地出發(fā)對(duì)每座跨河橋只走一次，而，使得從某地出發(fā)對(duì)每座跨河橋只走一次，而在遍歷了七橋之后卻又能回到原地？在遍歷了七橋之后卻又能回到原地？ A Ab b2 2B BD DC Cb b4 4b b1 1b b3 3b b5 5b b7 7b b6 67/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院5/98/98EulerEuler圖圖n定義定義13.113.1設(shè)設(shè)G G是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含是一個(gè)無(wú)孤立結(jié)點(diǎn)的

4、圖，包含G G的的每條邊每條邊的的簡(jiǎn)單道路簡(jiǎn)單道路（回路回路）稱為該圖的一條）稱為該圖的一條歐拉道路歐拉道路（回路回路）。）。具有歐拉回路具有歐拉回路的圖稱為的圖稱為歐歐拉圖拉圖。規(guī)定平凡圖為歐拉圖。規(guī)定平凡圖為歐拉圖。 顯然，每個(gè)歐拉圖必然是連通圖。顯然，每個(gè)歐拉圖必然是連通圖。 因此，一條歐拉道路（回路）是經(jīng)過(guò)圖中每因此，一條歐拉道路（回路）是經(jīng)過(guò)圖中每邊一次且僅一次的道路（回路）。邊一次且僅一次的道路（回路）。為什么？為什么？無(wú)重復(fù)邊復(fù)習(xí)：若道路中的所有邊復(fù)習(xí)：若道路中的所有邊e1，e2，ek（有向邊）（有向邊）互不相同，則稱此道路為互不相同，則稱此道路為簡(jiǎn)單道路簡(jiǎn)單道路；閉的簡(jiǎn)單道路；

5、閉的簡(jiǎn)單道路稱為稱為回路回路。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院6/98/98EulerEuler圖圖n定義定義13.113.1設(shè)設(shè)G G是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含G G的每條邊的簡(jiǎn)單道路（回路）稱為該圖的一條的每條邊的簡(jiǎn)單道路（回路）稱為該圖的一條歐拉道路（回路）。具有歐拉回路的圖稱為歐歐拉道路（回路）。具有歐拉回路的圖稱為歐拉圖。拉圖。規(guī)定規(guī)定平凡圖為歐拉圖平凡圖為歐拉圖。 顯然，每個(gè)顯然，每個(gè)歐拉圖歐拉圖必然是連通圖。必然是連通圖。 因此，一條歐拉道路（回路）是經(jīng)過(guò)圖中每因此，一條歐拉道路（回路）是經(jīng)過(guò)圖中每邊一次且僅一次的道路（回路）。邊一次且僅一次的道路（

6、回路）。為什么？為什么？7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院7/98/98EulerEuler圖圖n定義定義13.113.1設(shè)設(shè)G G是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含G G的每條邊的簡(jiǎn)單道路（回路）稱為該圖的一條的每條邊的簡(jiǎn)單道路（回路）稱為該圖的一條歐拉道路（回路）。具有歐拉回路的圖稱為歐歐拉道路（回路）。具有歐拉回路的圖稱為歐拉圖。拉圖。規(guī)定平凡圖為歐拉圖。規(guī)定平凡圖為歐拉圖。 顯然，每個(gè)歐拉圖必然是連通圖。顯然，每個(gè)歐拉圖必然是連通圖。 因此，一條因此，一條歐拉道路歐拉道路（回路回路）是經(jīng)過(guò)圖中）是經(jīng)過(guò)圖中每每邊一次且僅一次邊一次且僅一次的道路（的道路（回路回路）。）

7、。為什么？為什么？7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院8/98/98例例13.113.1v v5 5v v1 1v v2 2v v3 3v v4 4a)a)v v5 5v v1 1v v2 2v v3 3v v4 4b)b)v v4 4v v1 1v v2 2v v3 3c)c) 圖圖a a是歐拉圖；圖是歐拉圖；圖b b不是歐拉圖，但存在歐拉道不是歐拉圖，但存在歐拉道路；圖路；圖c c不存在歐拉道路。不存在歐拉道路。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院9/98/98n定理定理13.1 13.1 無(wú)向連通圖無(wú)向連通圖G GVE是歐拉圖當(dāng)是歐拉圖當(dāng)且僅當(dāng)且僅當(dāng)G G的的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)所有結(jié)

8、點(diǎn)的度數(shù)都為偶數(shù)。證明：證明： “ “” 設(shè)設(shè)G G是是EulerEuler圖，則圖，則G G必然存在一條包含所有邊必然存在一條包含所有邊（也包含所有結(jié)點(diǎn)）的回路（也包含所有結(jié)點(diǎn)）的回路C C，對(duì)，對(duì) u u V V，u u必然在必然在C C中出現(xiàn)一次（可出現(xiàn)多次），中出現(xiàn)一次（可出現(xiàn)多次），每出現(xiàn)每出現(xiàn)u u一次，都一次，都關(guān)聯(lián)著關(guān)聯(lián)著G G中的兩條邊，而當(dāng)中的兩條邊，而當(dāng)u u又重復(fù)出現(xiàn)時(shí)，它又又重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)著關(guān)聯(lián)著G G中的另外的兩條邊，（為什么？）中的另外的兩條邊，（為什么？） 因而因而u u每出現(xiàn)一次，都將使得結(jié)點(diǎn)每出現(xiàn)一次，都將使得結(jié)點(diǎn)u u的度數(shù)增的度數(shù)增加加2 2度，若

9、度，若u u在通路中重復(fù)出現(xiàn)在通路中重復(fù)出現(xiàn)j j次，則次，則deg(u)deg(u)2j2j。 即即u u的度數(shù)必為偶數(shù)。的度數(shù)必為偶數(shù)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院10/98/98n定理定理13.1 13.1 無(wú)向連通圖無(wú)向連通圖G GVE是歐拉圖當(dāng)是歐拉圖當(dāng)且僅當(dāng)且僅當(dāng)G G的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)。的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)。證明：證明： “” 設(shè)設(shè)G G是是EulerEuler圖，則圖，則G G必然存在一條包含所有邊必然存在一條包含所有邊（也包含所有結(jié)點(diǎn)）的回路（也包含所有結(jié)點(diǎn)）的回路C C，對(duì)，對(duì) u u V V，u u必然在必然在C C中出現(xiàn)一次（可出現(xiàn)多次），中出現(xiàn)一次（

10、可出現(xiàn)多次），每出現(xiàn)每出現(xiàn)u u一次，都一次，都關(guān)聯(lián)著關(guān)聯(lián)著G G中的兩條邊，而當(dāng)中的兩條邊，而當(dāng)u u又重復(fù)出現(xiàn)時(shí)，它又又重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)著關(guān)聯(lián)著G G中的另外的兩條邊，（中的另外的兩條邊，（為什么？為什么？） 因而因而u u每出現(xiàn)一次，都將使得結(jié)點(diǎn)每出現(xiàn)一次，都將使得結(jié)點(diǎn)u u的度數(shù)增的度數(shù)增加加2 2度，若度，若u u在通路中重復(fù)出現(xiàn)在通路中重復(fù)出現(xiàn)j j次，則次，則deg(u)deg(u)2j2j。 即即u u的度數(shù)必為偶數(shù)的度數(shù)必為偶數(shù)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院11/98/98n定理定理13.1 13.1 無(wú)向連通圖無(wú)向連通圖G GVE是歐拉圖當(dāng)是歐拉圖當(dāng)且僅當(dāng)且僅當(dāng)

11、G G的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)。的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)。證明：證明： “” 設(shè)設(shè)G G是是EulerEuler圖，則圖，則G G必然存在一條包含所有邊必然存在一條包含所有邊（也包含所有結(jié)點(diǎn)）的回路（也包含所有結(jié)點(diǎn)）的回路C C，對(duì)，對(duì) u u V V，u u必然在必然在C C中出現(xiàn)一次（可出現(xiàn)多次），中出現(xiàn)一次（可出現(xiàn)多次），每出現(xiàn)每出現(xiàn)u u一次，都一次，都關(guān)聯(lián)著關(guān)聯(lián)著G G中的兩條邊，而當(dāng)中的兩條邊，而當(dāng)u u又重復(fù)出現(xiàn)時(shí)，它又又重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)著關(guān)聯(lián)著G G中的另外的兩條邊，（中的另外的兩條邊，（為什么？為什么？） 因而因而u u每出現(xiàn)一次，都將使得結(jié)點(diǎn)每出現(xiàn)一次，都將使得結(jié)點(diǎn)u

12、u的度數(shù)增的度數(shù)增加加2 2度，若度，若u u在通路中重復(fù)出現(xiàn)在通路中重復(fù)出現(xiàn)j j次，則次，則deg(u)deg(u)2j2j。 即即u u的度數(shù)必為偶數(shù)的度數(shù)必為偶數(shù)。由于在回路由于在回路C中邊不可能重中邊不可能重復(fù)出現(xiàn)復(fù)出現(xiàn)7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院12/98/98“” 設(shè)連通圖設(shè)連通圖G G的結(jié)點(diǎn)的的結(jié)點(diǎn)的度數(shù)度數(shù)都是偶數(shù)，則都是偶數(shù)，則G G必必含有簡(jiǎn)單回路含有簡(jiǎn)單回路（可用歸納法證明可用歸納法證明） 。 設(shè)設(shè)C C是一條包含是一條包含G G中邊最多的簡(jiǎn)單回路：中邊最多的簡(jiǎn)單回路： 若若C C已經(jīng)包含已經(jīng)包含G G中所有的邊，則中所有的邊，則C C就是就是EulerEule

13、r回回路，結(jié)論成立。路，結(jié)論成立。 若若C C不能包含不能包含G G中所有的邊，則刪邊子圖中所有的邊，則刪邊子圖 G-EG-E（C C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。 由于由于G G是連通的，是連通的，C C中應(yīng)至少存在一點(diǎn)中應(yīng)至少存在一點(diǎn)v v，使，使G-G-E E（C C）中有一條包含）中有一條包含v v的回路的回路CC。（見(jiàn)示意圖）（見(jiàn)示意圖）7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院13/98/98“” 設(shè)連通圖設(shè)連通圖G G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G G必必含有簡(jiǎn)單回路（可用歸納法證明）含有簡(jiǎn)單回路（可用歸納法證明） 。 設(shè)設(shè)C C是一條包含是一條包含G G

14、中邊最多的簡(jiǎn)單回路：中邊最多的簡(jiǎn)單回路： 若若C C已經(jīng)包含已經(jīng)包含G G中所有的邊，則中所有的邊，則C C就是就是EulerEuler回回路，結(jié)論成立。路，結(jié)論成立。 若若C C不能包含不能包含G G中所有的邊，則刪邊子圖中所有的邊，則刪邊子圖 G-EG-E（C C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。 由于由于G G是連通的，是連通的，C C中應(yīng)至少存在一點(diǎn)中應(yīng)至少存在一點(diǎn)v v，使，使G-G-E E（C C）中有一條包含）中有一條包含v v的回路的回路CC。（見(jiàn)示意圖）（見(jiàn)示意圖）7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院14/98/98“” 設(shè)連通圖設(shè)連通圖G G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則的

15、結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G G必必含有簡(jiǎn)單回路（可用歸納法證明）含有簡(jiǎn)單回路（可用歸納法證明） 。 設(shè)設(shè)C C是一條包含是一條包含G G中邊最多的簡(jiǎn)單回路：中邊最多的簡(jiǎn)單回路： 若若C C已經(jīng)包含已經(jīng)包含G G中所有的邊，則中所有的邊，則C C就是就是EulerEuler回回路，結(jié)論成立。路，結(jié)論成立。 若若C C不能包含不能包含G G中所有的邊，則刪邊子圖中所有的邊，則刪邊子圖 G-EG-E（C C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。 由于由于G G是連通的，是連通的，C C中應(yīng)至少存在一點(diǎn)中應(yīng)至少存在一點(diǎn)v v，使，使G-G-E E（C C）中有一條包含）中有一條包含v v的回路的回路C

16、C。（見(jiàn)示意圖）（見(jiàn)示意圖）7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院15/98/98“” 設(shè)連通圖設(shè)連通圖G G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G G必必含有簡(jiǎn)單回路（可用歸納法證明）含有簡(jiǎn)單回路（可用歸納法證明） 。 設(shè)設(shè)C C是一條包含是一條包含G G中邊最多的簡(jiǎn)單回路：中邊最多的簡(jiǎn)單回路： 若若C C已經(jīng)包含已經(jīng)包含G G中所有的邊，則中所有的邊，則C C就是就是EulerEuler回回路，結(jié)論成立。路，結(jié)論成立。 若若C C不能包含不能包含G G中所有的邊，則刪邊子圖中所有的邊，則刪邊子圖 G-EG-E（C C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。 由于由于G G是連通的

17、，是連通的，C C中應(yīng)至少存在一點(diǎn)中應(yīng)至少存在一點(diǎn)v v，使，使G-G-E E（C C）中有一條包含）中有一條包含v v的回路的回路CC。（見(jiàn)示意圖）（見(jiàn)示意圖）7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院16/98/98 這樣，就可以構(gòu)造出一條由這樣，就可以構(gòu)造出一條由C C和和CC組成的組成的G G的回路，其包含的邊數(shù)比的回路，其包含的邊數(shù)比C C多，與多，與假設(shè)矛盾假設(shè)矛盾。因此，因此，C C必是必是EulerEuler回路，結(jié)論成立。回路，結(jié)論成立。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院17/98/98證明：證明：“” ” 設(shè)設(shè)G G具有一條具有一條EulerEuler通路通路L L，則在，則在

18、L L中除起點(diǎn)中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G G中僅有零個(gè)（中僅有零個(gè)（EulerEuler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。“” ” ：若若 G G沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；若若G G有兩個(gè)奇度數(shù)結(jié)點(diǎn)有兩個(gè)奇度數(shù)結(jié)點(diǎn)u u和和v v，則，則G+uvG+uv是是EulerEuler圖，從而圖，從而存在存在EulerEuler回路回路C C。從。從C C中去掉邊中去掉邊uvuv，則得到一條簡(jiǎn)單道，則得到一條簡(jiǎn)單道路路L L（起點(diǎn)（起點(diǎn)u u和終點(diǎn)和終點(diǎn)v v），且包

19、含了），且包含了G G的全部邊，即的全部邊，即L L是一是一條條EulerEuler道路。道路。注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通中每條歐拉通路的端點(diǎn)。路的端點(diǎn)。n推論推論13.1.113.1.1非平凡連通圖非平凡連通圖G GVE含有歐拉道路當(dāng)且含有歐拉道路當(dāng)且僅當(dāng)僅當(dāng)G G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院18/98/98證明：證明：“” 設(shè)設(shè)G G具有一條具有一條EulerEuler通路通路L L，則，則在在L L中除起點(diǎn)中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)和終點(diǎn)外，其余每

20、個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，所以，G G中中僅有零個(gè)僅有零個(gè)（EulerEuler回路回路）或者或者兩個(gè)兩個(gè)奇數(shù)度結(jié)點(diǎn)奇數(shù)度結(jié)點(diǎn)。“” ” ：若若 G G沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；若若G G有兩個(gè)奇度數(shù)結(jié)點(diǎn)有兩個(gè)奇度數(shù)結(jié)點(diǎn)u u和和v v，則，則G+uvG+uv是是EulerEuler圖，從而圖，從而存在存在EulerEuler回路回路C C。從。從C C中去掉邊中去掉邊uvuv，則得到一條簡(jiǎn)單道，則得到一條簡(jiǎn)單道路路L L（起點(diǎn)（起點(diǎn)u u和終點(diǎn)和終點(diǎn)v v），且包含了），且包含了G G的全部邊，即的全部邊，即L L是一是一條條EulerEuler道

21、路。道路。注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通中每條歐拉通路的端點(diǎn)。路的端點(diǎn)。n推論推論13.1.113.1.1非平凡連通圖非平凡連通圖G GVE含有歐拉道路當(dāng)且含有歐拉道路當(dāng)且僅當(dāng)僅當(dāng)G G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院19/98/98證明：證明：“” ” 設(shè)設(shè)G G具有一條具有一條EulerEuler通路通路L L，則在，則在L L中除起點(diǎn)中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G G中僅有零個(gè)（中僅有零個(gè)（EulerE

22、uler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。“” ” ：若若 G G沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；若若G G有兩個(gè)奇度數(shù)結(jié)點(diǎn)有兩個(gè)奇度數(shù)結(jié)點(diǎn)u u和和v v，則，則G+uvG+uv是是EulerEuler圖圖，從而，從而存在存在EulerEuler回路回路C C。從。從C C中去掉邊中去掉邊uvuv，則得到一條簡(jiǎn)單道，則得到一條簡(jiǎn)單道路路L L（起點(diǎn)（起點(diǎn)u u和終點(diǎn)和終點(diǎn)v v），且包含了），且包含了G G的全部邊，即的全部邊，即L L是一是一條條EulerEuler道路。道路。注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們

23、是G中每條歐拉通中每條歐拉通路的端點(diǎn)。路的端點(diǎn)。n推論推論13.1.113.1.1非平凡連通圖非平凡連通圖G GVE含有歐拉道路當(dāng)且含有歐拉道路當(dāng)且僅當(dāng)僅當(dāng)G G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院20/98/98證明：證明：“” ” 設(shè)設(shè)G G具有一條具有一條EulerEuler通路通路L L，則在，則在L L中除起點(diǎn)中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G G中僅有零個(gè)（中僅有零個(gè)（EulerEuler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。“” ” ：若若

24、 G G沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；若若G G有兩個(gè)奇度數(shù)結(jié)點(diǎn)有兩個(gè)奇度數(shù)結(jié)點(diǎn)u u和和v v，則，則G+uvG+uv是是EulerEuler圖，從而圖，從而存在存在EulerEuler回路回路C C。從。從C C中去掉邊中去掉邊uvuv，則得到一條簡(jiǎn)單道，則得到一條簡(jiǎn)單道路路L L（起點(diǎn)（起點(diǎn)u u和終點(diǎn)和終點(diǎn)v v），且包含了），且包含了G G的全部邊，即的全部邊，即L L是一是一條條EulerEuler道路。道路。注意：注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通中每條歐拉通路的端點(diǎn)。路的端點(diǎn)。n推論推論13.1.113

25、.1.1非平凡連通圖非平凡連通圖G GVE含有歐拉道路當(dāng)且含有歐拉道路當(dāng)且僅當(dāng)僅當(dāng)G G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院21/98/98例例13.213.2由由定理定理13.113.1及及推論推論13.1.113.1.1容易看出：容易看出：是歐拉圖；是歐拉圖；不是歐拉圖，但存在歐拉道路；不是歐拉圖，但存在歐拉道路；既不是歐拉圖，也不存在歐拉道路。既不是歐拉圖，也不存在歐拉道路。V V2 2V V1 1V V5 5V V3 3V V4 4(a)(a)V V2 2V V1 1V V5 5V V3 3V V4 4(b)(b)V V1 1V

26、V4 4V V2 2V V3 3(c)(c)7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院22/98/98例例13.213.2由由定理定理13.113.1及及推論推論13.1.113.1.1容易看出：容易看出：是歐拉圖；是歐拉圖；不是歐拉圖，但存在歐拉道路；不是歐拉圖，但存在歐拉道路；既不是歐拉圖，也不存在歐拉道路。既不是歐拉圖，也不存在歐拉道路。V V2 2V V1 1V V5 5V V3 3V V4 4(a)(a)V V2 2V V1 1V V5 5V V3 3V V4 4(b)(b)V V1 1V V4 4V V2 2V V3 3(c)(c)現(xiàn)在，我們是現(xiàn)在，我們是不是已經(jīng)解決不是已經(jīng)解決了哥尼斯

27、堡七了哥尼斯堡七橋問(wèn)題？橋問(wèn)題？7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院23/98/98有向圖的歐拉道路、歐拉圖有向圖的歐拉道路、歐拉圖n 定理定理13.213.2（教材（教材p165p165）有向連通圖有向連通圖G G含有有向歐拉道路，當(dāng)且僅當(dāng)含有有向歐拉道路，當(dāng)且僅當(dāng)除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大度大1 1，另一個(gè)結(jié)點(diǎn)的出度比入度大，另一個(gè)結(jié)點(diǎn)的出度比入度大1 1。）有向連通圖）有向連通圖G G含有有向歐拉回路，當(dāng)且僅當(dāng)含有有向歐拉回路，當(dāng)且僅當(dāng)G G中的所

28、有結(jié)點(diǎn)的入度等于出度。中的所有結(jié)點(diǎn)的入度等于出度。 類似于無(wú)向圖的討論，對(duì)有向圖我們有以下類似于無(wú)向圖的討論，對(duì)有向圖我們有以下結(jié)論：結(jié)論：同樣，有向同樣，有向EulerEuler圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有向向EulerEuler道路的圖道路的圖僅有零個(gè)或者僅有零個(gè)或者兩個(gè)奇度數(shù)結(jié)點(diǎn)。兩個(gè)奇度數(shù)結(jié)點(diǎn)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院24/98/98有向圖的歐拉道路、歐拉圖有向圖的歐拉道路、歐拉圖n 定理定理13.213.2（教材（教材p165p165）有向連通圖有向連通圖G G含有有向歐拉道路，當(dāng)且僅當(dāng)含有有向歐拉道路，當(dāng)且僅當(dāng)除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度

29、等于出度，除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大度大1 1，另一個(gè)結(jié)點(diǎn)的出度比入度大，另一個(gè)結(jié)點(diǎn)的出度比入度大1 1。）有向連通圖有向連通圖G G含有含有有向歐拉回路有向歐拉回路，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)G G中的中的所有結(jié)點(diǎn)的入度等于出度所有結(jié)點(diǎn)的入度等于出度。 類似于無(wú)向圖的討論，對(duì)有向圖我們有以下類似于無(wú)向圖的討論，對(duì)有向圖我們有以下結(jié)論：結(jié)論：同樣，有向同樣，有向EulerEuler圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有向向EulerEuler道路的圖道路的圖僅有零個(gè)或者僅有零個(gè)或者兩個(gè)

30、奇度數(shù)結(jié)點(diǎn)。兩個(gè)奇度數(shù)結(jié)點(diǎn)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院25/98/98有向圖的歐拉道路、歐拉圖有向圖的歐拉道路、歐拉圖n 定理定理13.213.2）有向連通圖有向連通圖G G含有有向歐拉道路，當(dāng)且僅當(dāng)含有有向歐拉道路，當(dāng)且僅當(dāng)除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大度大1 1，另一個(gè)結(jié)點(diǎn)的出度比入度大，另一個(gè)結(jié)點(diǎn)的出度比入度大1 1。）有向連通圖有向連通圖G G含有有向歐拉回路，當(dāng)且僅當(dāng)含有有向歐拉回路，當(dāng)且僅當(dāng)G G中的所有結(jié)點(diǎn)的入度等于出度。中的所有結(jié)點(diǎn)

31、的入度等于出度。 類似于無(wú)向圖的討論，對(duì)有向圖我們有以下類似于無(wú)向圖的討論，對(duì)有向圖我們有以下結(jié)論：結(jié)論：同樣，同樣，有向有向EulerEuler圖的圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有有向向EulerEuler道路道路的圖的圖僅有零個(gè)或者僅有零個(gè)或者兩個(gè)奇度數(shù)結(jié)點(diǎn)。兩個(gè)奇度數(shù)結(jié)點(diǎn)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院26/98/98例例13.313.3V V1 1V V2 2V V3 3V V4 4V V1 1V V2 2V V3 3V V4 4V V8 8V V2 2V V4 4V V6 6V V1 1V V3 3V V5 5V V7 7n 圖圖a)a)存在一條的歐拉道路：存

32、在一條的歐拉道路：v v3 3v v1 1v v2 2v v3 3v v4 4v v1 1；(a)(a)(b)(b)(c)(c)n 圖圖(b)(b)中存在歐拉回路中存在歐拉回路v v1 1v v2 2v v3 3v v4 4v v1 1v v3 3v v1 1，因而，因而(b)(b)是歐拉圖；是歐拉圖；n 圖圖(c)(c)中有歐拉回路中有歐拉回路v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v2 2v v4 4v v6 6v v8 8v v1 1因而因而(c)(c)是歐拉圖。是歐拉圖。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院27/98/98例例

33、13.413.4解解在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)b b，c c，因而存，因而存在從在從b b到到c c的歐拉通路，螞蟻乙走到的歐拉通路，螞蟻乙走到c c只要走一條歐拉通路，只要走一條歐拉通路，邊數(shù)為邊數(shù)為9 9條。而螞蟻甲要想走完所有的邊到達(dá)條。而螞蟻甲要想走完所有的邊到達(dá)c c，至少要，至少要先走一條邊到達(dá)先走一條邊到達(dá)b b，再走一條歐拉通路，因而它至少要走，再走一條歐拉通路，因而它至少要走1010條邊才能到達(dá)條邊才能到達(dá)c c，所以乙必勝。，所以乙必勝。甲、乙兩只螞蟻分別位于右圖甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)中的結(jié)點(diǎn)a a，b b處，并設(shè)圖中的邊長(zhǎng)

34、處，并設(shè)圖中的邊長(zhǎng)度是相等的。甲、乙進(jìn)行比賽：從度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過(guò)圖中的它們所在的結(jié)點(diǎn)出發(fā)，走過(guò)圖中的所有邊最后到達(dá)結(jié)點(diǎn)所有邊最后到達(dá)結(jié)點(diǎn)c c處。如果它們處。如果它們的速度相同，問(wèn)誰(shuí)先到達(dá)目的地？的速度相同，問(wèn)誰(shuí)先到達(dá)目的地？c cb(b(乙乙) )a(a(甲甲) )7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院28/98/98例例13.413.4解解 在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)b b，c c，因而存，因而存在從在從b b到到c c的歐拉通路，螞蟻乙走到的歐拉通路，螞蟻乙走到c c只要走一條歐拉通路，只要走一條歐拉通路，邊數(shù)為邊

35、數(shù)為9 9條。而螞蟻甲要想走完所有的邊到達(dá)條。而螞蟻甲要想走完所有的邊到達(dá)c c，至少要，至少要先走一條邊到達(dá)先走一條邊到達(dá)b b，再走一條歐拉通路，因而它至少要走，再走一條歐拉通路，因而它至少要走1010條邊才能到達(dá)條邊才能到達(dá)c c，所以乙必勝。，所以乙必勝。甲、乙兩只螞蟻分別位于右圖甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)中的結(jié)點(diǎn)a a，b b處，并設(shè)圖中的邊長(zhǎng)處，并設(shè)圖中的邊長(zhǎng)度是相等的。甲、乙進(jìn)行比賽：從度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過(guò)圖中的它們所在的結(jié)點(diǎn)出發(fā)，走過(guò)圖中的所有邊最后到達(dá)結(jié)點(diǎn)所有邊最后到達(dá)結(jié)點(diǎn)c c處。如果它們處。如果它們的速度相同，問(wèn)誰(shuí)先到達(dá)目的地？的

36、速度相同，問(wèn)誰(shuí)先到達(dá)目的地？c cb(b(乙乙) )a(a(甲甲) )7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院29/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEuler回路）回路）n設(shè)設(shè)G GVE是一個(gè)是一個(gè)歐拉圖歐拉圖任取任取v v0 0VV，令，令P P0 0v v0 0；設(shè)設(shè)P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法從，按下面的方法從 G GK K=E-e=E-e1 1,e,e2 2,e,ei i 中選取中選取e ei+1i+1：e ei+1i+1與與v vi i相關(guān)聯(lián)；相關(guān)聯(lián)；除非無(wú)別的邊可選取，否則除非無(wú)別的邊可

37、選取，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的橋；中的橋；當(dāng)當(dāng)G Gk k為零圖時(shí)，算法結(jié)束；否則，返回為零圖時(shí)，算法結(jié)束；否則，返回2 2。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院30/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEuler回路）回路）n設(shè)設(shè)G GVE是一個(gè)歐拉圖是一個(gè)歐拉圖任取任取v v0 0VV，令，令P P0 0v v0 0；設(shè)設(shè)P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法從，按下面的方法從 G GK K=E-e=E-e1 1,e,e2

38、 2,e,ei i 中選取中選取e ei+1i+1：e ei+1i+1與與v vi i相關(guān)聯(lián)相關(guān)聯(lián)；除非無(wú)別的邊可選取除非無(wú)別的邊可選取，否則，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的中的橋橋；當(dāng)當(dāng)G Gk k為零圖時(shí)，算法結(jié)束；否則，返回為零圖時(shí)，算法結(jié)束；否則，返回2 2。即如果即如果e ei+1i+1是割邊，是割邊，同時(shí)還有其它邊同時(shí)還有其它邊與與v vi i相關(guān)聯(lián)，則相關(guān)聯(lián)，則不能選不能選e ei+1i+17/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院31/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEule

39、r回路）回路）n設(shè)設(shè)G GVE是一個(gè)歐拉圖是一個(gè)歐拉圖任取任取v v0 0VV，令，令P P0 0v v0 0；設(shè)設(shè)P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法從，按下面的方法從 G GK K=E-e=E-e1 1,e,e2 2,e,ei i 中選取中選取e ei+1i+1：e ei+1i+1與與v vi i相關(guān)聯(lián)相關(guān)聯(lián)；除非無(wú)別的邊可選取除非無(wú)別的邊可選取，否則，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的中的橋橋；當(dāng)當(dāng)G Gk k為零圖時(shí)，算法結(jié)束；否則，返回為零圖時(shí)，算法結(jié)

40、束；否則，返回2 2。即如果即如果e ei+1i+1是割邊，是割邊，同時(shí)還有其它邊同時(shí)還有其它邊與與v vi i相關(guān)聯(lián)，則相關(guān)聯(lián)，則不能選不能選e ei+1i+1能不走能不走橋就不橋就不走橋！走橋！7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院32/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEuler回路）回路）n設(shè)設(shè)G GVE是一個(gè)歐拉圖是一個(gè)歐拉圖任取任取v v0 0VV，令，令P P0 0v v0 0；設(shè)設(shè)P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法從，按下面的方法從 G GK K=E-e=E-e1 1,e,e2 2,e,e

41、i i 中選取中選取e ei+1i+1：e ei+1i+1與與v vi i相關(guān)聯(lián)；相關(guān)聯(lián)；除非無(wú)別的邊可選取，否則除非無(wú)別的邊可選取，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的橋；中的橋；當(dāng)當(dāng)G Gk k為零圖時(shí)，算法結(jié)束；否則，返回為零圖時(shí)，算法結(jié)束；否則，返回2 2。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院33/98/98例例13.513.5v v4 4v v5 5v v6 6e e4 4e e5 5e e6 6e e1010e e9 9e e8 8e e3 3在右圖所示的歐拉圖中，某在右圖所示的歐拉圖中，某人用算法求中的歐拉回

42、路時(shí)，人用算法求中的歐拉回路時(shí)，走了簡(jiǎn)單的回路：走了簡(jiǎn)單的回路：v v2 2e e2 2v v3 3e e3 3v v4 4e e1414v v9 9e e1010v v2 2e e1 1v v1 1e e8 8v v8 8e e9 9v v2 2之后，無(wú)法行遍了，試分析在哪之后，無(wú)法行遍了，試分析在哪步他犯了錯(cuò)誤？步他犯了錯(cuò)誤？v v1 1v v3 3v v7 7e e1 1e e2 2e e7 7v ve e1 1e e1 1e e1 1e e1 1v v2 2v v4 4v v5 5v v6 6e e4 4e e5 5e e6 6e e1010e e9 9e e8 8e e3 3v v1

43、 1v v3 3v v7 7e e1 1e e2 2e e7 7v ve e1 1e e1 1e e1 1e e1 1v v2 2此人行遍此人行遍v v8 8時(shí)犯了能不走橋就不走橋的錯(cuò)時(shí)犯了能不走橋就不走橋的錯(cuò)誤，因而未能行遍出歐拉回路。當(dāng)他走到誤，因而未能行遍出歐拉回路。當(dāng)他走到v v8 8時(shí)，時(shí)，e e2 2，e e3 3，e e1414，e e1010，e e1 1，e e8 8, ,見(jiàn)右圖，此時(shí)，見(jiàn)右圖，此時(shí)，e e9 9為該圖中的橋?yàn)樵搱D中的橋，而，而e e7 7、e e1111均不是橋。因此，他不該走均不是橋。因此，他不該走e e9 9 ，而應(yīng)，而應(yīng)該走該走e e7 7或或e e1

44、111 。但在行遍。但在行遍v v3 3和和v v1 1時(shí)，也遇時(shí)，也遇到橋，為什么沒(méi)有問(wèn)題呢？到橋，為什么沒(méi)有問(wèn)題呢？v v9 9v v9 97/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院34/98/98中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題 山東師范大學(xué)，管梅谷先生山東師范大學(xué)，管梅谷先生19621962提出并解決。提出并解決。 （參考文獻(xiàn)：參考文獻(xiàn)：19621962（數(shù)學(xué)通報(bào)）（數(shù)學(xué)通報(bào)）81.10,P81.10,P3232, , ,81.5,81.5） 一個(gè)郵遞員從郵局出發(fā)，在其分管的投遞區(qū)域內(nèi)一個(gè)郵遞員從郵局出發(fā)，在其分管的投遞區(qū)域內(nèi)走遍所有的街道把郵件送到每個(gè)收件人手中，最后又走遍所有的街道把郵件送到

45、每個(gè)收件人手中，最后又回到郵局，要走怎樣的線路使全程最短。回到郵局，要走怎樣的線路使全程最短。 這個(gè)問(wèn)題用圖來(lái)表示：街道為圖這個(gè)問(wèn)題用圖來(lái)表示：街道為圖的邊，街道交叉口為圖的結(jié)點(diǎn)，的邊，街道交叉口為圖的結(jié)點(diǎn)，問(wèn)題就是要從這樣一個(gè)圖中找出問(wèn)題就是要從這樣一個(gè)圖中找出一條一條至少包含每條邊一次的總長(zhǎng)至少包含每條邊一次的總長(zhǎng)最短的回路最短的回路。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院35/98/98 對(duì)此，管梅谷曾證明，對(duì)此，管梅谷曾證明，若圖的邊數(shù)為若圖的邊數(shù)為m m，則所求回，則所求回路的長(zhǎng)度最小是路的長(zhǎng)度最小是m m，最多不超過(guò)，最多不超過(guò)2m2m，并且每條邊在其中，并且每條邊在其中最多出現(xiàn)兩次

46、最多出現(xiàn)兩次。中國(guó)郵遞員問(wèn)題，一般為在帶權(quán)連通圖。中國(guó)郵遞員問(wèn)題，一般為在帶權(quán)連通圖中找一條包括全部邊的且權(quán)最小的回路。中找一條包括全部邊的且權(quán)最小的回路。 這個(gè)問(wèn)題有著有效的解決辦法，其中最直觀的方法這個(gè)問(wèn)題有著有效的解決辦法，其中最直觀的方法之一是之一是: :把圖中的某些邊復(fù)制成兩條邊，然后在所求圖把圖中的某些邊復(fù)制成兩條邊，然后在所求圖中找一條歐拉回路。中找一條歐拉回路。 中國(guó)郵遞員問(wèn)題是運(yùn)籌學(xué)中一個(gè)典型的優(yōu)化問(wèn)題。中國(guó)郵遞員問(wèn)題是運(yùn)籌學(xué)中一個(gè)典型的優(yōu)化問(wèn)題。 顯然，當(dāng)這個(gè)圖是歐拉圖時(shí)，任何一條歐拉回路都顯然，當(dāng)這個(gè)圖是歐拉圖時(shí)，任何一條歐拉回路都符合要求；當(dāng)這個(gè)圖不是歐拉圖時(shí)，所求回路

47、必然要重復(fù)符合要求；當(dāng)這個(gè)圖不是歐拉圖時(shí)，所求回路必然要重復(fù)通過(guò)某些邊。通過(guò)某些邊。關(guān)鍵是：復(fù)制哪些邊？關(guān)鍵是：復(fù)制哪些邊？7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院36/98/98算法算法（1 1）若）若G G不含奇數(shù)度結(jié)點(diǎn)，則任一歐拉回路就是問(wèn)題的不含奇數(shù)度結(jié)點(diǎn)，則任一歐拉回路就是問(wèn)題的解決。解決。 （2 2）若）若G G含有含有2K(2K(K0K0) )個(gè)奇數(shù)度結(jié)點(diǎn)，則個(gè)奇數(shù)度結(jié)點(diǎn)，則先求出其中任何先求出其中任何兩點(diǎn)間的最短路徑兩點(diǎn)間的最短路徑，然后再在這些路徑之中找出，然后再在這些路徑之中找出K K條路條路徑徑P P1 1，P P2 2，P PK K，使得滿足以下，使得滿足以下條件條件： 任

48、何任何P Pi i和和P Pj j（ijij）沒(méi)有相同的起點(diǎn)和終點(diǎn)。）沒(méi)有相同的起點(diǎn)和終點(diǎn)。 在所滿足在所滿足的的K K條最短路徑的集合中，條最短路徑的集合中， P P1 1，P P2 2，PPK K的長(zhǎng)度總和最短。的長(zhǎng)度總和最短。（3 3）根據(jù)（）根據(jù)（2 2）中求出的）中求出的K K條最短道路條最短道路P P1 1，P P2 2，P PK K，在原圖在原圖G G中復(fù)制所有出現(xiàn)的在這條道路上的邊，設(shè)所得中復(fù)制所有出現(xiàn)的在這條道路上的邊，設(shè)所得之圖為之圖為G G。（4 4）構(gòu)造）構(gòu)造G G的歐拉回路，即得中國(guó)郵遞員問(wèn)題的解。的歐拉回路，即得中國(guó)郵遞員問(wèn)題的解。 找出需復(fù)找出需復(fù)制的邊制的邊連通

49、圖中，奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)。連通圖中，奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)。7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院37/98/98例例13.613.61 1因?yàn)橐驗(yàn)镚 G含有奇數(shù)度結(jié)點(diǎn)，所以含有奇數(shù)度結(jié)點(diǎn)，所以2 2G G中有中有2K=4(2K=4(K=2K=2) )個(gè)奇結(jié)點(diǎn)個(gè)奇結(jié)點(diǎn): : V V1 1，V V2 2，V V3 3，V V5 5。 這這4 4點(diǎn)間的距離點(diǎn)間的距離: : d(V d(V1 1,V,V2 2)=3)=3， d(Vd(V1 1,V,V3 3)=5)=5， d(Vd(V1 1,V,V5 5)=4)=4， d(Vd(V2 2,V,V3 3)=2)=2， d(Vd(V2 2,V,

50、V5 5)=3)=3， d(Vd(V3 3,V,V5 5)=4)=4各路徑各路徑:V:V1 1V V2 2(3),V(3),V3 3V V5 5(4)7(4)7 V V1 1V V3 3(5),V(5),V2 2V V5 5(3)(3)8 8 V V1 1V V5 5(4),V(4),V2 2V V3 3(2)(2)6 6兩條兩條長(zhǎng)度最短長(zhǎng)度最短P P1 1=V=V1 1V V7 7V V5 5,P,P2 2=V=V2 2V V3 33 3構(gòu)造構(gòu)造GG的任一的任一E E圖就是中國(guó)郵遞員圖就是中國(guó)郵遞員問(wèn)題的解。問(wèn)題的解。 GG7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院38/98/98Euler圖的應(yīng)

51、用圖的應(yīng)用 模數(shù)轉(zhuǎn)換問(wèn)題模數(shù)轉(zhuǎn)換問(wèn)題：設(shè)有旋轉(zhuǎn)鼓輪其表面被等分成：設(shè)有旋轉(zhuǎn)鼓輪其表面被等分成1616個(gè)部分，如圖個(gè)部分，如圖1 1所示。所示。 其中每一部分分別用絕緣體或其中每一部分分別用絕緣體或?qū)w組成，絕緣體部分給出導(dǎo)體組成，絕緣體部分給出信號(hào)信號(hào)0 0，導(dǎo)體部分給出導(dǎo)體部分給出信號(hào)信號(hào)1 1，在圖中陰影部，在圖中陰影部分表示導(dǎo)體，空白部分表示絕緣體，分表示導(dǎo)體，空白部分表示絕緣體，根據(jù)鼓輪的位置，根據(jù)鼓輪的位置，觸點(diǎn)觸點(diǎn)將得到信息將得到信息11011101，如果鼓輪沿順時(shí)針?lè)较蛐D(zhuǎn)，如果鼓輪沿順時(shí)針?lè)较蛐D(zhuǎn)一個(gè)部分，觸點(diǎn)將有信息一個(gè)部分，觸點(diǎn)將有信息10101010。問(wèn)問(wèn)鼓輪上鼓輪上16

52、16個(gè)部分怎樣安排導(dǎo)體及絕個(gè)部分怎樣安排導(dǎo)體及絕緣體，才能使鼓輪每旋轉(zhuǎn)一個(gè)部分，緣體，才能使鼓輪每旋轉(zhuǎn)一個(gè)部分，四個(gè)觸點(diǎn)能得到一組不同的四位二四個(gè)觸點(diǎn)能得到一組不同的四位二進(jìn)制數(shù)信息。進(jìn)制數(shù)信息。圖圖1 17/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院39/98/98n 設(shè)有一個(gè)設(shè)有一個(gè)八個(gè)結(jié)點(diǎn)八個(gè)結(jié)點(diǎn)的有的有向圖（向圖（圖圖2 2 ），其結(jié)點(diǎn)分），其結(jié)點(diǎn)分別 記 為 三 位 二 進(jìn) 制 數(shù)別 記 為 三 位 二 進(jìn) 制 數(shù)000000，001001，010010，011011，100100，101101，110110，111111，設(shè)設(shè)a ai i00，11，從結(jié)點(diǎn)從結(jié)點(diǎn)a a1 1a a2 2a a

53、3 3可引出兩條有向邊，可引出兩條有向邊，其終點(diǎn)分別是其終點(diǎn)分別是a a2 2a a3 30 0以及以及a a2 2a a3 31 1。該兩條邊分別記。該兩條邊分別記為為a a1 1a a2 2a a3 30 0和和a a1 1a a2 2a a3 31 1。圖圖2 27/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院40/98/98 按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有1616條條邊，在這種圖的任一條路中，其鄰接的邊必是邊，在這種圖的任一條路中，其鄰接的邊必是a a1 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，

54、即是的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊標(biāo)號(hào)的頭三位數(shù)相同。二條邊標(biāo)號(hào)的頭三位數(shù)相同。 因?yàn)閳D因?yàn)閳D2 2中中1616條邊被記成不同的二進(jìn)制數(shù)，可見(jiàn)前條邊被記成不同的二進(jìn)制數(shù)，可見(jiàn)前述鼓輪轉(zhuǎn)動(dòng)所得到述鼓輪轉(zhuǎn)動(dòng)所得到1616個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。 如如e e0 0e e1 1e e2 2e e4 4e e9 9e e3 3e e6 6e e1313e

55、e1010e e5 5e e1111e e7 7e e1515e e1414e e1212e e8 8是一條歐拉是一條歐拉回路，這回路，這1616個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列00001001101011110000100110101111。把這個(gè)序列排成環(huán)狀。把這個(gè)序列排成環(huán)狀, ,即與所求的即與所求的鼓輪相對(duì)應(yīng)。鼓輪相對(duì)應(yīng)。 7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院41/98/98 按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有1616條條邊，在這種圖的任一條路中，其鄰接的邊必是邊，在這種圖的任一條路中，其鄰接的邊必是a a1

56、 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊標(biāo)號(hào)的頭三位數(shù)相同。二條邊標(biāo)號(hào)的頭三位數(shù)相同。 因?yàn)閳D因?yàn)閳D2 2中中1616條邊被記成不同的二進(jìn)制數(shù)，可見(jiàn)前條邊被記成不同的二進(jìn)制數(shù)，可見(jiàn)前述鼓輪轉(zhuǎn)動(dòng)所得到述鼓輪轉(zhuǎn)動(dòng)所得到1616個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。 如如e

57、 e0 0e e1 1e e2 2e e4 4e e9 9e e3 3e e6 6e e1313e e1010e e5 5e e1111e e7 7e e1515e e1414e e1212e e8 8是一條歐拉是一條歐拉回路，這回路，這1616個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列00001001101011110000100110101111。把這個(gè)序列排成環(huán)狀。把這個(gè)序列排成環(huán)狀, ,即與所求的即與所求的鼓輪相對(duì)應(yīng)。鼓輪相對(duì)應(yīng)。 7/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院42/98/98 按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有

58、1616條條邊，在這種圖的任一條路中，其鄰接的邊必是邊，在這種圖的任一條路中，其鄰接的邊必是a a1 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊標(biāo)號(hào)的頭三位數(shù)相同。二條邊標(biāo)號(hào)的頭三位數(shù)相同。 因?yàn)閳D因?yàn)閳D2 2中中1616條邊被記成不同的二進(jìn)制數(shù)，可見(jiàn)前條邊被記成不同的二進(jìn)制數(shù)，可見(jiàn)前述鼓輪轉(zhuǎn)動(dòng)所得到述鼓輪轉(zhuǎn)動(dòng)所得到1616個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每

59、條邊對(duì)應(yīng)碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。 如如e e0 0e e1 1e e2 2e e4 4e e9 9e e3 3e e6 6e e1313e e1010e e5 5e e1111e e7 7e e1515e e1414e e1212e e8 8是一條歐拉是一條歐拉回路，這回路，這1616個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列00001001101011110000100110101111。把這個(gè)序列排成環(huán)狀。把這個(gè)序列排成環(huán)狀, ,即與所求的即與所求的鼓輪相對(duì)應(yīng)。鼓輪相對(duì)應(yīng)。 7/5/2022計(jì)算機(jī)學(xué)院計(jì)算

60、機(jī)學(xué)院43/98/98習(xí)題習(xí)題P P174174 5 57/5/2022計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院44/98/98哈密頓圖哈密頓圖周游世界問(wèn)題周游世界問(wèn)題 18571857（5959）年愛(ài)爾蘭數(shù)學(xué)家）年愛(ài)爾蘭數(shù)學(xué)家W.R.HamiltonW.R.Hamilton在給他朋友的一封在給他朋友的一封信中，首先談到關(guān)于十二面體的信中，首先談到關(guān)于十二面體的一個(gè)數(shù)學(xué)游戲：將左圖中的每個(gè)一個(gè)數(shù)學(xué)游戲：將左圖中的每個(gè)結(jié)點(diǎn)看成一個(gè)城市，聯(lián)結(jié)兩個(gè)結(jié)結(jié)點(diǎn)看成一個(gè)城市，聯(lián)結(jié)兩個(gè)結(jié)點(diǎn)的邊看成是交通線，他的問(wèn)題點(diǎn)的邊看成是交通線，他的問(wèn)題就是能不能找到旅行路線，沿著就是能不能找到旅行路線，沿著交通線經(jīng)過(guò)每個(gè)城市恰好一次，交通