第15章歐拉圖與哈密頓圖

1、1第十五章第十五章 歐拉圖與哈密頓圖歐拉圖與哈密頓圖主要內(nèi)容主要內(nèi)容l 歐拉圖歐拉圖l 哈密頓圖哈密頓圖l 帶權(quán)圖與貨郎擔(dān)問(wèn)題帶權(quán)圖與貨郎擔(dān)問(wèn)題215.1 歐拉圖歐拉圖歷史背景：哥尼斯堡七橋問(wèn)題與歐拉圖歷史背景：哥尼斯堡七橋問(wèn)題與歐拉圖要求邊不重復(fù)地一筆畫出整個(gè)圖要求邊不重復(fù)地一筆畫出整個(gè)圖3歐拉圖定義歐拉圖定義定義定義15.1 (1) 歐拉通路歐拉通路經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的通路點(diǎn)的通路. (2) 歐拉回歐拉回路路經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的回路點(diǎn)的回路.(3) 歐拉圖歐拉圖具有歐拉回路的圖具

2、有歐拉回路的圖.(4) 半歐拉圖半歐拉圖具有歐拉通路而無(wú)歐拉回路的圖具有歐拉通路而無(wú)歐拉回路的圖.幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：規(guī)定平凡圖為歐拉圖規(guī)定平凡圖為歐拉圖.歐拉通路是生成的簡(jiǎn)單通路，歐拉回路是生成的簡(jiǎn)單回路歐拉通路是生成的簡(jiǎn)單通路，歐拉回路是生成的簡(jiǎn)單回路.環(huán)不影響圖的歐拉性環(huán)不影響圖的歐拉性.4上圖中，上圖中，(1) ,(4) 為歐拉圖，為歐拉圖，(2),(5)為半歐拉圖，為半歐拉圖，(3),(6)既不是歐拉圖，也不是半歐拉圖既不是歐拉圖，也不是半歐拉圖. 在在(3),(6)中各至少加幾條邊才能成為歐拉圖？中各至少加幾條邊才能成為歐拉圖？ 歐拉圖實(shí)例歐拉圖實(shí)例5無(wú)向歐拉圖的判別法無(wú)向歐拉圖的

3、判別法定理定理15.1 無(wú)向圖無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)G連通且無(wú)奇度數(shù)頂點(diǎn)連通且無(wú)奇度數(shù)頂點(diǎn).證證 若若G 為平凡圖為平凡圖,顯然成立，無(wú)問(wèn)題顯然成立，無(wú)問(wèn)題. 下設(shè)下設(shè)G為為 n 階階 m 條邊的無(wú)向圖條邊的無(wú)向圖.必要性必要性 因因G是歐拉圖，所以是歐拉圖，所以G中存在歐拉回路，設(shè)中存在歐拉回路，設(shè)C 為為G 中中一條歐拉回路一條歐拉回路.(1) G 連通顯然連通顯然.(2) vi V(G)，vi在在C上每出現(xiàn)一次獲上每出現(xiàn)一次獲2度，所以度，所以vi為偶度頂點(diǎn)為偶度頂點(diǎn). 由由vi 的任意性，結(jié)論為真的任意性，結(jié)論為真. 充分性充分性 對(duì)邊數(shù)對(duì)邊數(shù)m做歸納法（第二數(shù)學(xué)歸納

4、法）做歸納法（第二數(shù)學(xué)歸納法）.(1) m=1時(shí)，時(shí)，G為一個(gè)環(huán)，則為一個(gè)環(huán)，則G為歐拉圖為歐拉圖.(2) 設(shè)設(shè)m k（k 1）時(shí)結(jié)論為真，）時(shí)結(jié)論為真，m=k+1時(shí)如下證明：時(shí)如下證明：6無(wú)向歐拉圖的判別法無(wú)向歐拉圖的判別法（a）制造滿足歸納假設(shè)的若干個(gè)小歐拉圖）制造滿足歸納假設(shè)的若干個(gè)小歐拉圖. 由連通及無(wú)奇度數(shù)頂點(diǎn)可知，由連通及無(wú)奇度數(shù)頂點(diǎn)可知， (G) 2， 用擴(kuò)大路徑法可得用擴(kuò)大路徑法可得G中長(zhǎng)度中長(zhǎng)度 3的圈的圈C1. 刪除刪除C1上所有的邊（不破壞上所有的邊（不破壞G中頂點(diǎn)度數(shù)的奇偶性）得中頂點(diǎn)度數(shù)的奇偶性）得G的的生成子圖生成子圖G ，則，則G 無(wú)奇度頂點(diǎn)，無(wú)奇度頂點(diǎn)， 設(shè)它有

