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

陳瑜Email：chenyu.inbox@g04二月2023離散數(shù)學(xué)計(jì)算機(jī)學(xué)院

第13章歐拉圖與哈密頓圖2023/2/4計(jì)算機(jī)學(xué)院2/98主要內(nèi)容(1)Euler圖及其應(yīng)用

1)歐拉道路（回路）的定義

2)如何判別歐拉圖

3)一個(gè)圖含有歐拉道路的條件

4)連通有向圖G中含有有向歐拉道路和回路的充要條件

5)Fleury算法

6)Euler圖的應(yīng)用(中國(guó)郵遞員問(wèn)題算法)2023/2/4計(jì)算機(jī)學(xué)院3/98主要內(nèi)容(2)哈密頓圖及其應(yīng)用：哈密頓道路（圈）的定義連通圖G是哈密頓圖的必要條件連通圖G是哈密頓圖的充分條件連通圖G是哈密頓圖的充要條件

哈密頓圖的應(yīng)用(推銷商問(wèn)題)2023/2/4計(jì)算機(jī)學(xué)院4/98哥尼斯堡七橋問(wèn)題

哥尼斯堡城市有一條橫貫全城的普雷格爾(Pregel)河，城的各部分用七座橋聯(lián)接，每逢假日，城中居民進(jìn)行環(huán)城逛游，這樣就產(chǎn)生了一個(gè)問(wèn)題：能不能設(shè)計(jì)一次“遍游”，使得從某地出發(fā)對(duì)每座跨河橋只走一次，而在遍歷了七橋之后卻又能回到原地？

Ab2BDCb4b1b3b5b7b62023/2/4計(jì)算機(jī)學(xué)院5/98Euler圖定義13.1

設(shè)G是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含G的每條邊的簡(jiǎn)單道路（回路）稱為該圖的一條歐拉道路（回路）。具有歐拉回路的圖稱為歐拉圖。

規(guī)定平凡圖為歐拉圖。顯然，每個(gè)歐拉圖必然是連通圖。

因此，一條歐拉道路（回路）是經(jīng)過(guò)圖中每邊一次且僅一次的道路（回路）。為什么？無(wú)重復(fù)邊復(fù)習(xí)：若道路中的所有邊e1，e2，…，ek（有向邊）互不相同，則稱此道路為簡(jiǎn)單道路；閉的簡(jiǎn)單道路稱為回路。2023/2/4計(jì)算機(jī)學(xué)院6/98Euler圖定義13.1

設(shè)G是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含G的每條邊的簡(jiǎn)單道路（回路）稱為該圖的一條歐拉道路（回路）。具有歐拉回路的圖稱為歐拉圖。

規(guī)定平凡圖為歐拉圖。

顯然，每個(gè)歐拉圖必然是連通圖。

因此，一條歐拉道路（回路）是經(jīng)過(guò)圖中每邊一次且僅一次的道路（回路）。為什么？2023/2/4計(jì)算機(jī)學(xué)院7/98Euler圖定義13.1

設(shè)G是一個(gè)無(wú)孤立結(jié)點(diǎn)的圖，包含G的每條邊的簡(jiǎn)單道路（回路）稱為該圖的一條歐拉道路（回路）。具有歐拉回路的圖稱為歐拉圖。規(guī)定平凡圖為歐拉圖。顯然，每個(gè)歐拉圖必然是連通圖。

因此，一條歐拉道路（回路）是經(jīng)過(guò)圖中每邊一次且僅一次的道路（回路）。為什么？2023/2/4計(jì)算機(jī)學(xué)院8/98例13.1v5v1v2v3v4a)v5v1v2v3v4b)v4v1v2v3c)

圖a是歐拉圖；圖b不是歐拉圖，但存在歐拉道路；圖c不存在歐拉道路。2023/2/4計(jì)算機(jī)學(xué)院9/98定理13.1無(wú)向連通圖G＝<V，E>是歐拉圖當(dāng)且僅當(dāng)G的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)。證明：“”

設(shè)G是Euler圖，則G必然存在一條包含所有邊（也包含所有結(jié)點(diǎn)）的回路C，對(duì)uV，u必然在C中出現(xiàn)一次（可出現(xiàn)多次），每出現(xiàn)u一次，都關(guān)聯(lián)著G中的兩條邊，而當(dāng)u又重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)著G中的另外的兩條邊，（為什么？）因而u每出現(xiàn)一次，都將使得結(jié)點(diǎn)u的度數(shù)增加2度，若u在通路中重復(fù)出現(xiàn)j次，則deg(u)＝2j。即u的度數(shù)必為偶數(shù)。2023/2/4計(jì)算機(jī)學(xué)院10/98定理13.1無(wú)向連通圖G＝<V，E>是歐拉圖當(dāng)且僅當(dāng)G的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)。證明：

“”

設(shè)G是Euler圖，則G必然存在一條包含所有邊（也包含所有結(jié)點(diǎn)）的回路C，對(duì)uV，u必然在C中出現(xiàn)一次（可出現(xiàn)多次），每出現(xiàn)u一次，都關(guān)聯(lián)著G中的兩條邊，而當(dāng)u又重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)著G中的另外的兩條邊，（為什么？）

因而u每出現(xiàn)一次，都將使得結(jié)點(diǎn)u的度數(shù)增加2度，若u在通路中重復(fù)出現(xiàn)j次，則deg(u)＝2j。即u的度數(shù)必為偶數(shù)。2023/2/4計(jì)算機(jī)學(xué)院11/98定理13.1無(wú)向連通圖G＝<V，E>是歐拉圖當(dāng)且僅當(dāng)G的所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)。證明：

“”

設(shè)G是Euler圖，則G必然存在一條包含所有邊（也包含所有結(jié)點(diǎn)）的回路C，對(duì)uV，u必然在C中出現(xiàn)一次（可出現(xiàn)多次），每出現(xiàn)u一次，都關(guān)聯(lián)著G中的兩條邊，而當(dāng)u又重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)著G中的另外的兩條邊，（為什么？）

因而u每出現(xiàn)一次，都將使得結(jié)點(diǎn)u的度數(shù)增加2度，若u在通路中重復(fù)出現(xiàn)j次，則deg(u)＝2j。即u的度數(shù)必為偶數(shù)。由于在回路C中邊不可能重復(fù)出現(xiàn)2023/2/4計(jì)算機(jī)學(xué)院12/98“”

設(shè)連通圖G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G必含有簡(jiǎn)單回路（可用歸納法證明）。

設(shè)C是一條包含G中邊最多的簡(jiǎn)單回路：⑴若C已經(jīng)包含G中所有的邊，則C就是Euler回路，結(jié)論成立。⑵若C不能包含G中所有的邊，則刪邊子圖

G-E（C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。

由于G是連通的，C中應(yīng)至少存在一點(diǎn)v，使G-E（C）中有一條包含v的回路C′。（見示意圖）2023/2/4計(jì)算機(jī)學(xué)院13/98“”

