SchoolofInformationScienceandEngineering第十五章歐拉圖與哈密頓圖主要內(nèi)容帶權(quán)圖與貨郎擔(dān)問(wèn)題SchoolofInformationScienceandEngineering15.1歐拉圖歷史背景：哥尼斯堡七橋問(wèn)題與歐拉圖ABCDe1e5e7e6e3e4e2ABCDSchoolofInformationScienceandEngineering歐拉圖定義[歐拉通路]經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的通路。[歐拉回路]

經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的回路。[歐拉圖]有歐拉回路的圖。[半歐拉圖]有歐拉通路而無(wú)歐拉回路的圖。說(shuō)明：規(guī)定平凡圖為歐拉圖。歐拉通路是生成的簡(jiǎn)單通路，歐拉回路是生成的簡(jiǎn)單回路。環(huán)不影響圖的歐拉性。SchoolofInformationScienceandEngineering歐拉圖的判別法定理15.2

無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn)。證明：必要性簡(jiǎn)單.充分性（利用定理15-1）設(shè)u,v為G中的兩個(gè)奇度頂點(diǎn)，令

G=G(u,v)則G連通且無(wú)奇度頂點(diǎn)，由定理15-1知G為歐拉圖，因而存在歐拉回路C，令=C(u,v)則為G中歐拉通路.理解：G有兩個(gè)奇數(shù)度結(jié)點(diǎn)：就從一個(gè)奇數(shù)度結(jié)點(diǎn)出發(fā)，每當(dāng)?shù)竭_(dá)一個(gè)偶數(shù)度結(jié)點(diǎn)，必然可以再經(jīng)過(guò)另一條邊離開(kāi)此結(jié)點(diǎn)，如此重復(fù)下去，經(jīng)過(guò)所有邊后到達(dá)另一個(gè)奇數(shù)度結(jié)點(diǎn)。SchoolofInformationScienceandEngineering有向歐拉圖的判別法定理15.3

有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度都等于出度.

定理15.4

有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且D中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1，另一個(gè)的出度比入度大1，而其余頂點(diǎn)的入度都等于出度.定理15.5

G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干個(gè)邊不重的圈之并.

SchoolofInformationScienceandEngineering上圖中，(1),(4)為歐拉圖，(2)為半歐拉圖，(3),(5),(6)既不是歐拉圖，也不是半歐拉圖.歐拉圖實(shí)例SchoolofInformationScienceandEngineering歐拉回路算法G有E回路?選結(jié)點(diǎn)v以v為起點(diǎn)找簡(jiǎn)單回路E1E1包含所有邊停止NY打印E1在G-E1中找一個(gè)簡(jiǎn)單回路E2使E1與E2至少有一個(gè)公共點(diǎn)N

以某公共點(diǎn)為起、末點(diǎn),對(duì)

E1∪E2中的邊重新排序得新的簡(jiǎn)單回路CE1:=CY用上述算法求右圖中歐拉回路.此圖中所有結(jié)點(diǎn)度均為偶數(shù),所以有歐拉回路.a)選以1為起點(diǎn)的簡(jiǎn)單回路E1:1261b)E1不包含所有邊.c)在G-E1中找新簡(jiǎn)單回路E2:6356(6是E1與E2的公共點(diǎn))d)以公共點(diǎn)6為起點(diǎn),對(duì)E1∪E2中的邊排序:C=6356126e)E1:=Cf)E1不包含所有邊.g)在G-E1中找新簡(jiǎn)單回路E2:52345(5是E1與E2的公共點(diǎn))h)以公共點(diǎn)5為起點(diǎn),對(duì)E1∪E2中的邊排序:C=52345612635i)E1:=Cj)E1包含所有邊.k)打印E1=52345612635l)停止.162534162534SchoolofInformationScienceandEngineering15.2

哈密頓圖歷史背景：哈密頓周游世界問(wèn)題與哈密頓圖

(1)(2)SchoolofInformationScienceandEngineering實(shí)例在上圖中，(1),(2)是哈密頓圖;(3)是半哈密頓圖;(4)既不是哈密頓圖，也不是半哈密頓圖定理15.6:(必要條件)若圖G=<V,E>有H回路,則對(duì)V的任何非空子有限集V1,均有p(GV1)|V1|,其中p(GV1)是從G中刪去V1中所有結(jié)點(diǎn)及與這些結(jié)點(diǎn)關(guān)聯(lián)的邊所得到的子圖的連通分支數(shù).證明:設(shè)C是圖G的一條H回路,則對(duì)于V的任何非空子集V1,在C中刪去V1中任意一個(gè)結(jié)點(diǎn)v1后,則C-v1仍是連通的路,若再刪去V1中的另一個(gè)結(jié)點(diǎn)v2,則p(C-v1-

v2)≤2,若|V1|=n則刪去V1中的n個(gè)結(jié)點(diǎn),有p(C-v1-

v2-...-vn)≤n,所以p(C-v1-

v2-...-vn)≤|V1|.因?yàn)镃是H回路,所以它包含了G的所有結(jié)點(diǎn),即C是G的生成子圖.所以C-V1

也是G-V1

的生成子圖,故p(G-V1)≤|V1|.

用此定理可以判斷一個(gè)圖不是H圖.如右圖G

取V1={c}不滿足p(G-V1)≤|V1|.cebad無(wú)向哈密頓圖的一個(gè)必要條件SchoolofInformationScienceandEngineering無(wú)向哈密頓圖的一個(gè)必要條件推論設(shè)無(wú)向圖G=<V,E>是半哈密頓圖，對(duì)于任意的V1V且V1均有p(GV1)|V1|+1證令為G中起于u終于v哈密頓通路，令G=G(u,v)則G為哈密頓圖.由定理15.6知，p(G

V1)|V1|而p(GV1)=p(GV1(u,v))