5、設(shè)它有s（s 1）個(gè)連通分支）個(gè)連通分支G1 , G2 , , Gs , 它們的邊數(shù)均它們的邊數(shù)均 k，且無(wú)且無(wú)奇度數(shù)頂點(diǎn)奇度數(shù)頂點(diǎn)，由歸納法假設(shè)，因而它們都是小歐由歸納法假設(shè)，因而它們都是小歐拉圖拉圖. 設(shè)設(shè)C1 , C2 , , Cs 是是G1 , G2 , , Gs 的歐拉回路的歐拉回路. （b）將）將C1上被刪除的邊還原，從上被刪除的邊還原，從C1上某一頂點(diǎn)出發(fā)走出上某一頂點(diǎn)出發(fā)走出G的的一條歐拉回路一條歐拉回路C.例例1 哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題4個(gè)奇度頂點(diǎn)個(gè)奇度頂點(diǎn), 不存在不存在 歐拉通路歐拉通路, 更不存在歐拉回路更不存在歐拉回路。7PLAY從以上證明不難看出：歐拉圖是

6、若干個(gè)邊不重的圈之從以上證明不難看出：歐拉圖是若干個(gè)邊不重的圈之并，見(jiàn)示意圖并，見(jiàn)示意圖3. 8歐拉圖的判別法歐拉圖的判別法定理定理15.2 無(wú)向圖無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)G 連通且恰有兩個(gè)奇度連通且恰有兩個(gè)奇度頂點(diǎn)頂點(diǎn).證證 必要性簡(jiǎn)單必要性簡(jiǎn)單. 設(shè)設(shè)G是是m條邊的條邊的n階無(wú)向圖，因階無(wú)向圖，因G是半歐拉圖，是半歐拉圖，存在歐拉通回存在歐拉通回(但不存在歐拉回路但不存在歐拉回路)， 設(shè)為設(shè)為 ， (1) 若若v不是不是 的端點(diǎn)，設(shè)它在的端點(diǎn)，設(shè)它在 中出現(xiàn)中出現(xiàn)k次，每次獲得次，每次獲得2度，故度，故d(v)=2k, (2)若若v是是 的端點(diǎn)，的端點(diǎn)， 由于由于2個(gè)端

7、點(diǎn)是不同的且不相個(gè)端點(diǎn)是不同的且不相鄰，鄰，v作為端點(diǎn)只能出現(xiàn)一次，獲得作為端點(diǎn)只能出現(xiàn)一次，獲得1度，它還可能作為非端度，它還可能作為非端點(diǎn)出現(xiàn)若干次，每次獲得點(diǎn)出現(xiàn)若干次，每次獲得2度，故度，故d(v)為奇數(shù)。為奇數(shù)。充分性（利用定理充分性（利用定理15.1）設(shè)設(shè)u,v為為G 中的兩個(gè)奇度頂點(diǎn)，令中的兩個(gè)奇度頂點(diǎn)，令 G =G (u,v)則則G 連通且無(wú)奇度頂點(diǎn)，由定理連通且無(wú)奇度頂點(diǎn)，由定理15.1知知G 為歐拉圖，因而為歐拉圖，因而存在歐拉回路存在歐拉回路C，令，令 =C (u,v)，則，則 為為 G 中歐拉通路中歐拉通路.9有向歐拉圖的判別法有向歐拉圖的判別法定理定理15.3 有向圖

8、有向圖D是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度都等于出度點(diǎn)的入度都等于出度.本定理的證明類似于定理本定理的證明類似于定理15.1. 定理定理15.4 有向圖有向圖D是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且是單向連通的，且D中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1，另一個(gè)，另一個(gè)的出度比入度大的出度比入度大1，而其余頂點(diǎn)的入度都等于出度，而其余頂點(diǎn)的入度都等于出度. 本定理的證明類似于定理本定理的證明類似于定理15.1. 定理定理15.5 G是非平凡的歐拉圖當(dāng)且僅當(dāng)是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通

9、的且為若干是連通的且為若干個(gè)邊不重的圈之并個(gè)邊不重的圈之并. 可用歸納法證定理可用歸納法證定理15.5. 10例題例題例例15.1 設(shè)設(shè)G是歐拉圖，但是歐拉圖，但G不是平凡圖，也不是一個(gè)環(huán)，則不是平凡圖，也不是一個(gè)環(huán)，則 (G) 2.證證 只需證明只需證明G中不可能有橋（如何證明？）中不可能有橋（如何證明？）上圖中，上圖中，(1),(2)兩兩圖都是歐拉圖，均從圖都是歐拉圖，均從A點(diǎn)出發(fā)，如何點(diǎn)出發(fā)，如何一次成功地走出一條歐拉回路來(lái)？一次成功地走出一條歐拉回路來(lái)？ (1) (2)11Fleury算法算法算法：算法：(1) 任取任取v0 V(G)，令，令P0=v0. (2) 設(shè)設(shè)Pi = v0e1

10、v1e2eivi 已經(jīng)行遍，按下面方法從已經(jīng)行遍，按下面方法從 E(G) e1,e2,ei 中選取中選取ei+1： (a) ei+1與與vi 相關(guān)聯(lián)；相關(guān)聯(lián)； (b) 除非無(wú)別的邊可供行遍，否則除非無(wú)別的邊可供行遍，否則ei+1不應(yīng)該為不應(yīng)該為 Gi = G e1,e2,ei 中的橋中的橋. (3) 當(dāng)當(dāng) (2)不能再進(jìn)行時(shí)，算法停止不能再進(jìn)行時(shí)，算法停止.可以證明算法停止時(shí)所得簡(jiǎn)單通路可以證明算法停止時(shí)所得簡(jiǎn)單通路 Pm = v0e1v1e2emvm(vm=v0)為為G 中一條歐拉回路中一條歐拉回路. 用用Fleury算法走出上一頁(yè)圖算法走出上一頁(yè)圖(1),(2)從從A出發(fā)（其實(shí)從任何一點(diǎn)出