設(shè)連通圖G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G必含有簡(jiǎn)單回路（可用歸納法證明）。

設(shè)C是一條包含G中邊最多的簡(jiǎn)單回路：⑴若C已經(jīng)包含G中所有的邊，則C就是Euler回路，結(jié)論成立。⑵若C不能包含G中所有的邊，則刪邊子圖

G-E（C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。

由于G是連通的，C中應(yīng)至少存在一點(diǎn)v，使G-E（C）中有一條包含v的回路C′。（見示意圖）2023/2/4計(jì)算機(jī)學(xué)院14/98“”

設(shè)連通圖G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G必含有簡(jiǎn)單回路（可用歸納法證明）。設(shè)C是一條包含G中邊最多的簡(jiǎn)單回路：⑴若C已經(jīng)包含G中所有的邊，則C就是Euler回路，結(jié)論成立。⑵若C不能包含G中所有的邊，則刪邊子圖

G-E（C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。

由于G是連通的，C中應(yīng)至少存在一點(diǎn)v，使G-E（C）中有一條包含v的回路C′。（見示意圖）2023/2/4計(jì)算機(jī)學(xué)院15/98“”

設(shè)連通圖G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G必含有簡(jiǎn)單回路（可用歸納法證明）。設(shè)C是一條包含G中邊最多的簡(jiǎn)單回路：⑴

若C已經(jīng)包含G中所有的邊，則C就是Euler回路，結(jié)論成立。⑵

若C不能包含G中所有的邊，則刪邊子圖

G-E（C）仍然無(wú)奇數(shù)度結(jié)點(diǎn)。

由于G是連通的，C中應(yīng)至少存在一點(diǎn)v，使G-E（C）中有一條包含v的回路C′。（見示意圖）2023/2/4計(jì)算機(jī)學(xué)院16/98

這樣，就可以構(gòu)造出一條由C和C′組成的G的回路，其包含的邊數(shù)比C多，與假設(shè)矛盾。因此，C必是Euler回路，結(jié)論成立。2023/2/4計(jì)算機(jī)學(xué)院17/98證明：“”設(shè)G具有一條Euler通路L，則在L中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G中僅有零個(gè)（Euler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)?！啊保孩湃鬐沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；⑵若G有兩個(gè)奇度數(shù)結(jié)點(diǎn)u和v，則G+uv是Euler圖，從而存在Euler回路C。從C中去掉邊uv，則得到一條簡(jiǎn)單道路L（起點(diǎn)u和終點(diǎn)v），且包含了G的全部邊，即L是一條Euler道路。注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通路的端點(diǎn)。推論13.1.1非平凡連通圖G＝<V，E>含有歐拉道路當(dāng)且僅當(dāng)G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院18/98證明：“”

設(shè)G具有一條Euler通路L，則在L中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G中僅有零個(gè)（Euler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)?！啊保孩湃鬐沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；⑵若G有兩個(gè)奇度數(shù)結(jié)點(diǎn)u和v，則G+uv是Euler圖，從而存在Euler回路C。從C中去掉邊uv，則得到一條簡(jiǎn)單道路L（起點(diǎn)u和終點(diǎn)v），且包含了G的全部邊，即L是一條Euler道路。注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通路的端點(diǎn)。推論13.1.1非平凡連通圖G＝<V，E>含有歐拉道路當(dāng)且僅當(dāng)G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院19/98證明：“”設(shè)G具有一條Euler通路L，則在L中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G中僅有零個(gè)（Euler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)?！啊保孩湃?/p>

G沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；⑵若G有兩個(gè)奇度數(shù)結(jié)點(diǎn)u和v，則G+uv是Euler圖，從而存在Euler回路C。從C中去掉邊uv，則得到一條簡(jiǎn)單道路L（起點(diǎn)u和終點(diǎn)v），且包含了G的全部邊，即L是一條Euler道路。注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通路的端點(diǎn)。推論13.1.1非平凡連通圖G＝<V，E>含有歐拉道路當(dāng)且僅當(dāng)G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院20/98證明：“”設(shè)G具有一條Euler通路L，則在L中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G中僅有零個(gè)（Euler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)?！啊保孩湃鬐沒(méi)有奇度數(shù)結(jié)點(diǎn)，則結(jié)論顯然成立；⑵若G有兩個(gè)奇度數(shù)結(jié)點(diǎn)u和v，則G+uv是Euler圖，從而存在Euler回路C。從C中去掉邊uv，則得到一條簡(jiǎn)單道路L（起點(diǎn)u和終點(diǎn)v），且包含了G的全部邊，即L是一條Euler道路。注意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通路的端點(diǎn)。推論13.1.1非平凡連通圖G＝<V，E>含有歐拉道路當(dāng)且僅當(dāng)G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院21/98例13.2由定理13.1及推論13.1.1容易看出：是歐拉圖；不是歐拉圖，但存在歐拉道路；既不是歐拉圖，也不存在歐拉道路。V2V1V5V3V4(a)V2V1V5V3V4(b)V1V4V2V3(c)2023/2/4計(jì)算機(jī)學(xué)院22/98例13.2由定理13.1及推論13.1.1容易看出：是歐拉圖；不是歐拉圖，但存在歐拉道路；既不是歐拉圖，也不存在歐拉道路。V2V1V5V3V4(a)V2V1V5V3V4(b)V1V4V2V3(c)現(xiàn)在，我們是不是已經(jīng)解決了哥尼斯堡七橋問(wèn)題？2023/2/4計(jì)算機(jī)學(xué)院23/98有向圖的歐拉道路、歐拉圖定理13.2（教材p165）?。┯邢蜻B通圖G含有有向歐拉道路，當(dāng)且僅當(dāng)除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大1。ⅱ）有向連通圖G含有有向歐拉回路，當(dāng)且僅當(dāng)G中的所有結(jié)點(diǎn)的入度等于出度。

類似于無(wú)向圖的討論，對(duì)有向圖我們有以下結(jié)論：同樣，有向Euler圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有向Euler道路的圖僅有零個(gè)或者兩個(gè)奇度數(shù)結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院24/98有向圖的歐拉道路、歐拉圖定理13.2（教材p165）ⅰ）有向連通圖G含有有向歐拉道路，當(dāng)且僅當(dāng)除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大1。ⅱ）有向連通圖G含有有向歐拉回路，當(dāng)且僅當(dāng)G中的所有結(jié)點(diǎn)的入度等于出度。

類似于無(wú)向圖的討論，對(duì)有向圖我們有以下結(jié)論：同樣，有向Euler圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有向Euler道路的圖僅有零個(gè)或者兩個(gè)奇度數(shù)結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院25/98有向圖的歐拉道路、歐拉圖定理13.2

