離散數(shù)學(xué)第十五章的課件

離散數(shù)學(xué)第十五章的課件1第一頁，共二十八頁，編輯于2023年，星期日15.1

歐拉圖歷史背景：哥尼斯堡七橋問題與歐拉圖18世紀(jì)中葉在歐洲普魯士的哥尼斯堡城內(nèi)有一條貫穿全市的普雷格爾河，河中有兩個小島，由7座橋相連接。當(dāng)時人們熱衷于一個難題：一個人怎么不重復(fù)走完七座橋，最后回到出發(fā)地點？這就是所謂的哥尼斯堡七橋問題。很長時間沒有人能解決這個難題。2第二頁，共二十八頁，編輯于2023年，星期日15.1

歐拉圖歷史背景：哥尼斯堡七橋問題與歐拉圖1763年，瑞士數(shù)學(xué)家歐拉發(fā)表論文，他用四個點分別表示兩個小島和兩岸，用連接兩點的線段表示橋。于是，哥尼斯堡七橋問題就是要求在這個圖中走一條歐拉回路（即經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路）。3第三頁，共二十八頁，編輯于2023年，星期日15.1歐拉圖定義15.1(1)歐拉通路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的通路.(2)歐拉回路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路.(3)歐拉圖——具有歐拉回路的圖.(4)半歐拉圖——具有歐拉通路而無歐拉回路的圖.幾點說明：規(guī)定平凡圖為歐拉圖.歐拉通路是生成的簡單通路，歐拉回路是生成的簡單回路.環(huán)不影響圖的歐拉性.4第四頁，共二十八頁，編輯于2023年，星期日上圖中，(1),(4)為歐拉圖，(2)為半歐拉圖，(3),(5),(6)既不是歐拉圖，也不是半歐拉圖.歐拉圖判斷實例5第五頁，共二十八頁，編輯于2023年，星期日要求掌握無向歐拉圖的判定定理15.1

無向圖G是歐拉圖當(dāng)且僅當(dāng)G連通且無奇度頂點.在以上三個無向圖（三個圖都是連通圖）中，只有圖（1）中沒有奇度頂點，因此圖（1）是歐拉圖。而圖（2）和圖（3）中都存在奇度頂點，因而它們都不是歐拉圖。6第六頁，共二十八頁，編輯于2023年，星期日半歐拉圖的判別法定理15.2

無向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個奇度頂點.在以上兩個無向圖（兩個圖都是連通圖）中，只有（2）中有兩個奇度頂點，因此（2）是半歐拉圖。而（3）中有4個奇度頂點，因而（3）不是半歐拉圖。7第七頁，共二十八頁，編輯于2023年，星期日有向歐拉圖的判別法定理15.3

有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強連通的且每個頂點的入度都等于出度.定理15.4

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

G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干個邊不重的初級回路（圈）之并.8第八頁，共二十八頁，編輯于2023年，星期日求歐拉回路的算法——Fleury算法算法：(1)任取v0V(G)，令P0=v0，i=0.(2)設(shè)Pi=v0e1v1e2…eivi已經(jīng)行遍如果E(G){e1,e2,…,ei}中沒有與vi關(guān)聯(lián)的邊，則計算停止；否則按下述條件從E(G){e1,e2,…,ei}中選取一條邊ei+1：

(a)ei+1與vi相關(guān)聯(lián)；

(b)除非無別的邊可供選擇，否則ei+1不應(yīng)該為

Gi=G{e1,e2,…,ei}中的橋.

設(shè)ei+1=(vi，vi+1

)，把ei+1vi+1加入

Pi得到Pi+1.(3)令i=i+1，返回(2).可以證明算法停止時所得簡單回路

Pm

=v0e1v1e2…emvm(vm=v0)為G中的一條歐拉回路.能夠一筆畫出的圖——歐拉圖。要求掌握使用定理15.1，要會判斷一個圖是否為歐拉圖。要求理解Fleury算法和應(yīng)用它一筆畫出歐拉圖。9第九頁，共二十八頁，編輯于2023年，星期日15.2

哈密頓圖歷史背景：哈密頓周游世界問題與哈密頓圖

(1)(2)1859年，愛爾蘭數(shù)學(xué)家哈密頓提出一個周游世界問題：有20個城市，城市之間的交通路線如（2）所示。問能否從某個城市出發(fā)沿交通路線經(jīng)過每個城市一次并且僅一次，最后回到出發(fā)點？用現(xiàn)在的語言，就是問這個圖中是否有哈密頓回路？哈密頓自己做了肯定的回答。哈密頓回路和哈密頓圖即由此得名。10第十頁，共二十八頁，編輯于2023年，星期日15.2

哈密頓圖歷史背景：哈密頓周游世界問題與哈密頓圖

(1)(2)11第十一頁，共二十八頁，編輯于2023年，星期日15.2