11、發(fā)（其實(shí)從任何一點(diǎn)出發(fā)都可以）的歐拉回路各一條出發(fā)都可以）的歐拉回路各一條. 1215.2 哈密頓圖哈密頓圖歷史背景：哈密頓周游世界問(wèn)題與哈密頓圖歷史背景：哈密頓周游世界問(wèn)題與哈密頓圖 (1) (2) 每個(gè)頂點(diǎn)是一個(gè)城市每個(gè)頂點(diǎn)是一個(gè)城市, , 有有20個(gè)城市個(gè)城市, , 要求從一個(gè)城市出要求從一個(gè)城市出發(fā)發(fā), , 恰好經(jīng)過(guò)每一個(gè)城市一次恰好經(jīng)過(guò)每一個(gè)城市一次, , 回到出發(fā)點(diǎn)回到出發(fā)點(diǎn). .13哈密頓圖與半哈密頓圖哈密頓圖與半哈密頓圖定義定義15.2 (1) 哈密頓通路哈密頓通路經(jīng)過(guò)圖中所有頂點(diǎn)一次僅一次的通路經(jīng)過(guò)圖中所有頂點(diǎn)一次僅一次的通路.(2) 哈密頓回路哈密頓回路經(jīng)過(guò)圖中所有頂點(diǎn)一次

12、僅一次的回路經(jīng)過(guò)圖中所有頂點(diǎn)一次僅一次的回路.(3) 哈密頓圖哈密頓圖具有哈密頓回路的圖具有哈密頓回路的圖.(4) 半哈密頓圖半哈密頓圖具有哈密頓通路且無(wú)哈密頓回路的圖具有哈密頓通路且無(wú)哈密頓回路的圖.幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：平凡圖是哈密頓圖平凡圖是哈密頓圖.哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路.環(huán)與平行邊不影響哈密頓性環(huán)與平行邊不影響哈密頓性.哈密頓圖的實(shí)質(zhì)是能將圖中的所有頂點(diǎn)排在同一個(gè)圈上哈密頓圖的實(shí)質(zhì)是能將圖中的所有頂點(diǎn)排在同一個(gè)圈上14實(shí)例實(shí)例在上圖中，在上圖中，(1),(2) 是哈密頓圖是哈密頓圖;(3)是半哈密頓圖是半哈密頓圖;(4)既不

13、是哈密頓圖，也不是半哈密頓圖，為什么？既不是哈密頓圖，也不是半哈密頓圖，為什么？15無(wú)向哈密頓圖的一個(gè)必要條件無(wú)向哈密頓圖的一個(gè)必要條件定理定理15.6 設(shè)無(wú)向圖設(shè)無(wú)向圖G=是哈密頓圖，對(duì)于任意是哈密頓圖，對(duì)于任意V1 V且且V1，均有，均有 p(G V1) |V1|證證 設(shè)設(shè)C為為G中一條哈密頓回路，當(dāng)中一條哈密頓回路，當(dāng)V1中頂點(diǎn)在中頂點(diǎn)在C上均不相鄰時(shí)，上均不相鄰時(shí)， p(C V1)達(dá)到最大值達(dá)到最大值|V1|，而當(dāng)，而當(dāng)V1中頂點(diǎn)在中頂點(diǎn)在C上有彼此相鄰的上有彼此相鄰的情況時(shí)，均有情況時(shí)，均有 p(C V1)|V1|，從而，從而(1) p(C V1) |V1| 而而C是是G的生成子圖，