ⅰ）有向連通圖G含有有向歐拉道路，當(dāng)且僅當(dāng)除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大1。ⅱ）有向連通圖G含有有向歐拉回路，當(dāng)且僅當(dāng)G中的所有結(jié)點(diǎn)的入度等于出度。

類似于無(wú)向圖的討論，對(duì)有向圖我們有以下結(jié)論：同樣，有向Euler圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有向Euler道路的圖僅有零個(gè)或者兩個(gè)奇度數(shù)結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院26/98例13.3V1V2V3V4V1V2V3V4V8V2V4V6V1V3V5V7圖a)存在一條的歐拉道路：v3v1v2v3v4v1；(a)(b)(c)圖(b)中存在歐拉回路v1v2v3v4v1v3v1，因而(b)是歐拉圖；圖(c)中有歐拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是歐拉圖。2023/2/4計(jì)算機(jī)學(xué)院27/98例13.4解在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c的歐拉通路，螞蟻乙走到c只要走一條歐拉通路，邊數(shù)為9條。而螞蟻甲要想走完所有的邊到達(dá)c，至少要先走一條邊到達(dá)b，再走一條歐拉通路，因而它至少要走10條邊才能到達(dá)c，所以乙必勝。甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)a，b處，并設(shè)圖中的邊長(zhǎng)度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過(guò)圖中的所有邊最后到達(dá)結(jié)點(diǎn)c處。如果它們的速度相同，問(wèn)誰(shuí)先到達(dá)目的地？cb(乙)a(甲)2023/2/4計(jì)算機(jī)學(xué)院28/98例13.4解

在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c的歐拉通路，螞蟻乙走到c只要走一條歐拉通路，邊數(shù)為9條。而螞蟻甲要想走完所有的邊到達(dá)c，至少要先走一條邊到達(dá)b，再走一條歐拉通路，因而它至少要走10條邊才能到達(dá)c，所以乙必勝。甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)a，b處，并設(shè)圖中的邊長(zhǎng)度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過(guò)圖中的所有邊最后到達(dá)結(jié)點(diǎn)c處。如果它們的速度相同，問(wèn)誰(shuí)先到達(dá)目的地？cb(乙)a(甲)2023/2/4計(jì)算機(jī)學(xué)院29/98Fleury算法（構(gòu)造Euler回路）設(shè)G＝<V，E>是一個(gè)歐拉圖任取v0∈V，令P0＝v0；設(shè)P0＝v0e1v1e2…eivi，按下面的方法從

GK=E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無(wú)別的邊可選取，否則ei+1不應(yīng)該為

Gk＝G-{e1,e2,…,ei}中的橋；當(dāng)Gk為零圖時(shí)，算法結(jié)束；否則，返回2。2023/2/4計(jì)算機(jī)學(xué)院30/98Fleury算法（構(gòu)造Euler回路）設(shè)G＝<V，E>是一個(gè)歐拉圖任取v0∈V，令P0＝v0；設(shè)P0＝v0e1v1e2…eivi，按下面的方法從

GK=E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無(wú)別的邊可選取，否則ei+1不應(yīng)該為

Gk＝G-{e1,e2,…,ei}中的橋；當(dāng)Gk為零圖時(shí)，算法結(jié)束；否則，返回2。即如果ei+1是割邊，同時(shí)還有其它邊與vi相關(guān)聯(lián)，則不能選ei+12023/2/4計(jì)算機(jī)學(xué)院31/98Fleury算法（構(gòu)造Euler回路）設(shè)G＝<V，E>是一個(gè)歐拉圖任取v0∈V，令P0＝v0；設(shè)P0＝v0e1v1e2…eivi，按下面的方法從

GK=E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無(wú)別的邊可選取，否則ei+1不應(yīng)該為

Gk＝G-{e1,e2,…,ei}中的橋；當(dāng)Gk為零圖時(shí)，算法結(jié)束；否則，返回2。即如果ei+1是割邊，同時(shí)還有其它邊與vi相關(guān)聯(lián)，則不能選ei+1能不走橋就不走橋！2023/2/4計(jì)算機(jī)學(xué)院32/98Fleury算法（構(gòu)造Euler回路）設(shè)G＝<V，E>是一個(gè)歐拉圖任取v0∈V，令P0＝v0；設(shè)P0＝v0e1v1e2…eivi，按下面的方法從

GK=E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無(wú)別的邊可選取，否則ei+1不應(yīng)該為

Gk＝G-{e1,e2,…,ei}中的橋；當(dāng)Gk為零圖時(shí)，算法結(jié)束；否則，返回2。2023/2/4計(jì)算機(jī)學(xué)院33/98例13.5v4v5v6e4e5e6e10e9e8e3

在右圖所示的歐拉圖中，某人用算法求Ｇ中的歐拉回路時(shí)，走了簡(jiǎn)單的回路：v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后，無(wú)法行遍了，試分析在哪步他犯了錯(cuò)誤？v1v3v7e1e2e7v８e1３e1２e1４e1１v2v4v5v6e4e5e6e10e9e8e3v1v3v7e1e2e7v８e1３e1２e1４e1１v2此人行遍v8時(shí)犯了能不走橋就不走橋的錯(cuò)誤，因而未能行遍出歐拉回路。當(dāng)他走到v8時(shí)，Ｇ－｛e2，e3，e14，e10，e1，e8｝,見右圖，此時(shí)，e9為該圖中的橋，而e7、e11均不是橋。因此，他不該走e9

，而應(yīng)該走e7或e11

。但在行遍v3和v1時(shí)，也遇到橋，為什么沒(méi)有問(wèn)題呢？v9v92023/2/4計(jì)算機(jī)學(xué)院34/98中國(guó)郵遞員問(wèn)題

山東師范大學(xué)，管梅谷先生1962提出并解決。（參考文獻(xiàn)：①1962（數(shù)學(xué)通報(bào)）81.10,P32,②<電子技術(shù)應(yīng)用>,81.5）

一個(gè)郵遞員從郵局出發(fā)，在其分管的投遞區(qū)域內(nèi)走遍所有的街道把郵件送到每個(gè)收件人手中，最后又回到郵局，要走怎樣的線路使全程最短。

這個(gè)問(wèn)題用圖來(lái)表示：街道為圖的邊，街道交叉口為圖的結(jié)點(diǎn)，問(wèn)題就是要從這樣一個(gè)圖中找出一條至少包含每條邊一次的總長(zhǎng)最短的回路。2023/2/4計(jì)算機(jī)學(xué)院35/98

對(duì)此，管梅谷曾證明，若圖的邊數(shù)為m，則所求回路的長(zhǎng)度最小是m，最多不超過(guò)2m，并且每條邊在其中最多出現(xiàn)兩次。中國(guó)郵遞員問(wèn)題，一般為在帶權(quán)連通圖中找一條包括全部邊的且權(quán)最小的回路。