哈密頓圖定義15.2

(1)哈密頓通路——經(jīng)過圖中所有頂點一次僅一次的通路.(2)哈密頓回路——經(jīng)過圖中所有頂點一次僅一次的回路.(3)哈密頓圖——具有哈密頓回路的圖.(4)半哈密頓圖——具有哈密頓通路且無哈密頓回路的圖.幾點說明：平凡圖是哈密頓圖.哈密頓通路是初級通路，哈密頓回路是初級回路.環(huán)與平行邊不影響哈密頓性.12第十二頁，共二十八頁，編輯于2023年，星期日上圖中，(1),(2),(3)三個無向圖都有哈密頓回路，都是哈密頓圖。在有向圖中，(4)有哈密頓回路，是哈密頓圖。(5)只有哈密頓通路，沒有哈密頓回路，是半哈密頓圖，而(6)中既無哈密頓回路，也沒有哈密頓通路，因而不是哈密頓圖，也不是半哈密頓圖.要求掌握哈密頓圖的判定13第十三頁，共二十八頁，編輯于2023年，星期日無向哈密頓圖的一個必要條件定理15.6

設(shè)無向圖G=<V,E>是哈密頓圖，對于任意V1V且V1，均有p(GV1)|V1|推論設(shè)無向圖G=<V,E>是半哈密頓圖，對于任意的V1V且V1均有p(GV1)|V1|+1定理15.6中的條件是哈密頓圖的必要條件，但不是充分條件。常利用定理15.6判斷某些圖不是哈密頓圖.14第十四頁，共二十八頁，編輯于2023年，星期日哈密頓圖和半哈密頓圖的幾個充分條件定理15.7

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

d(vi)+d(vj)