14、所以的生成子圖，所以(2) p(G V1) p(C V1) |V1| （因?yàn)椋ㄒ驗(yàn)镃 G）定理定理15.6中的條件是哈密頓圖的必要條件，但不是充分條件中的條件是哈密頓圖的必要條件，但不是充分條件（彼得松圖）（彼得松圖）16無(wú)向哈密頓圖的一個(gè)必要條件無(wú)向哈密頓圖的一個(gè)必要條件推論推論 設(shè)無(wú)向圖設(shè)無(wú)向圖G=是半哈密頓圖，對(duì)于任意的是半哈密頓圖，對(duì)于任意的V1 V且且V1均有均有 p(G V1) |V1|+1證證 令令 uv為為G中哈密頓通路，令中哈密頓通路，令G = G (u,v)，則，則G 為哈為哈密頓圖密頓圖. 于是于是 p(G V1) = p(G V1 (u,v) |V1|+117幾點(diǎn)說(shuō)明幾

15、點(diǎn)說(shuō)明l 由定理由定理15.6立刻可知，立刻可知，Kr,s當(dāng)當(dāng)s r+1時(shí)不是哈密頓圖時(shí)不是哈密頓圖. 易知易知Kr,r（r 2）時(shí)都是哈密頓圖，）時(shí)都是哈密頓圖，Kr,r+1都是半哈密頓圖都是半哈密頓圖. l 常利用定理常利用定理15.6判斷某些圖判斷某些圖不是不是哈密頓圖哈密頓圖.例例2 設(shè)設(shè)G為為n階無(wú)向連通簡(jiǎn)單圖，若階無(wú)向連通簡(jiǎn)單圖，若G中有割點(diǎn)或橋，則中有割點(diǎn)或橋，則G不不 是哈密頓圖是哈密頓圖.證證 設(shè)設(shè)v為割點(diǎn)，則為割點(diǎn)，則 p(G v) 2|v|=1. K2有橋，它顯然不是哈密頓圖有橋，它顯然不是哈密頓圖. 除除K2外，其他有橋的圖外，其他有橋的圖（連通的）均有割點(diǎn)（連通的）均

16、有割點(diǎn).其實(shí)，本例對(duì)非簡(jiǎn)單連通圖也對(duì)其實(shí)，本例對(duì)非簡(jiǎn)單連通圖也對(duì).18例15.3 ，為了應(yīng)用定理定理15.6及推論，及推論，問(wèn)頂點(diǎn)V1是如何得到的呢？一般地：設(shè)二部圖G=,|V1|V2|,且|V1|2, |V2|2,由定理15.6及其他推論可以得出下面結(jié)論：(1)若G是哈密頓圖哈密頓圖,則則 |V1|=|V2|,(2)若若G半哈密頓圖半哈密頓圖,則則 |V2|=|V1|+1(3)若|V2| |V1|+2,則G不是哈密頓圖哈密頓圖,也不是半哈密頓圖也不是半哈密頓圖19無(wú)向哈密頓圖的一個(gè)充分條件無(wú)向哈密頓圖的一個(gè)充分條件定理定理15.7 設(shè)設(shè)G是是n階無(wú)向簡(jiǎn)單圖，若對(duì)于任意不相鄰的頂點(diǎn)階無(wú)向簡(jiǎn)單圖

17、，若對(duì)于任意不相鄰的頂點(diǎn)vi,vj，均有，均有 d(vi)+d(vj) n 1 ( )則則G 中存在哈密頓通路中存在哈密頓通路. 證明線索：證明線索：(1) 由由( )證證G連通連通(2) = v1v2vl 為為G中極大路徑中極大路徑. 若若l = n, 證畢證畢. (3) 否則，證否則，證G 中存在過(guò)中存在過(guò) 上所有頂點(diǎn)的圈上所有頂點(diǎn)的圈C，由，由(1) 知知C外頂外頂點(diǎn)存在與點(diǎn)存在與C上某頂點(diǎn)相鄰頂點(diǎn)，從而得比上某頂點(diǎn)相鄰頂點(diǎn)，從而得比 更長(zhǎng)的路徑，重更長(zhǎng)的路徑，重復(fù)復(fù)(2) (3) ，最后得，最后得G中哈密頓通路中哈密頓通路. 20證明證明證（著重關(guān)鍵步驟）證（著重關(guān)鍵步驟）(1) 由由

18、( )及簡(jiǎn)單圖的性質(zhì)，用反證法證明及簡(jiǎn)單圖的性質(zhì)，用反證法證明G連通連通.(2) = v1v2vl 為極大路徑，為極大路徑，l n, 若若l = n（結(jié)束）（結(jié)束）.下面討論下面討論ln的情況，即要證的情況，即要證G中存在過(guò)中存在過(guò) 上所有頂點(diǎn)的圈上所有頂點(diǎn)的圈. 若若(v1,vl)在在G中，則中，則(u,v)為為G中圈中圈 否則，設(shè)否則，設(shè)v1與與 上上 相鄰，則相鄰，則k 2 (否則由否則由極大路徑端點(diǎn)性質(zhì)及極大路徑端點(diǎn)性質(zhì)及( )，會(huì)得到，會(huì)得到d(v1)+d(vl) 1+l 2n 1)，又又vl 至少與至少與 左邊相鄰頂點(diǎn)之一相鄰左邊相鄰頂點(diǎn)之一相鄰(寫出理由寫出理由)，設(shè)設(shè) 與與vl

19、相鄰，見(jiàn)圖中相鄰，見(jiàn)圖中(1) ，于是得，于是得G中回路中回路C (1)中圖去中圖去掉邊掉邊( ) ) kiiivvv,.,32kiiivvvv,.,2121rivrriivv,121 證明證明圖圖(1)圖圖(2)(3) 由連通性，可得比由連通性，可得比 更長(zhǎng)的路徑（如圖更長(zhǎng)的路徑（如圖(2) 所示），所示），對(duì)它再擴(kuò)大路徑，重復(fù)對(duì)它再擴(kuò)大路徑，重復(fù)(2) ，最后得哈密頓通路，最后得哈密頓通路.22推論推論推論推論 設(shè)設(shè)G為為n (n 3) 階無(wú)向簡(jiǎn)單圖，若對(duì)于階無(wú)向簡(jiǎn)單圖，若對(duì)于G中任意兩個(gè)中任意兩個(gè)不相鄰的頂點(diǎn)不相鄰的頂點(diǎn)vi,vj，均有，均有 d(vi)+d(vj) n （）則則G中存在

