離散數(shù)學(xué)(第13章)陳瑜

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

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

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

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

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

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

7、。為什么？為什么？7/5/2022計算機學(xué)院計算機學(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計算機學(xué)院計算機學(xué)院9/98/98n定理定理13.1 13.1 無向連通圖無向連通圖G GVE是歐拉圖當是歐拉圖當且僅當且僅當G G的的所有結(jié)點的度數(shù)都為偶數(shù)所有結(jié)

8、點的度數(shù)都為偶數(shù)。證明：證明： “ “” 設(shè)設(shè)G G是是EulerEuler圖，則圖，則G G必然存在一條包含所有邊必然存在一條包含所有邊（也包含所有結(jié)點）的回路（也包含所有結(jié)點）的回路C C，對，對 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中的兩條邊，而當中的兩條邊，而當u u又重復(fù)出現(xiàn)時，它又又重復(fù)出現(xiàn)時，它又關(guān)聯(lián)著關(guān)聯(lián)著G G中的另外的兩條邊，（為什么？）中的另外的兩條邊，（為什么？） 因而因而u u每出現(xiàn)一次，都將使得結(jié)點每出現(xiàn)一次，都將使得結(jié)點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計算機學(xué)院計算機學(xué)院10/98/98n定理定理13.1 13.1 無向連通圖無向連通圖G GVE是歐拉圖當是歐拉圖當且僅當且僅當G G的所有結(jié)點的度數(shù)都為偶數(shù)。的所有結(jié)點的度數(shù)都為偶數(shù)。證明：證明： “” 設(shè)設(shè)G G是是EulerEuler圖，則圖，則G G必然存在一條包含所有邊必然存在一條包含所有邊（也包含所有結(jié)點）的回路（也包含所有結(jié)點）的回路C C，對，對 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中的兩條邊，而當中的兩條邊，而當u u又重復(fù)出現(xiàn)時，它又又重復(fù)出現(xiàn)時，它又關(guān)聯(lián)著關(guān)聯(lián)著G G中的另外的兩條邊，（中的另外的兩條邊，（為什么？為什么？） 因而因而u u每出現(xiàn)一次，都將使得結(jié)點每出現(xiàn)一次，都將使得結(jié)點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計算機學(xué)院計算機學(xué)院11/98/98n定理定理13.1 13.1 無向連通圖無向連通圖G GVE是歐拉圖當是歐拉圖當且僅當且僅當

11、G G的所有結(jié)點的度數(shù)都為偶數(shù)。的所有結(jié)點的度數(shù)都為偶數(shù)。證明：證明： “” 設(shè)設(shè)G G是是EulerEuler圖，則圖，則G G必然存在一條包含所有邊必然存在一條包含所有邊（也包含所有結(jié)點）的回路（也包含所有結(jié)點）的回路C C，對，對 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中的兩條邊，而當中的兩條邊，而當u u又重復(fù)出現(xiàn)時，它又又重復(fù)出現(xiàn)時，它又關(guān)聯(lián)著關(guān)聯(lián)著G G中的另外的兩條邊，（中的另外的兩條邊，（為什么？為什么？） 因而因而u u每出現(xiàn)一次，都將使得結(jié)點每出現(xiàn)一次，都將使得結(jié)點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計算機學(xué)院計算機學(xué)院12/98/98“” 設(shè)連通圖設(shè)連通圖G G的結(jié)點的的結(jié)點的度數(shù)度數(shù)都是偶數(shù)，則都是偶數(shù)，則G G必必含有簡單回路含有簡單回路（可用歸納法證明可用歸納法證明） 。 設(shè)設(shè)C C是一條包含是一條包含G G中邊最多的簡單回路：中邊最多的簡單回路： 若若C C已經(jīng)包含已經(jīng)包含G G中所有的邊，則中所有的邊，則C C就是就是EulerEule

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

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

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

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

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

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

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

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

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

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

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

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

25、.1.1非平凡連通圖非平凡連通圖G GVE含有歐拉道路當且含有歐拉道路當且僅當僅當G G僅有零個或者兩個奇數(shù)度結(jié)點。僅有零個或者兩個奇數(shù)度結(jié)點。7/5/2022計算機學(xué)院計算機學(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計算機學(xué)院計算機學(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、堡七了哥尼斯堡七橋問題？橋問題？7/5/2022計算機學(xué)院計算機學(xué)院23/98/98有向圖的歐拉道路、歐拉圖有向圖的歐拉道路、歐拉圖n 定理定理13.213.2（教材（教材p165p165）有向連通圖有向連通圖G G含有有向歐拉道路，當且僅當含有有向歐拉道路，當且僅當除了兩個結(jié)點以外，其余結(jié)點的入度等于出度，除了兩個結(jié)點以外，其余結(jié)點的入度等于出度，而這兩個例外的結(jié)點中，一個結(jié)點的入度比出而這兩個例外的結(jié)點中，一個結(jié)點的入度比出度大度大1 1，另一個結(jié)點的出度比入度大，另一個結(jié)點的出度比入度大1 1。）有向連通圖）有向連通圖G G含有有向歐拉回路，當且僅當含有有向歐拉回路，當且僅當G G中的所

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

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

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

31、的入度等于出度。 類似于無向圖的討論，對有向圖我們有以下類似于無向圖的討論，對有向圖我們有以下結(jié)論：結(jié)論：同樣，同樣，有向有向EulerEuler圖的圖的結(jié)點度數(shù)都為偶數(shù)；含有結(jié)點度數(shù)都為偶數(shù)；含有有有向向EulerEuler道路道路的圖的圖僅有零個或者僅有零個或者兩個奇度數(shù)結(jié)點。兩個奇度數(shù)結(jié)點。7/5/2022計算機學(xué)院計算機學(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計算機學(xué)院計算機學(xué)院27/98/98例例

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

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

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

36、速度相同，問誰先到達目的地？c cb(b(乙乙) )a(a(甲甲) )7/5/2022計算機學(xué)院計算機學(xué)院29/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEuler回路）回路）n設(shè)設(shè)G GVE是一個是一個歐拉圖歐拉圖任取任取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)；除非無別的邊可選取，否則除非無別的邊可

37、選取，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的橋；中的橋；當當G Gk k為零圖時，算法結(jié)束；否則，返回為零圖時，算法結(jié)束；否則，返回2 2。7/5/2022計算機學(xué)院計算機學(xué)院30/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEuler回路）回路）n設(shè)設(shè)G GVE是一個歐拉圖是一個歐拉圖任取任取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)；除非無別的邊可選取除非無別的邊可選取，否則，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的中的橋橋；當當G Gk k為零圖時，算法結(jié)束；否則，返回為零圖時，算法結(jié)束；否則，返回2 2。即如果即如果e ei+1i+1是割邊，是割邊，同時還有其它邊同時還有其它邊與與v vi i相關(guān)聯(lián)，則相關(guān)聯(lián)，則不能選不能選e ei+1i+17/5/2022計算機學(xué)院計算機學(xué)院31/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEule

39、r回路）回路）n設(shè)設(shè)G GVE是一個歐拉圖是一個歐拉圖任取任取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)；除非無別的邊可選取除非無別的邊可選取，否則，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的中的橋橋；當當G Gk k為零圖時，算法結(jié)束；否則，返回為零圖時，算法結(jié)

40、束；否則，返回2 2。即如果即如果e ei+1i+1是割邊，是割邊，同時還有其它邊同時還有其它邊與與v vi i相關(guān)聯(lián)，則相關(guān)聯(lián)，則不能選不能選e ei+1i+1能不走能不走橋就不橋就不走橋！走橋！7/5/2022計算機學(xué)院計算機學(xué)院32/98/98FleuryFleury算法算法（構(gòu)造（構(gòu)造EulerEuler回路）回路）n設(shè)設(shè)G GVE是一個歐拉圖是一個歐拉圖任取任取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)；除非無別的邊可選取，否則除非無別的邊可選取，否則e ei+1i+1不應(yīng)該為不應(yīng)該為 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的橋；中的橋；當當G Gk k為零圖時，算法結(jié)束；否則，返回為零圖時，算法結(jié)束；否則，返回2 2。7/5/2022計算機學(xué)院計算機學(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、路時，人用算法求中的歐拉回路時，走了簡單的回路：走了簡單的回路：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之后，無法行遍了，試分析在哪之后，無法行遍了，試分析在哪步他犯了錯誤？步他犯了錯誤？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時犯了能不走橋就不走橋的錯時犯了能不走橋就不走橋的錯誤，因而未能行遍出歐拉回路。當他走到誤，因而未能行遍出歐拉回路。當他走到v v8 8時，時，e e2 2，e e3 3，e e1414，e e1010，e e1 1，e e8 8, ,見右圖，此時，見右圖，此時，e e9 9為該圖中的橋為該圖中的橋，而，而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時，也遇時，也遇到橋，為什么沒有問題呢？到橋，為什么沒有問題呢？v v9 9v v9 97/5/2022計算機學(xué)院計算機學(xué)院34/98/98中國郵遞員問題中國郵遞員問題 山東師范大學(xué)，管梅谷先生山東師范大學(xué)，管梅谷先生19621962提出并解決。提出并解決。 （參考文獻：參考文獻：19621962（數(shù)學(xué)通報）（數(shù)學(xué)通報）81.10,P81.10,P3232, , ,81.5,81.5） 一個郵遞員從郵局出發(fā)，在其分管的投遞區(qū)域內(nèi)一個郵遞員從郵局出發(fā)，在其分管的投遞區(qū)域內(nèi)走遍所有的街道把郵件送到每個收件人手中，最后又走遍所有的街道把郵件送到

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

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

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

48、何任何P Pi i和和P Pj j（ijij）沒有相同的起點和終點。）沒有相同的起點和終點。 在所滿足在所滿足的的K K條最短路徑的集合中，條最短路徑的集合中， P P1 1，P P2 2，PPK K的長度總和最短。的長度總和最短。（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的歐拉回路，即得中國郵遞員問題的解。的歐拉回路，即得中國郵遞員問題的解。 找出需復(fù)找出需復(fù)制的邊制的邊連通

49、圖中，奇數(shù)度結(jié)點的個數(shù)必為偶數(shù)個。連通圖中，奇數(shù)度結(jié)點的個數(shù)必為偶數(shù)個。7/5/2022計算機學(xué)院計算機學(xué)院37/98/98例例13.613.61 1因為因為G G含有奇數(shù)度結(jié)點，所以含有奇數(shù)度結(jié)點，所以2 2G G中有中有2K=4(2K=4(K=2K=2) )個奇結(jié)點個奇結(jié)點: : V V1 1，V V2 2，V V3 3，V V5 5。 這這4 4點間的距離點間的距離: : 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兩條兩條長度最短長度最短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圖就是中國郵遞員圖就是中國郵遞員問題的解。問題的解。 GG7/5/2022計算機學(xué)院計算機學(xué)院38/98/98Euler圖的應(yīng)

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

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

53、3 3可引出兩條有向邊，可引出兩條有向邊，其終點分別是其終點分別是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計算機學(xué)院計算機學(xué)院40/98/98 按照上述方法，對于八個結(jié)點的有向圖共有按照上述方法，對于八個結(jié)點的有向圖共有1616條條邊，在這種圖的任一條路中，其鄰接的邊必是邊，在這種圖的任一條路中，其鄰接的邊必是a a1 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，

54、即是的形式，即是第一條邊標號的后三位數(shù)與第第一條邊標號的后三位數(shù)與第二條邊標號的頭三位數(shù)相同。二條邊標號的頭三位數(shù)相同。 因為圖因為圖2 2中中1616條邊被記成不同的二進制數(shù)，可見前條邊被記成不同的二進制數(shù)，可見前述鼓輪轉(zhuǎn)動所得到述鼓輪轉(zhuǎn)動所得到1616個不同位置觸點上的二進制信息，個不同位置觸點上的二進制信息，即對應(yīng)于圖中的一條歐拉回路，由回路中每條邊對應(yīng)即對應(yīng)于圖中的一條歐拉回路，由回路中每條邊對應(yīng)碼的第一個符號構(gòu)成的循環(huán)序列就是所求結(jié)果。碼的第一個符號構(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個二進制數(shù)可寫成對應(yīng)的二進制數(shù)序列個二進制數(shù)可寫成對應(yīng)的二進制數(shù)序列00001001101011110000100110101111。把這個序列排成環(huán)狀。把這個序列排成環(huán)狀, ,即與所求的即與所求的鼓輪相對應(yīng)。鼓輪相對應(yīng)。 7/5/2022計算機學(xué)院計算機學(xué)院41/98/98 按照上述方法，對于八個結(jié)點的有向圖共有按照上述方法，對于八個結(jié)點的有向圖共有1616條條邊，在這種圖的任一條路中，其鄰接的邊必是邊，在這種圖的任一條路中，其鄰接的邊必是a a1

56、 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，即是第一條邊標號的后三位數(shù)與第的形式，即是第一條邊標號的后三位數(shù)與第二條邊標號的頭三位數(shù)相同。二條邊標號的頭三位數(shù)相同。 因為圖因為圖2 2中中1616條邊被記成不同的二進制數(shù)，可見前條邊被記成不同的二進制數(shù)，可見前述鼓輪轉(zhuǎn)動所得到述鼓輪轉(zhuǎn)動所得到1616個不同位置觸點上的二進制信息，個不同位置觸點上的二進制信息，即對應(yīng)于圖中的一條歐拉回路，由回路中每條邊對應(yīng)即對應(yīng)于圖中的一條歐拉回路，由回路中每條邊對應(yīng)碼的第一個符號構(gòu)成的循環(huán)序列就是所求結(jié)果。碼的第一個符號構(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個二進制數(shù)可寫成對應(yīng)的二進制數(shù)序列個二進制數(shù)可寫成對應(yīng)的二進制數(shù)序列00001001101011110000100110101111。把這個序列排成環(huán)狀。把這個序列排成環(huán)狀, ,即與所求的即與所求的鼓輪相對應(yīng)。鼓輪相對應(yīng)。 7/5/2022計算機學(xué)院計算機學(xué)院42/98/98 按照上述方法，對于八個結(jié)點的有向圖共有按照上述方法，對于八個結(jié)點的有向圖共有

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

59、條邊對應(yīng)碼的第一個符號構(gòu)成的循環(huán)序列就是所求結(jié)果。碼的第一個符號構(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個二進制數(shù)可寫成對應(yīng)的二進制數(shù)序列個二進制數(shù)可寫成對應(yīng)的二進制數(shù)序列00001001101011110000100110101111。把這個序列排成環(huán)狀。把這個序列排成環(huán)狀, ,即與所求的即與所求的鼓輪相對應(yīng)。鼓輪相對應(yīng)。 7/5/2022計算機學(xué)院計算

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