|V1|+1SchoolofInformationScienceandEngineering無(wú)向哈密頓圖的一個(gè)充分條件定理15.7

設(shè)G是n階無(wú)向簡(jiǎn)單圖，若對(duì)于任意不相鄰的頂點(diǎn)vi,vj，均有

d(vi)+d(vj)

n1則G中存在哈密頓通路.推論

設(shè)G為n(n3)階無(wú)向簡(jiǎn)單圖，若對(duì)于G中任意兩個(gè)不相鄰的頂點(diǎn)vi,vj，均有

d(vi)+d(vj)n則G中存在哈密頓回路，從而G為哈密頓圖.SchoolofInformationScienceandEngineering幾點(diǎn)說(shuō)明定理15.7是半哈密頓圖的充分條件，但不是必要條件。長(zhǎng)為n1（n4）的路徑構(gòu)成的圖不滿足（）條件，但它顯然是半哈密頓圖。定理15.7的推論同樣不是哈密頓圖的必要條件G為長(zhǎng)為n的圈，不滿足（）條件，但它當(dāng)然是哈密頓圖。由定理15.7的推論可知，Kn（n3）均為哈密頓圖。SchoolofInformationScienceandEngineering定理15.9

若D為n（n2）階競(jìng)賽圖，則D中具有哈密頓通路(注意，競(jìng)賽圖的基圖是無(wú)向完全圖)證明思路：對(duì)n（n2）做歸納.書(shū)P302,定理15.9無(wú)向哈密頓圖的充分條件SchoolofInformationScienceandEngineering2．滿足定理15.7推論的條件.例4

完全圖Kn(n3)中任何兩個(gè)頂點(diǎn)u,v，均有

d(u)+d(v)=2(n1)

n（n3），所以Kn為哈密頓圖.3．破壞定理15.6的條件的圖不是哈密頓圖.判斷某圖是否為哈密頓圖方法SchoolofInformationScienceandEngineering設(shè)P是G中的一條通路，P中所有邊的權(quán)之和稱為P的長(zhǎng)度，記作W(P)，即[定義]

給定圖G=<V,E>，(G為無(wú)向圖或有向圖)，給定W:ER

(R為實(shí)數(shù)集)，對(duì)G中任意邊e=(vi,vj)(G為有向圖時(shí)，e=<vi,vj>)，設(shè)W(e)=wij，稱實(shí)數(shù)wij為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱G為帶權(quán)圖，此時(shí)常將帶權(quán)圖G記作<V,E,W>.15.3最短路問(wèn)題與貨郎擔(dān)問(wèn)題例如右圖中v1v2v3v6的路長(zhǎng)為？.3.帶權(quán)圖的兩點(diǎn)間距離:結(jié)點(diǎn)u與v之間的最短路的長(zhǎng)度稱為結(jié)點(diǎn)u與v之間的距離.記作d(u,v).規(guī)定：d(u,u)=0,當(dāng)u和v不連通(u不可達(dá)v)時(shí),d(u,v)=

例如上圖中d(v2,v5)=？4.帶權(quán)圖中求一個(gè)結(jié)點(diǎn)到各點(diǎn)的最短路的算法:此算法是于1959年由E.W.Dijkstra提出的.基本思想:若使(u0,u1,u2,…,un-1,un)最短,就要使(u0,u1,u2,…,un-1)最短,即保證從u0到以后各點(diǎn)的路都是最短的.v6v5v4v1v3v2365112336例.求右圖中從v1到v6的最短路徑1.置初值:u0=v1d(u0,u0)=0d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=∞2.3.i=0S0={v1}S0’={v2,v3,v4,v5,v6}d(u0,v2)=min{d(u0,v2),d(u0,u0)+w(u0,v2)}=min{∞,0+3}=3d(u0,v3)=min{d(u0,v3),d(u0,u0)+w(u0,v3)}=min{∞,0+∞}=∞d(u0,v4)=min{d(u0,v4),d(u0,u0)+w(u0,v4)}=min{∞,0+5}=5d(u0,v5)=min{d(u0,v5),d(u0,u0)+w(u0,v5)}=min{∞,0+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u0)+w(u0,v6)}=min{∞,0+∞}=∞min{3,∞,5,∞,∞}=3ui+1=u1=v2,實(shí)際已求出d(u0,v2)=3,路是u0v2v6v5v4v1v3v2365113336i=1S1={v1,

v2}S1’={v3,v4,v5,v6}u1=v2d(u0,u1)=3d(u0,v3)=min{d(u0,v3),d(u0,u1)+w(u1,v3)}=min{∞,3+6}=9d(u0,v4)=min{d(u0,v4),d(u0,u1)+w(u1,v4)}=min{5,3+1}=4d(u0,v5)=min{d(u0,v5),d(u0,u1)+w(u1,v5)}=min{∞,3+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u1)+w(u1,v6)}=min{∞,3+∞}=∞min{9,4,∞,∞}=4ui+1=u2=v4,實(shí)際已求出d(u0,v4)=4,路是u0v2v4v6v5v4v1v3v2365113336SchoolofInformationScienceandEngineering貨郎擔(dān)問(wèn)題設(shè)G=<V,E,W>為一個(gè)n階完全帶權(quán)圖Kn，各邊的權(quán)非負(fù)，且有的邊的權(quán)可能為.求G中的一條最短的哈密頓回路，這就是貨郎擔(dān)問(wèn)題的數(shù)學(xué)模型.完全帶權(quán)圖Kn（n3）中不同的哈密頓回路數(shù)(1)Kn中有(n