20、哈密頓回路，從而中存在哈密頓回路，從而G為哈密頓圖為哈密頓圖.證明線索：由定理證明線索：由定理15.7得得 = v1v2vn 為為G中哈密頓通路中哈密頓通路. 若若(v1,vn) E(G)，得證，得證. 否則利用（否則利用（）證明存在過(guò)）證明存在過(guò)v1, v2, vn的圈的圈(此圈即為哈密頓回路此圈即為哈密頓回路). 定理定理15.8 設(shè)設(shè)u,v為為n階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖G中兩個(gè)不相鄰的頂點(diǎn)，中兩個(gè)不相鄰的頂點(diǎn)，且且d(u)+d(v) n，則，則G為哈密頓圖當(dāng)且僅當(dāng)為哈密頓圖當(dāng)且僅當(dāng)G (u,v)為哈密頓為哈密頓圖圖. 23幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明定理定理15.7是半哈密頓圖的充分條件，但不是必要

21、條件是半哈密頓圖的充分條件，但不是必要條件. 長(zhǎng)度長(zhǎng)度為為n 1（n 4）的路徑構(gòu)成的圖不滿足（）的路徑構(gòu)成的圖不滿足（ ）條件，但它顯）條件，但它顯然是半哈密頓圖然是半哈密頓圖.定理定理15.7的推論同樣不是哈密頓圖的必要條件，的推論同樣不是哈密頓圖的必要條件，G為長(zhǎng)為為長(zhǎng)為n的的圈，不滿足（圈，不滿足（）條件，但它當(dāng)然是哈密頓圖）條件，但它當(dāng)然是哈密頓圖.由定理由定理15.7的推論可知，的推論可知，Kn（n 3）均為哈密頓圖）均為哈密頓圖.24應(yīng)用實(shí)例應(yīng)用實(shí)例例例15.4 某次國(guó)際會(huì)議某次國(guó)際會(huì)議8人參加，人參加，他們來(lái)自不同的他們來(lái)自不同的國(guó)家。已知他們中任何兩人無(wú)共同語(yǔ)言的人，國(guó)家。已

22、知他們中任何兩人無(wú)共同語(yǔ)言的人，與其余有與其余有共同語(yǔ)言共同語(yǔ)言的人數(shù)之和大于或等于的人數(shù)之和大于或等于8，試證明：能將這試證明：能將這8 人人排在同一張圓桌就座，使排在同一張圓桌就座，使得每個(gè)人都能與兩邊的人交談？得每個(gè)人都能與兩邊的人交談？解解 作無(wú)向圖作無(wú)向圖G=, 其中其中V=v|v為與會(huì)者為與會(huì)者， E=(u,v) | u,v V, u與與v有共同語(yǔ)言有共同語(yǔ)言, 且且u v. G為為8階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖. d(v)為與為與v有共同語(yǔ)言的人數(shù)有共同語(yǔ)言的人數(shù). 根據(jù)已知條件根據(jù)已知條件, u,v V, 有有d(u)+d(v) 8. 由定理由定理15.7的推論的推論 ，可知，可知

23、G中存在哈密頓回路中存在哈密頓回路. 服務(wù)員在服務(wù)員在G中找一條哈密頓回路中找一條哈密頓回路C，按，按C中相鄰關(guān)中相鄰關(guān)系安排座位即可系安排座位即可. 25競(jìng)賽圖競(jìng)賽圖競(jìng)賽圖競(jìng)賽圖: 任意兩個(gè)頂點(diǎn)之間恰好有一條有向邊任意兩個(gè)頂點(diǎn)之間恰好有一條有向邊.在循環(huán)賽中在循環(huán)賽中, n個(gè)參賽隊(duì)中的任個(gè)參賽隊(duì)中的任意兩個(gè)隊(duì)比賽一次意兩個(gè)隊(duì)比賽一次, 假設(shè)沒(méi)有假設(shè)沒(méi)有平局平局, 用有向圖描述比賽結(jié)果用有向圖描述比賽結(jié)果: 頂點(diǎn)表示參賽隊(duì)頂點(diǎn)表示參賽隊(duì), A到到B有一條有一條邊當(dāng)且僅當(dāng)邊當(dāng)且僅當(dāng)A隊(duì)勝隊(duì)勝B隊(duì)隊(duì). 25ABCD26競(jìng)賽圖競(jìng)賽圖(續(xù)續(xù))定理定理 在在n(n2)階有向圖階有向圖D中中, 如果所有有

24、向邊如果所有有向邊均用無(wú)向邊代替均用無(wú)向邊代替, 所得無(wú)向圖中含生成子所得無(wú)向圖中含生成子圖圖Kn, 則有向圖則有向圖D中存在哈密頓通路中存在哈密頓通路.根據(jù)定理根據(jù)定理, 競(jìng)賽圖中一定有哈密頓通路競(jìng)賽圖中一定有哈密頓通路, 當(dāng)然當(dāng)然也可能有哈密頓回路也可能有哈密頓回路. 當(dāng)沒(méi)有哈密頓回路時(shí)當(dāng)沒(méi)有哈密頓回路時(shí), 通常只有一條哈密頓通常只有一條哈密頓通路通路, 這條通路給出參賽隊(duì)的惟一名次這條通路給出參賽隊(duì)的惟一名次. 例如例如, DABC是一條哈密頓通路是一條哈密頓通路, 它沒(méi)有哈密它沒(méi)有哈密頓回路頓回路, 比賽結(jié)果是比賽結(jié)果是D第一第一, A第二第二, B第三第三, C第四第四.26ABCD