這個(gè)問(wèn)題有著有效的解決辦法，其中最直觀的方法之一是:把圖中的某些邊復(fù)制成兩條邊，然后在所求圖中找一條歐拉回路。中國(guó)郵遞員問(wèn)題是運(yùn)籌學(xué)中一個(gè)典型的優(yōu)化問(wèn)題。

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

①任何Pi和Pj（i≠j）沒(méi)有相同的起點(diǎn)和終點(diǎn)。

②在所滿足①的K條最短路徑的集合中，

P1，P2，…PK的長(zhǎng)度總和最短。（3）根據(jù)（2）中求出的K條最短道路P1，P2，…，PK，在原圖G中復(fù)制所有出現(xiàn)的在這條道路上的邊，設(shè)所得之圖為G′。（4）構(gòu)造G′的歐拉回路，即得中國(guó)郵遞員問(wèn)題的解。找出需復(fù)制的邊連通圖中，奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)。2023/2/4計(jì)算機(jī)學(xué)院37/98例13.61．因?yàn)镚含有奇數(shù)度結(jié)點(diǎn)，所以2．G中有2K=4(K=2)個(gè)奇結(jié)點(diǎn):V1，V2，V3，V5。這4點(diǎn)間的距離:d(V1,V2)=3，d(V1,V3)=5，

d(V1,V5)=4，d(V2,V3)=2，

d(V2,V5)=3，d(V3,V5)=4各路徑:V1V2(3),V3V5(4)—7V1V3(5),V2V5(3)—8V1V5(4),V2V3(2)—6∴兩條長(zhǎng)度最短P1=V1V7V5,P2=V2V33．構(gòu)造G’的任一E圖就是中國(guó)郵遞員問(wèn)題的解。G′G2023/2/4計(jì)算機(jī)學(xué)院38/98Euler圖的應(yīng)用

模數(shù)轉(zhuǎn)換問(wèn)題：設(shè)有旋轉(zhuǎn)鼓輪其表面被等分成16個(gè)部分，如圖1所示。

其中每一部分分別用絕緣體或?qū)w組成，絕緣體部分給出信號(hào)0，導(dǎo)體部分給出信號(hào)1，在圖中陰影部分表示導(dǎo)體，空白部分表示絕緣體，根據(jù)鼓輪的位置，觸點(diǎn)將得到信息1101，如果鼓輪沿順時(shí)針?lè)较蛐D(zhuǎn)一個(gè)部分，觸點(diǎn)將有信息1010。問(wèn)鼓輪上16個(gè)部分怎樣安排導(dǎo)體及絕緣體，才能使鼓輪每旋轉(zhuǎn)一個(gè)部分，四個(gè)觸點(diǎn)能得到一組不同的四位二進(jìn)制數(shù)信息。圖12023/2/4計(jì)算機(jī)學(xué)院39/98設(shè)有一個(gè)八個(gè)結(jié)點(diǎn)的有向圖（圖2

），其結(jié)點(diǎn)分別記為三位二進(jìn)制數(shù){000，001，010，011，100，101，110，111}，設(shè)ai∈{0，1>，從結(jié)點(diǎn)a1a2a3可引出兩條有向邊，其終點(diǎn)分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。圖22023/2/4計(jì)算機(jī)學(xué)院40/98

按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊標(biāo)號(hào)的頭三位數(shù)相同。

因?yàn)閳D2中16條邊被記成不同的二進(jìn)制數(shù)，可見前述鼓輪轉(zhuǎn)動(dòng)所得到16個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一條歐拉回路，這16個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列0000100110101111。把這個(gè)序列排成環(huán)狀,即與所求的鼓輪相對(duì)應(yīng)。2023/2/4計(jì)算機(jī)學(xué)院41/98

按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊標(biāo)號(hào)的頭三位數(shù)相同。

因?yàn)閳D2中16條邊被記成不同的二進(jìn)制數(shù)，可見前述鼓輪轉(zhuǎn)動(dòng)所得到16個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。

如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一條歐拉回路，這16個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列0000100110101111。把這個(gè)序列排成環(huán)狀,即與所求的鼓輪相對(duì)應(yīng)。2023/2/4計(jì)算機(jī)學(xué)院42/98

按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊標(biāo)號(hào)的頭三位數(shù)相同。因?yàn)閳D2中16條邊被記成不同的二進(jìn)制數(shù)，可見前述鼓輪轉(zhuǎn)動(dòng)所得到16個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路，由回路中每條邊對(duì)應(yīng)碼的第一個(gè)符號(hào)構(gòu)成的循環(huán)序列就是所求結(jié)果。

如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一條歐拉回路，這16個(gè)二進(jìn)制數(shù)可寫成對(duì)應(yīng)的二進(jìn)制數(shù)序列0000100110101111。把這個(gè)序列排成環(huán)狀,即與所求的鼓輪相對(duì)應(yīng)。

2023/2/4計(jì)算機(jī)學(xué)院43/98習(xí)題P174

52023/2/4計(jì)算機(jī)學(xué)院44/98哈密頓圖周游世界問(wèn)題

1857（59）年愛爾蘭數(shù)學(xué)家W.R.Hamilton在給他朋友的一封信中，首先談到關(guān)于十二面體的一個(gè)數(shù)學(xué)游戲：將左圖中的每個(gè)結(jié)點(diǎn)看成一個(gè)城市，聯(lián)結(jié)兩個(gè)結(jié)點(diǎn)的邊看成是交通線，他的問(wèn)題就是能不能找到旅行路線，沿著交通線經(jīng)過(guò)每個(gè)城市恰好一次，再回到原來(lái)的出發(fā)地?他把這個(gè)問(wèn)題稱為周游世界問(wèn)題。

12345678910111213141516171819202023/2/4計(jì)算機(jī)學(xué)院45/98定義13.2