n1(15.1)則G中存在哈密頓通路.推論設(shè)G為n(n3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有

d(vi)+d(vj)

n(15.2)則G中存在哈密頓回路，從而G為哈密頓圖.定理15.7是半哈密頓圖的充分條件，但不是必要條件.長度為n1（n>5）的初級通路構(gòu)成的圖不滿足(15.1)的條件，但它顯然是半哈密頓圖.定理15.7的推論同樣不是哈密頓圖的必要條件，G為長為n（n>4）的初級回路，不滿足(15.2)條件，但它當(dāng)然是哈密頓圖.由定理15.7的推論可知，Kn（n3）均為哈密頓圖.15第十五頁，共二十八頁，編輯于2023年，星期日哈密頓圖和半哈密頓圖的幾個充分條件定理15.8

設(shè)u,v為n階無向簡單圖G中兩個不相鄰的頂點，且d(u)+d(v)n，則G為哈密頓圖當(dāng)且僅當(dāng)G(u,v)為哈密頓圖（(u,v)是加的新邊）.定理15.9

n（n2）階競賽圖中都有哈密頓通路若D為n（n2）階競賽圖，則D中具有哈密頓通路。16第十六頁，共二十八頁，編輯于2023年，星期日判斷某圖是否為哈密頓圖的方法判斷某圖是否為哈密頓圖至今還是一個難題.總結(jié)判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法.1.觀察出哈密頓回路.例3

下圖(周游世界問題)是哈密頓圖易知a

b

c

d

e

f

g

h

i

j

k

l

m

no

p

q

r

s

t

a為圖中的一條哈密頓回路.注意，此圖不滿足定理15.7推論的條件.17第十七頁，共二十八頁，編輯于2023年，星期日2．滿足定理15.7推論的條件（15.2）.例4

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

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

n（n3），所以Kn為哈密頓圖.3．破壞定理15.6的條件的圖不是哈密頓圖.判斷某圖是否為哈密頓圖的方法18第十八頁，共二十八頁，編輯于2023年，星期日設(shè)GG，稱為G的權(quán)，并記作W(G)，即定義15.3

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

(R為實數(shù)集)，對G中的每一條邊e=(vi,vj)(G為有向圖時，e=<vi,vj>)，設(shè)W(e)=wij，稱實數(shù)wij為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱G為帶權(quán)圖，記作G

=

<V,E,W>.當(dāng)e=(vi,vj)(<vi,vj>)，把W(e)記作W(vi,vj).15.3最短路問題與貨郎擔(dān)問題設(shè)P是G中的一條通路，P中所有邊的權(quán)之和稱為P的長度，記作W(P)，即。類似可定義回路C的長度W(C)。19第十九頁，共二十八頁，編輯于2023年，星期日最短路問題

設(shè)帶權(quán)圖G

=

<V,E,W>（無向圖或有向圖），其中每一條邊e的權(quán)W(e)為非負(fù)實數(shù)。u,v∈V，當(dāng)u和v連通時（即u可達v

），稱從u到v長度最短的路徑為從u到v的最短路徑，稱其長度為從u到v的距離，記作d(u,v)。約定：d(u,u)=0；當(dāng)u和v不連通時（即u不可達v

），d(u,v)=+∞。20第二十頁，共二十八頁，編輯于2023年，星期日最短路問題最短路問題：給定帶權(quán)圖G=<V,E,W>及頂點u和v，其中每一條邊e的權(quán)W(e)為非負(fù)實數(shù)，求從u到v的最短路徑。如果uvi1vi2…vikv是從u到v的最短路徑，則對每一個l（1≤l≤k

），uvi1vi2…vil是從u到vil的最短路徑。根據(jù)該性質(zhì)，E.W.Dijkstra于1959年給出下述最短路徑算法。最短路徑算法給出從給定的起點s到每一點的最短路徑。在計算過程中，賦予每一個頂點v一個標(biāo)號l(v)=(l1(v),l2(v))。標(biāo)號分為永久標(biāo)號和臨時標(biāo)號：在v的永久標(biāo)號l(v)中，l1(v)表示s到v的最短路徑上v的前一個頂點，l2(v)表示從s到v的距離（即從s到v的最短路徑的長度）。當(dāng)l(v)是臨時標(biāo)號時，l1(v)表示當(dāng)前從s經(jīng)過永久標(biāo)號的頂點到v的長度最短的路徑上v的前一個頂點；l2(v)表示當(dāng)前從s經(jīng)過永久標(biāo)號的頂點到v的長度最短的路徑的長度。21第二十一頁，共二十八頁，編輯于2023年，星期日Dijkstra標(biāo)號法輸入：帶權(quán)圖G

=

<V,E,W>和s∈V，其中|V|=n

，e∈E，W(e)≥0輸出：s到G中每一點的最短路徑及距離1.令l(s)=(s,0)，l(v)=(s,+∞)(v∈V–{s})，i=1，

l(s)是永久標(biāo)號，其余標(biāo)號均為臨時標(biāo)號，u=s（l(u):永久標(biāo)號）2.for與u關(guān)聯(lián)的臨時標(biāo)號的頂點v（l(v):臨時標(biāo)號）3. ifl2(u)+W(u,v)<l2(v)

l(v)=(u,l2(u)+W(u,v))4.計算l2(t)=min{l2(v)|v∈V且有臨時標(biāo)號}，把l(t)改為永久標(biāo)號5.ifi<n

u=t,i=i+1,goto2

計算結(jié)束時，對每一個頂點u，d(s,u)=l2(u)，利用l1(v)從u開始回溯找到s到u的最短路徑。22第二十二頁，共二十八頁，編輯于2023年，星期日貨郎擔(dān)問題

設(shè)G=<V,E,W>為一個n階完全帶權(quán)圖Kn，各邊的權(quán)W(e)非負(fù)且可以為∞.求G中的一條最短的哈密頓回路——這就是貨郎擔(dān)問題的數(shù)學(xué)模型.

貨郎擔(dān)問題（旅行商問題）：有n個城市，給定城市之間道路的長度（長度可以為∞，對應(yīng)這兩個城市之間無交通線）。一個旅行商從某個城市出發(fā)，要經(jīng)過每個城市一次且僅一次，最后回到出發(fā)的城市。問如何走才能使他走的路線最短？這個問題可以用圖論方法描述如下：23第二十三頁，共二十八頁，編輯于2023年，星期日

解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可見C3是最短的，其權(quán)為9.圖(2)是所求的最短路線圖例6

求圖中(1)所示4階完全帶權(quán)圖K4中最短哈密頓回路及其最短線路圖.

(1)(2)貨郎擔(dān)問題實例24第二十四頁，共二十八頁，編輯于2023年，星期日重點主要內(nèi)容歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖帶權(quán)圖、貨郎擔(dān)問題判斷哪些圖可一筆畫出？用Dijkstra標(biāo)號法求所示帶權(quán)圖中從頂點v1到頂點vi(i=2..7)的最短路徑。

求所示帶權(quán)圖中所有哈密頓回路，指出哪條最短并畫出其路線圖。25第二十五頁，共二十八頁，編輯于2023年，星期日第十五章習(xí)題課

主要內(nèi)容歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖帶權(quán)圖、貨郎擔(dān)問題基本要求深刻理解歐拉圖、半歐拉圖的定義及判別定理深刻理解哈密頓圖、半哈密頓圖的定義.會用哈密頓圖的必要條件判斷某些圖不是哈密頓圖.會用充分條件判斷某些圖是哈密頓圖.要特別注意的是，不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要條件.26第二十六頁，共二十八頁，編輯于2023年，星期日1.設(shè)G為n（n2）階無向歐拉圖，證明G中無橋(見例1思考題)方法二：反證法.利用歐拉圖無奇度頂點及握手定理的推論.否則，設(shè)e=(u,v)為G中橋，則Ge產(chǎn)生兩個連通分支G1,G2，不妨設(shè)u