25、27n（n 2）階競(jìng)賽圖中存在哈密頓通路）階競(jìng)賽圖中存在哈密頓通路定理定理15.9 若若D為為n（n 2）階競(jìng)賽圖，則）階競(jìng)賽圖，則D中具有哈密頓通路中具有哈密頓通路證明思路：注意，競(jìng)賽圖的基圖是無(wú)向完全圖證明思路：注意，競(jìng)賽圖的基圖是無(wú)向完全圖. 對(duì)對(duì)n（n 2）做歸納做歸納. 只需觀察下面兩個(gè)圖只需觀察下面兩個(gè)圖. 無(wú)向哈密頓圖的充分條件無(wú)向哈密頓圖的充分條件28證明：證明：設(shè)設(shè)D為為n階階競(jìng)賽圖競(jìng)賽圖，當(dāng)，當(dāng)n=2時(shí)，時(shí)，D的基圖的基圖為為K2，結(jié)論成立。，結(jié)論成立。 設(shè)設(shè)n=k時(shí)成立，現(xiàn)設(shè)時(shí)成立，現(xiàn)設(shè)n=k+1，設(shè)，設(shè)V(D)=v1,v2 ,vk,vk+1.令令D1=D-vk+1，易知

26、易知D1為為k階階競(jìng)賽圖競(jìng)賽圖，由，由歸納歸納法假設(shè)，法假設(shè)，D1存在存在哈密頓通路哈密頓通路 1 = v1v2vk , 下面證明可以擴(kuò)到下面證明可以擴(kuò)到 1中去。中去。若存在若存在vr(1 r k)使得使得E(D),i=1,2,.,r-1.且且E(D)，如圖如圖(a)所示，則所示，則 = v1v2vk+1 vrvk ,為為D中中哈密頓通路哈密頓通路.否則，對(duì)任意否則，對(duì)任意i1,2, . ,k，均有，均有E(D)，如圖，如圖(b)所示，所示，則則 = v1v2vkvk+1 ,為為D中中哈密頓通路哈密頓通路.無(wú)向哈密頓圖的充分條件無(wú)向哈密頓圖的充分條件29判斷某圖是否為哈密頓圖方法判斷某圖是否

27、為哈密頓圖方法 判斷某圖是否為哈密頓圖至今還是一個(gè)判斷某圖是否為哈密頓圖至今還是一個(gè)NP難題難題.總結(jié)判斷某圖是哈密頓圖或不是總結(jié)判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法哈密頓圖的某些可行的方法.1. 觀察出哈密頓回路觀察出哈密頓回路.例例15.5 下圖下圖(周游世界問(wèn)題周游世界問(wèn)題)是哈密頓圖是哈密頓圖易知易知a b c d e f g h i j k l m n p q r s t a為圖中的一條哈密頓回路為圖中的一條哈密頓回路.注意，此圖不滿足定理注意，此圖不滿足定理15.7推論條件推論條件.302滿足定理滿足定理15.7推論的條件（推論的條件（）.例例4 完全圖完全圖Kn (n

28、 3) 中任何兩個(gè)頂點(diǎn)中任何兩個(gè)頂點(diǎn)u,v，均有，均有 d(u)+d(v) = 2(n 1) n（n 3），），所以所以Kn為哈密頓圖為哈密頓圖. 3破壞定理破壞定理15.6的條件的圖不是哈密頓圖的條件的圖不是哈密頓圖.例例5 在四分之一國(guó)際象棋盤（在四分之一國(guó)際象棋盤（4 4方格組成）上跳馬無(wú)解方格組成）上跳馬無(wú)解.在在8 8國(guó)際象棋盤上跳馬有解國(guó)際象棋盤上跳馬有解. 判斷某圖是否為哈密頓圖方法判斷某圖是否為哈密頓圖方法 31令令V1=a, b, c, d, 則則 p(G V1) = 6 4，由定理，由定理15.6可知圖可知圖中無(wú)哈密頓回路中無(wú)哈密頓回路.在在8 8國(guó)際象棋盤上跳馬有解，試試