設(shè)G是一個(gè)連通圖，若G中存在一條包含全部結(jié)點(diǎn)的基本道路，則稱這條道路為G的哈密頓道路；若G中存在一個(gè)包含全部結(jié)點(diǎn)的圈，則稱這個(gè)圈為G的哈密頓圈；含有哈密頓圈的圖稱為哈密頓圖。規(guī)定平凡圖為哈密頓圖。哈密頓道路是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的道路中長(zhǎng)度最短的道路；哈密頓圈是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的圈中長(zhǎng)度最短的圈。2023/2/4計(jì)算機(jī)學(xué)院46/98定義13.2設(shè)G是一個(gè)連通圖，若G中存在一條包含全部結(jié)點(diǎn)的基本道路，則稱這條道路為G的哈密頓道路；若G中存在一個(gè)包含全部結(jié)點(diǎn)的圈，則稱這個(gè)圈為G的哈密頓圈；含有哈密頓圈的圖稱為哈密頓圖。規(guī)定平凡圖為哈密頓圖。哈密頓道路是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的道路中長(zhǎng)度最短的道路；哈密頓圈是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的圈中長(zhǎng)度最短的圈。2023/2/4計(jì)算機(jī)學(xué)院47/98定義13.2設(shè)G是一個(gè)連通圖，若G中存在一條包含全部結(jié)點(diǎn)的基本道路，則稱這條道路為G的哈密頓道路；若G中存在一個(gè)包含全部結(jié)點(diǎn)的圈，則稱這個(gè)圈為G的哈密頓圈；含有哈密頓圈的圖稱為哈密頓圖。規(guī)定平凡圖為哈密頓圖。哈密頓道路是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的道路中長(zhǎng)度最短的道路；哈密頓圈是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的圈中長(zhǎng)度最短的圈。2023/2/4計(jì)算機(jī)學(xué)院48/98定義13.2設(shè)G是一個(gè)連通圖，若G中存在一條包含全部結(jié)點(diǎn)的基本道路，則稱這條道路為G的哈密頓道路；若G中存在一個(gè)包含全部結(jié)點(diǎn)的圈，則稱這個(gè)圈為G的哈密頓圈；含有哈密頓圈的圖稱為哈密頓圖。規(guī)定平凡圖為哈密頓圖。哈密頓道路是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的道路中長(zhǎng)度最短的道路；哈密頓圈是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的圈中長(zhǎng)度最短的圈。2023/2/4計(jì)算機(jī)學(xué)院49/98例13.7

既存在哈密頓道路，又存在哈密頓回路，即為哈密頓圖。(a)(c)(b)ac既不存在哈密頓道路，也不存在哈密頓圈。既存在哈密頓道路，又存在哈密頓圈，即為哈密頓圖。存在哈密頓道路，但不存在哈密頓圈。(d)2023/2/4計(jì)算機(jī)學(xué)院50/98定理13.3

設(shè)無(wú)向連通圖G＝<V,E>是哈密頓圖，S是V的任意非空真子集，則(G-S)≤|S|

其中(G-S)是從G中刪除S后所得到圖的連通分支數(shù)。證明：設(shè)C是G的一個(gè)哈密頓圈，則對(duì)

S(≠)V，有(C-S)≤|S|∵C-S是G-S的一個(gè)生成子圖

∴(G-S)≤(C-S)≤|S|2023/2/4計(jì)算機(jī)學(xué)院51/98定理13.3

設(shè)無(wú)向連通圖G＝<V,E>是哈密頓圖，S是V的任意非空真子集，則(G-S)≤|S|

其中(G-S)是從G中刪除S后所得到圖的連通分支數(shù)。證明：設(shè)C是G的一個(gè)哈密頓圈，則對(duì)

S(≠)V，有

(C-S)≤|S|

∵

C-S是G-S的一個(gè)生成子圖

∴

(G-S)≤(C-S)≤|S|為什么？2023/2/4計(jì)算機(jī)學(xué)院52/98注意定理13.3在應(yīng)用中它本身用處不大，但它的逆否命題卻非常有用。我們經(jīng)常利用定理13.3的逆否命題來(lái)判斷某些圖不是哈密頓圖，即：若存在V的某個(gè)非空子集V1使得(G-V1)＞|V1|，則G不是哈密頓圖。例如在右圖中取V1=｛a,c｝，則(G-V1)＝4＞|V1|＝2，因而該圖不是哈密頓圖。定理13.3給出的是哈密頓圖的必要條件，而不是充分條件。下圖所示的彼得森圖，對(duì)V的任意非空子集V1，均滿足(G-V1)≤|V1|，但它不是哈密頓圖。2023/2/4計(jì)算機(jī)學(xué)院53/98注意定理13.3在應(yīng)用中它本身用處不大，但它的逆否命題卻非常有用。我們經(jīng)常利用定理13.3的逆否命題來(lái)判斷某些圖不是哈密頓圖，即：若存在V的某個(gè)非空子集V1使得(G-V1)＞|V1|，則G不是哈密頓圖。例如在右圖中取V1=｛a,c｝，則(G-V1)＝4＞|V1|＝2，因而該圖不是哈密頓圖。定理13.3給出的是哈密頓圖的必要條件，而不是充分條件。下圖所示的彼得森圖，對(duì)V的任意非空子集V1，均滿足(G-V1)≤|V1|，但它不是哈密頓圖。ca2023/2/4計(jì)算機(jī)學(xué)院54/98定理13.4

設(shè)G＝<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖。如果對(duì)任意兩個(gè)結(jié)點(diǎn)u,v∈V，均有deg(u)+deg(v)≥n-1

則G中存在哈密頓道路。證明：首先證明滿足上述條件的G是連通圖。否則G至少有兩支，即

G1＝<V1，E1>和G2＝<V2，E2>

對(duì)v1∈V1，v2∈V2，顯然deg(v1)＋deg(v2)≤|V1|-1+|V2|-1=n-2

與已知矛盾，故G是連通的。2023/2/4計(jì)算機(jī)學(xué)院55/98定理13.4

設(shè)G＝<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖。如果對(duì)任意兩個(gè)結(jié)點(diǎn)u,v∈V，均有deg(u)+deg(v)≥n-1

則G中存在哈密頓道路。證明：首先證明滿足上述條件的G是連通圖。否則G至少有兩支，即

G1＝<V1，E1>和G2＝<V2，E2>

對(duì)v1∈V1，v2∈V2，

顯然deg(v1)＋deg(v2)≤|V1|-1+|V2|-1=n-2

與已知矛盾，故G是連通的。2023/2/4計(jì)算機(jī)學(xué)院56/98定理13.4

設(shè)G＝<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖。如果對(duì)任意兩個(gè)結(jié)點(diǎn)u,v∈V，均有deg(u)+deg(v)≥n-1

則G中存在哈密頓道路。證明：首先證明滿足上述條件的G是連通圖。否則G至少有兩支，即

G1＝<V1，E1>和G2＝<V2，E2>

對(duì)v1∈V1，v2∈V2，

顯然

deg(v1)＋deg(v2)≤|V1|-1+|V2|-1=n-2

與已知矛盾，故G是連通的。2023/2/4計(jì)算機(jī)學(xué)院57/98證明(續(xù)1)

其次，證明G中存在哈密頓道路。

設(shè)L＝v1v2…vk為G中最長(zhǎng)的一條基本道路，顯然k≤n。若k＝n，則L為G中經(jīng)過(guò)所有結(jié)點(diǎn)的道路，即為哈密頓道路。若k＜n，由L的最長(zhǎng)性可知，v1和vk的全部鄰接點(diǎn)都在L上。若v1vkE，則v1v2…vkv1就構(gòu)成G的一個(gè)包含L的圈。若v1vkE，則存在L上的結(jié)點(diǎn)vi，使得2023/2/4計(jì)算機(jī)學(xué)院58/98證明(續(xù)1)

其次，證明G中存在哈密頓道路。