29、看國(guó)際象棋盤上跳馬有解，試試看. 解解 每個(gè)方格看作一個(gè)頂點(diǎn)每個(gè)方格看作一個(gè)頂點(diǎn), 2個(gè)頂點(diǎn)之間有邊當(dāng)且僅當(dāng)馬可以個(gè)頂點(diǎn)之間有邊當(dāng)且僅當(dāng)馬可以從一個(gè)方格跳到另一個(gè)方格從一個(gè)方格跳到另一個(gè)方格, 得到得到16階圖階圖G, 如左圖紅邊所示如左圖紅邊所示. 32設(shè)設(shè)GG，稱稱 為為G 的權(quán)，并記作的權(quán)，并記作W(G )，即，即 ) ()(GEeeW ) ()() (GEeewGW定義定義15.3 給定圖給定圖G = ，(G為無(wú)向圖或有向圖為無(wú)向圖或有向圖)，設(shè)，設(shè)W:ER (R為實(shí)數(shù)集為實(shí)數(shù)集)，對(duì)，對(duì)G中任意邊中任意邊e = (vi,vj) (G為有向圖為有向圖時(shí)，時(shí)，e = )，設(shè)，設(shè)W(e)

30、= wij，稱實(shí)數(shù)，稱實(shí)數(shù)wij 為邊為邊e上的上的權(quán)權(quán)，并將，并將wij標(biāo)注在邊標(biāo)注在邊e上，稱上，稱G為為帶權(quán)圖帶權(quán)圖，此時(shí)常將帶權(quán)圖，此時(shí)常將帶權(quán)圖G記作記作 . 15.3 最短路問(wèn)題最短路問(wèn)題與貨郎擔(dān)問(wèn)題與貨郎擔(dān)問(wèn)題例例 P1=v0v1v3v5, W(P1)=10, P2=v0v1v4v5, W(P2)=12, P3=v0v2v4v5, P(P3)=11.33最短路問(wèn)題最短路問(wèn)題帶權(quán)圖帶權(quán)圖G=, 其中其中w:ER. e E, w(e)稱作稱作e的的權(quán)權(quán).為非負(fù)實(shí)數(shù)，為非負(fù)實(shí)數(shù)， e=(vi,vj), 記記w(e)=wij . 若若vi,vj不相鄰不相鄰, 記記wij = .又規(guī)定又規(guī)

31、定 wii =0；通路通路L的的權(quán)權(quán): L的所有邊的權(quán)之和的所有邊的權(quán)之和, 記作記作w(L).u和和v之間的之間的最短路徑最短路徑: u和和v之間權(quán)最小的通路之間權(quán)最小的通路.從從u到到v長(zhǎng)度最短的路徑稱為從長(zhǎng)度最短的路徑稱為從u到到v的的最短路徑最短路徑，稱其長(zhǎng)度為，稱其長(zhǎng)度為從從u到到v的距離，記作的距離，記作d(u,v).約定約定d(u,u)=0;當(dāng)當(dāng)u和和v不連通（不連通（u不可達(dá)不可達(dá)v）d(u,v)=+ ;最短路徑最短路徑問(wèn)題：?jiǎn)栴}：給定給定帶權(quán)圖帶權(quán)圖G=及頂點(diǎn)及頂點(diǎn)u和和v,其中每一其中每一條邊條邊e的權(quán)為非負(fù)實(shí)數(shù)，求從的權(quán)為非負(fù)實(shí)數(shù)，求從u到到v的的 最短路徑最短路徑。不難

32、看出，如果不難看出，如果uvi1vi2,vikv是從是從u到到v的最短路徑，則對(duì)每的最短路徑，則對(duì)每一個(gè)一個(gè)t（kt1），），uvi1vi2,vit是從是從u到到vit的最短路徑的最短路徑.3434標(biāo)號(hào)法標(biāo)號(hào)法(E.W.Dijkstra, 1959)設(shè)帶權(quán)圖設(shè)帶權(quán)圖G=, 其中其中 e E, w(e) 0.設(shè)設(shè)V=v1,v2,vn, 求求v1到其余各頂點(diǎn)的最短路徑到其余各頂點(diǎn)的最短路徑1. 令令 l10, p1 , lj+ , pj , j=2,3,n, P=v1, T=V-v1, k1, t1. / 表示空表示空2. 對(duì)所有的對(duì)所有的vj T且且(vk,vj) E 令令lminlj, lk+

33、wkj, 若若l=lk+wkj, 則令則令ljl, pjvk.3. 求求li=minlj| vj T. 令令PP vi, TT-vi, ki.4. 令令tt+1, 若若tn, 則轉(zhuǎn)則轉(zhuǎn)2.35Dijkstra標(biāo)號(hào)法實(shí)例標(biāo)號(hào)法實(shí)例例例 求求v0到到v5的最短路徑的最短路徑 t v0 v1 v2 v3 v4 v5 1 (0, )* (+ , ) (+ , ) (+ , ) (+ , ) (+ , ) 2 (1,v0)* (4,v0) (+ , ) (+ , ) (+ , ) 3 (3,v1)* (8,v1) (6,v1) (+ , ) 4 (8,v1) (4,v2)* (+ , ) 5 (7,v4

34、)* (10,v4) 6 (9,v3)*v0到到v5的最短路徑的最短路徑: v0v1v2v4v3v5 , d(v0,v5)=936Dijkstra標(biāo)號(hào)法實(shí)例標(biāo)號(hào)法實(shí)例P304t v1 v2v3 v4 v5 v6 v71 (0, v1) (+ , v1) (+ , v1) (+ , v1) (+ , v1) (+ , v1) (+ , v1)2 (3, v1) (7, v1)(5, v1) (+ , v1) (+ , v1) (+ , v1)3 (5, v2) (5, v1) (9, v2) (+ , v1) (+ , v1)4(5, v1) (8, v3) (+ , v1) (+ , v1)5

35、 (8, v3) (7, v4) (13, v4)6 (8, v3) (9, v6)7 (9, v6)例：例： 求求v1到其余各點(diǎn)的最短到其余各點(diǎn)的最短路徑和距離。路徑和距離。v1到到v7的最短路徑的最短路徑: v1v4v6v7 , d(v1,v7)=9v1到到v5的最短路徑的最短路徑: v1v2v3v5 , d(v1,v5)=8*v1(0,v1)v2(3,v1)v3(5,v2)v4(5,v1)v5(8,v3)v7(9,v6)v6(7,v4)37貨郎擔(dān)問(wèn)題貨郎擔(dān)問(wèn)題 貨郎擔(dān)問(wèn)題貨郎擔(dān)問(wèn)題(旅行商問(wèn)題旅行商問(wèn)題): 有有n n個(gè)城市個(gè)城市, ,給定給定城市城市之間道路之間道路的長(zhǎng)度（長(zhǎng)度可以為的

36、長(zhǎng)度（長(zhǎng)度可以為 ，對(duì)應(yīng)這兩個(gè)，對(duì)應(yīng)這兩個(gè)城市城市之間無(wú)交通線），之間無(wú)交通線），一個(gè)一個(gè)旅行商從某個(gè)旅行商從某個(gè)城市出發(fā)城市出發(fā), , 要要經(jīng)過(guò)每個(gè)城市一次經(jīng)過(guò)每個(gè)城市一次且僅且僅一次一次, , 最后最后回到出發(fā)回到出發(fā)的的城市城市, ,問(wèn)如何走才能使他走的路線問(wèn)如何走才能使他走的路線最短？最短？設(shè)設(shè)G=為一個(gè)為一個(gè)n階完全帶權(quán)圖階完全帶權(quán)圖Kn，各邊的權(quán)非負(fù)，且，各邊的權(quán)非負(fù)，且有的邊的權(quán)可能為有的邊的權(quán)可能為 . 求求G中的一條最短的哈密頓回路，這就中的一條最短的哈密頓回路，這就是貨郎擔(dān)問(wèn)題的數(shù)學(xué)模型是貨郎擔(dān)問(wèn)題的數(shù)學(xué)模型. 完全帶權(quán)圖完全帶權(quán)圖Kn（n 3）中不同的哈密頓回路數(shù)）中不同

37、的哈密頓回路數(shù)(1) Kn中有中有(n 1)! 條不同的哈密頓回路（定義意義下）條不同的哈密頓回路（定義意義下）(2) 完全帶權(quán)圖中有完全帶權(quán)圖中有(n 1)! 條不同的哈密頓回路條不同的哈密頓回路(3) 用窮舉法解貨郎擔(dān)問(wèn)題算法的復(fù)雜度為用窮舉法解貨郎擔(dān)問(wèn)題算法的復(fù)雜度為(n 1)！，當(dāng)！，當(dāng)n較大較大時(shí)，計(jì)算量驚人地大時(shí)，計(jì)算量驚人地大38 解解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9可見(jiàn)可見(jiàn)C3 (見(jiàn)圖中見(jiàn)圖中(2) 是最短的，其權(quán)為是最短的，其權(quán)為9. 例例6 求圖中求圖中(1) 所示

38、帶權(quán)圖所示帶權(quán)圖K4中最短哈密頓回路中最短哈密頓回路. (1) (2) 39第十五章第十五章 習(xí)題課習(xí)題課 主要內(nèi)容主要內(nèi)容l 歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法l 哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖l 帶權(quán)圖、貨郎擔(dān)問(wèn)題帶權(quán)圖、貨郎擔(dān)問(wèn)題基本要求基本要求l 深刻理解歐拉圖、半歐拉圖的定義及判別定理深刻理解歐拉圖、半歐拉圖的定義及判別定理l 深刻理解哈密頓圖、半哈密頓圖的定義深刻理解哈密頓圖、半哈密頓圖的定義. l 會(huì)用哈密頓圖的必要條件判斷某些圖不是哈密頓圖會(huì)用哈密頓圖的必要條件判

39、斷某些圖不是哈密頓圖. l 會(huì)用充分條件判斷某些圖是哈密頓圖會(huì)用充分條件判斷某些圖是哈密頓圖. 要特別注意的是，要特別注意的是，不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要條件條件. 401. 設(shè)設(shè)G為為n（n 2）階無(wú)向歐拉圖，證明）階無(wú)向歐拉圖，證明G中無(wú)橋中無(wú)橋(見(jiàn)例見(jiàn)例1思考題思考題)方法二：反證法方法二：反證法. 利用歐拉圖無(wú)奇度頂點(diǎn)及握手定理的推論利用歐拉圖無(wú)奇度頂點(diǎn)及握手定理的推論. 否則，設(shè)否則，設(shè)e=(u,v)為為G中橋，則中橋，則G e產(chǎn)生兩個(gè)連通分支產(chǎn)生兩個(gè)連通分支G1, G2，不妨設(shè)不妨設(shè)u在在G1中，中，v在在G2中中. 由于從由于從G中刪除中刪除e時(shí)，只改變時(shí)，只改變u,v 的度數(shù)的度數(shù)(