設(shè)L＝v1v2…vk為G中最長(zhǎng)的一條基本道路，顯然k≤n。若k＝n，則L為G中經(jīng)過(guò)所有結(jié)點(diǎn)的道路，即為哈密頓道路。若k＜n，由L的最長(zhǎng)性可知，v1和vk的全部鄰接點(diǎn)都在L上。若v1vkE，則v1v2…vkv1就構(gòu)成G的一個(gè)包含L的圈。若v1vkE，則存在L上的結(jié)點(diǎn)vi，使得2023/2/4計(jì)算機(jī)學(xué)院59/98證明(續(xù)1)

其次，證明G中存在哈密頓道路。設(shè)L＝v1v2…vk為G中最長(zhǎng)的一條基本道路，顯然k≤n。若k＝n，則L為G中經(jīng)過(guò)所有結(jié)點(diǎn)的道路，即為哈密頓道路。若k＜n，由L的最長(zhǎng)性可知，v1和vk的全部鄰接點(diǎn)都在L上。若v1vkE，則v1v2…vkv1就構(gòu)成G的一個(gè)包含L的圈。若v1vkE，則存在L上的結(jié)點(diǎn)vi，使得2023/2/4計(jì)算機(jī)學(xué)院60/98證明(續(xù)1)

其次，證明G中存在哈密頓道路。設(shè)L＝v1v2…vk為G中最長(zhǎng)的一條基本道路，顯然k≤n。若k＝n，則L為G中經(jīng)過(guò)所有結(jié)點(diǎn)的道路，即為哈密頓道路。若k＜n，由L的最長(zhǎng)性可知，v1和vk的全部鄰接點(diǎn)都在L上。若v1vkE，則v1v2…vkv1就構(gòu)成G的一個(gè)包含L的圈。若v1vkE，則存在L上的結(jié)點(diǎn)vi，使得Why?2023/2/4計(jì)算機(jī)學(xué)院61/98證明(續(xù)1)

其次，證明G中存在哈密頓道路。設(shè)L＝v1v2…vk為G中最長(zhǎng)的一條基本道路，顯然k≤n。若k＝n，則L為G中經(jīng)過(guò)所有結(jié)點(diǎn)的道路，即為哈密頓道路。若k＜n，由L的最長(zhǎng)性可知，v1和vk的全部鄰接點(diǎn)都在L上。若v1vkE，則v1v2…vkv1就構(gòu)成G的一個(gè)包含L的圈。若v1vkE，則存在L上的結(jié)點(diǎn)vi，使得2023/2/4計(jì)算機(jī)學(xué)院62/98證明(續(xù)2)

v1viEvi-1vkE。（否則，即對(duì)viL，v1viE而vi-1vkE。設(shè)v1在L上與vi1，vi2，…，vit相鄰（t≥2），則vk不能與vi1-1,vi2-1,…,vit-1中的任何一個(gè)相鄰，這樣就有d(vk)≤k-t-1，d(v1)=t，d(v1)+d(vk)≤k-1＜n-1。推出矛盾。）這樣就可以構(gòu)造一個(gè)圈

C＝v1v2…vi-1vkvk-1…viv1。如圖所示，這個(gè)圈包含了L中的全部結(jié)點(diǎn)。v1vkvivi-1vjvk-12023/2/4計(jì)算機(jī)學(xué)院63/98證明(續(xù)2)

v1viEvi-1vkE。（否則，即對(duì)viL，v1viE而vi-1vkE。設(shè)v1在L上與vi1，vi2，…，vit相鄰（t≥2），則vk不能與vi1-1,vi2-1,…,vit-1中的任何一個(gè)相鄰，這樣就有d(vk)≤k-t-1，d(v1)=t，d(v1)+d(vk)≤k-1＜n-1。推出矛盾。）這樣就可以構(gòu)造一個(gè)圈

C＝v1v2…vi-1vkvk-1…viv1。如圖所示，這個(gè)圈包含了L中的全部結(jié)點(diǎn)。v1vkvivi-1vjvk-12023/2/4計(jì)算機(jī)學(xué)院64/98證明(續(xù)2)

v1viEvi-1vkE。（否則，即對(duì)viL，v1viE而vi-1vkE。設(shè)v1在L上與vi1，vi2，…，vit相鄰（t≥2），則vk不能與vi1-1,vi2-1,…,vit-1中的任何一個(gè)相鄰，這樣就有d(vk)≤k-t-1，d(v1)=t，d(v1)+d(vk)≤k-1＜n-1。推出矛盾。）這樣就可以構(gòu)造一個(gè)圈

C＝v1v2…vi-1vkvk-1…viv1。v1vkvivi-1vjvk-1如圖所示，這個(gè)圈包含了L中的全部結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院65/98證明(續(xù)2)

v1viEvi-1vkE。（否則，即對(duì)viL，v1viE而vi-1vkE。設(shè)v1在L上與vi1，vi2，…，vit相鄰（t≥2），則vk不能與vi1-1,vi2-1,…,vit-1中的任何一個(gè)相鄰，這樣就有d(vk)≤k-t-1，d(v1)=t，d(v1)+d(vk)≤k-1＜n-1。推出矛盾。）這樣就可以構(gòu)造一個(gè)圈

C＝v1v2…vi-1vkvk-1…viv1。v1vkvivi-1vjvk-1如圖所示，這個(gè)圈包含了L中的全部結(jié)點(diǎn)。2023/2/4計(jì)算機(jī)學(xué)院66/98證明(續(xù)3)

這樣，對(duì)a）和b），都可以構(gòu)造一個(gè)包含L中的全部結(jié)點(diǎn)的一個(gè)圈C。

因?yàn)閗＜n，所以V中還有一些結(jié)點(diǎn)不在C中，由G的連通性知，存在C外的結(jié)點(diǎn)u與C上結(jié)點(diǎn)vj相鄰。顯然，可以構(gòu)造一條基本道路P′＝uvjvj+1…vi-1vkvk-1…viv1v2…vj-1。P′比P長(zhǎng)，與L的最長(zhǎng)性相矛盾。所以，必然k=n，即L必是G的一條哈密頓道路。由此可以看到，本定理的證明方法是一種構(gòu)造性證明方法。v1vkvivi-1vj2023/2/4計(jì)算機(jī)學(xué)院67/98證明(續(xù)3)

這樣，對(duì)a）和b），都可以構(gòu)造一個(gè)包含L中的全部結(jié)點(diǎn)的一個(gè)圈C。

因?yàn)閗＜n，所以V中還有一些結(jié)點(diǎn)不在C中，由G的連通性知，存在C外的結(jié)點(diǎn)u與C上結(jié)點(diǎn)vj相鄰。顯然，可以構(gòu)造一條基本道路P′＝uvjvj+1…vi-1vkvk-1…viv1v2…vj-1。P′比P長(zhǎng)，與L的最長(zhǎng)性相矛盾。

所以，必然k=n，即L必是G的一條哈密頓道路。由此可以看到，本定理的證明方法是一種構(gòu)造性證明方法。v1vkvivi-1vju2023/2/4計(jì)算機(jī)學(xué)院68/98證明(續(xù)3)

這樣，對(duì)a）和b），都可以構(gòu)造一個(gè)包含L中的全部結(jié)點(diǎn)的一個(gè)圈C。因?yàn)閗＜n，所以V中還有一些結(jié)點(diǎn)不在C中，由G的連通性知，存在C外的結(jié)點(diǎn)u與C上結(jié)點(diǎn)vj相鄰。顯然，可以構(gòu)造一條基本道路P′＝uvjvj+1…vi-1vkvk-1…viv1v2…vj-1。P′比P長(zhǎng)，與L的最長(zhǎng)性相矛盾。

所以，必然k=n，即L必是G的一條哈密頓道路。由此可以看到，本定理的證明方法是一種構(gòu)造性證明方法。v1vkvivi-1vju2023/2/4計(jì)算機(jī)學(xué)院69/98證明(續(xù)3)

這樣，對(duì)a）和b），都可以構(gòu)造一個(gè)包含L中的全部結(jié)點(diǎn)的一個(gè)圈C。因?yàn)閗＜n，所以V中還有一些結(jié)點(diǎn)不在C中，由G的連通性知，存在C外的結(jié)點(diǎn)u與C上結(jié)點(diǎn)vj相鄰。顯然，可以構(gòu)造一條基本道路P′＝uvjvj+1…vi-1vkvk-1…viv1v2…vj-1。P′比P長(zhǎng)，與L的最長(zhǎng)性相矛盾。所以，必然k=n，即L必是G的一條哈密頓道路。由此可以看到，本定理的證明方法是一種構(gòu)造性證明方法。2023/2/4計(jì)算機(jī)學(xué)院70/98定理13.5設(shè)G＝<V,E>是具有n個(gè)結(jié)點(diǎn)（n≥3）的簡(jiǎn)單圖。如果對(duì)任意的兩個(gè)結(jié)點(diǎn)u,v∈V，均有：deg(u)+deg(v)≥n，則G必是哈密頓圖。（教材170）

證明：利用已知條件，仿照定理13.4中b）的方法，可構(gòu)造出一個(gè)包含所有結(jié)點(diǎn)的哈密頓圈。(略)

定理13.5給出的是哈密頓圖的充分條件，而不是必要條件。在六邊形中，任意兩個(gè)結(jié)點(diǎn)的度數(shù)之和都是4＜6，但六邊形是哈密頓圖。2023/2/4計(jì)算機(jī)學(xué)院71/98定理13.5設(shè)G＝<V,E>是具有n個(gè)結(jié)點(diǎn)（n≥3）的簡(jiǎn)單圖。如果對(duì)任意的兩個(gè)結(jié)點(diǎn)u,v∈V，均有：deg(u)+deg(v)≥n，則G必是哈密頓圖。證明：利用已知條件，仿照定理13.4中b）的方法，可構(gòu)造出一個(gè)包含所有結(jié)點(diǎn)的哈密頓圈。

定理13.5給出的是哈密頓圖的充分條件，而不是必要條件。例如，在六邊形中，任意兩個(gè)結(jié)點(diǎn)的度數(shù)之和都是4＜6，但六邊形是哈密頓圖。2023/2/4計(jì)算機(jī)學(xué)院72/98例13.8某地有5個(gè)風(fēng)景點(diǎn)，若每個(gè)風(fēng)景點(diǎn)均有兩條道路與其他點(diǎn)相通。問(wèn)游人可否經(jīng)過(guò)每個(gè)風(fēng)景點(diǎn)恰好一次而游完這5處？

解：將5個(gè)風(fēng)景點(diǎn)看成是有5個(gè)結(jié)點(diǎn)的無(wú)向圖，兩風(fēng)景點(diǎn)間的道路看成是無(wú)向圖的邊，因?yàn)槊刻幘袃蓷l道路與其他結(jié)點(diǎn)相通，故每個(gè)結(jié)點(diǎn)的度數(shù)均為2，從而任意兩個(gè)結(jié)點(diǎn)的度數(shù)之和等于4，正好為總結(jié)點(diǎn)數(shù)減1。故此圖中存在一條哈密頓道路，因此本題有解。2023/2/4計(jì)算機(jī)學(xué)院73/98例13.8某地有5個(gè)風(fēng)景點(diǎn)，若每個(gè)風(fēng)景點(diǎn)均有兩條道路與其他點(diǎn)相通。問(wèn)游人可否經(jīng)過(guò)每個(gè)風(fēng)景點(diǎn)恰好一次而游完這5處？解：將5個(gè)風(fēng)景點(diǎn)看成是有5個(gè)結(jié)點(diǎn)的無(wú)向圖，兩風(fēng)景點(diǎn)間的道路看成是無(wú)向圖的邊，因?yàn)槊刻幘袃蓷l道路與其他結(jié)點(diǎn)相通，故每個(gè)結(jié)點(diǎn)的度數(shù)均為2，從而任意兩個(gè)結(jié)點(diǎn)的度數(shù)之和等于4，正好為總結(jié)點(diǎn)數(shù)減1。故此圖中存在一條哈密頓道路，因此本題有解。2023/2/4計(jì)算機(jī)學(xué)院74/98例13.9證明下圖(a)所示的圖中，不存在哈密頓圈。證明

在圖(a)中，刪除結(jié)點(diǎn)子集V1＝{a,b,c}，得到圖(b)，在圖(b)中，它的連通分支為4，顯然有：(G-V1)＝4＞|V1|＝3。由定理13.3可知：圖(a)所示的圖中不會(huì)存在哈密頓圈，即不是哈密頓圖。dabcfeihj(a)jhdfei(b)2023/2/4計(jì)算機(jī)學(xué)院75/98例13.10

判斷右圖所示的圖是否存在哈密頓圈。

解：若該圖中存在哈密頓圈，則該圈組成的圖中任何結(jié)點(diǎn)的度數(shù)均為2。因而結(jié)點(diǎn)1、2、3、4、5所關(guān)聯(lián)的邊均在圈中，于是在結(jié)點(diǎn)a、b、c、d、e處均應(yīng)將不與1、2、3、4、5關(guān)聯(lián)的邊刪除，而要?jiǎng)h除與結(jié)點(diǎn)a、b、c、d、e關(guān)聯(lián)的其他邊，這樣一來(lái)，圖就不連通了，因而圖中不存在哈密頓圈。abcde123452023/2/4計(jì)算機(jī)學(xué)院76/98例13.10

判斷右圖所示的圖是否存在哈密頓圈。

解：若該圖中存在哈密頓圈，則該圈組成的圖中任何結(jié)點(diǎn)的度數(shù)均為2。因而結(jié)點(diǎn)1、2、3、4、5所關(guān)聯(lián)的邊均在圈中，于是在結(jié)點(diǎn)a、b、c、d、e處均應(yīng)將不與1、2、3、4、5關(guān)聯(lián)的邊刪除，而要?jiǎng)h除與結(jié)點(diǎn)a、b、c、d、e關(guān)聯(lián)的其他邊，這樣一來(lái)，圖就不連通了，因而圖中不存在哈密頓圈。abcde123452023/2/4計(jì)算機(jī)學(xué)院77/98例13.10

判斷右圖所示的圖是否存在哈密頓圈。

解：若該圖中存在哈密頓圈，則該圈組成的圖中任何結(jié)點(diǎn)的度數(shù)均為2。因而結(jié)點(diǎn)1、2、3、4、5所關(guān)聯(lián)的邊均在圈中，于是在結(jié)點(diǎn)a、b、c、d、e處均應(yīng)將不與1、2、3、4、5關(guān)聯(lián)的邊刪除，而要?jiǎng)h除與結(jié)點(diǎn)a、b、c、d、e關(guān)聯(lián)的其他邊，這樣一來(lái)，圖就不連通了，因而圖中不存在哈密頓圈。abcde123452023/2/4計(jì)算機(jī)學(xué)院78/98圖的閉包定理13.5的條件很強(qiáng)，有些圖雖然不直接滿足這個(gè)條件，但可以通過(guò)在一定條件下加邊的辦法來(lái)滿足這個(gè)條件。定義13.3設(shè)G＝<V,E>是n階的簡(jiǎn)單圖。若存在一對(duì)不相鄰的結(jié)點(diǎn)u,v∈V，滿足：

deg(u)+deg(v)≥n則構(gòu)造圖G+uv，并且在圖上G+uv重復(fù)上述步驟，直至不再存在這樣的結(jié)點(diǎn)對(duì)為止，所得之圖稱為圖G的閉包，記為c(G)。2023/2/4計(jì)算機(jī)學(xué)院79/98圖的閉包定理13.5的條件很強(qiáng)，有些圖雖然不直接滿足這個(gè)條件，但可以通過(guò)在一定條件下加邊的辦法來(lái)滿足這個(gè)條件。定義13.3

設(shè)G＝<V,E>是n階的簡(jiǎn)單圖。若存在一對(duì)不相鄰的結(jié)點(diǎn)u,v∈V，滿足：

deg(u)+deg(v)≥n

則構(gòu)造圖G+uv，并且在圖上G+uv重復(fù)上述步驟，直至不再存在這樣的結(jié)點(diǎn)對(duì)為止，所得之圖稱為圖G的閉包，記為c(G)。2023/2/4計(jì)算機(jī)學(xué)院80/98定理13.6一個(gè)簡(jiǎn)單圖G是哈密頓圖當(dāng)且僅當(dāng)其閉包圖是哈密頓圖。

證明：首先證明，若u,v是G的兩個(gè)非鄰接結(jié)點(diǎn)且deg(u)+deg(v)≥n，則G是哈密頓圖當(dāng)且僅當(dāng)G+uv是哈密頓圖。必要性是顯然的?，F(xiàn)證充分性，即G+uv是哈密頓圖，則G中必然存在一條以u(píng)為起點(diǎn)，v為終點(diǎn)的哈密頓道路L，仿照定理13.4的證明過(guò)程，由L可以構(gòu)造一個(gè)哈密頓圈，即G也是一個(gè)哈密頓圖。這樣，在構(gòu)造c(G)的過(guò)程中，所得的圖與G同為哈密頓圖或同不為哈密頓圖，所以結(jié)論成立。2023/2/4計(jì)算機(jī)學(xué)院81/98定理13.6一個(gè)簡(jiǎn)單圖G是哈密頓圖當(dāng)且僅當(dāng)其閉包圖是哈密頓圖。

證明：

首先證明，若u,v是G的兩個(gè)非鄰接結(jié)點(diǎn)且deg(u)+deg(v)≥n，則G是哈密頓圖當(dāng)且僅當(dāng)G+uv是哈密頓圖。必要性是顯然的?，F(xiàn)證充分性，即G+uv是哈密頓圖，則G中必然存在一條以u(píng)為起點(diǎn)，v為終點(diǎn)的哈密頓道路L，仿照定理13.4的證明過(guò)程，由L可以構(gòu)造一個(gè)哈密頓圈，即G也是一個(gè)哈密頓圖。

這樣，在構(gòu)造c(G)的過(guò)程中，所得的圖與G同為哈密頓圖或同不為哈密頓圖，所以結(jié)論成立。2023/2/4計(jì)算機(jī)學(xué)院82/98定理13.6一個(gè)簡(jiǎn)單圖G是哈密頓圖當(dāng)且僅當(dāng)其閉包圖是哈密頓圖。

證明：

首先證明，若u,v是G的兩個(gè)非鄰接結(jié)點(diǎn)且deg(u)+deg(v)≥n，則G是哈密頓圖當(dāng)且僅當(dāng)G+uv是哈密頓圖。必要性是顯然的。現(xiàn)證充分性，即G+uv是哈密頓圖，則G中必然存在一條以u(píng)為起點(diǎn)，v為終點(diǎn)的哈密頓道路L，仿照定理13.4的證明過(guò)程，由L可以構(gòu)造一個(gè)哈密頓圈，即G也是一個(gè)哈密頓圖。

這樣，在構(gòu)造c(G)的過(guò)程中，所得的圖與G同為哈密頓圖或同不為哈密頓圖，所以結(jié)論成立。2023/2/4計(jì)算機(jī)學(xué)院83/98定理13.6一個(gè)簡(jiǎn)單圖G是哈密頓圖當(dāng)且僅當(dāng)其閉包圖是哈密頓圖。

證明：

首先證明，若u,v是G的兩個(gè)非鄰接結(jié)點(diǎn)且deg(u)+deg(v)≥n，則G是哈密頓圖當(dāng)且僅當(dāng)G+uv是哈密頓圖。必要性是顯然的?，F(xiàn)證充分性，即G+uv是哈密頓圖，則G中必然存在一條以u(píng)為起點(diǎn)，v為終點(diǎn)的哈密頓道路L，仿照定理13.4的證明過(guò)程，由L可以構(gòu)造一個(gè)哈密頓圈，即G也是一個(gè)哈密頓圖。這樣，在構(gòu)造c(G)的過(guò)程中，所得的圖與G同為哈密頓圖或同不為哈密頓圖，所以結(jié)論成立。2023/2/4計(jì)算機(jī)學(xué)院84/98定理13.7

設(shè)G＝<V,E>是一個(gè)n階無(wú)環(huán)的連通平面圖。若G含有哈密頓圈C，則：其中和分別是含在圈C內(nèi)部和外部的i