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

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

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

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

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

無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn).在以上兩個(gè)無(wú)向圖（兩個(gè)圖都是連通圖）中，只有（2）中有兩個(gè)奇度頂點(diǎn)，因此（2）是半歐拉圖。而（3）中有4個(gè)奇度頂點(diǎn)，因而（3）不是半歐拉圖。7第七頁(yè)，共二十八頁(yè)，編輯于2023年，星期日有向歐拉圖的判別法定理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è)邊不重的初級(jí)回路（圈）之并.8第八頁(yè)，共二十八頁(yè)，編輯于2023年，星期日求歐拉回路的算法——Fleury算法算法：(1)任取v0V(G)，令P0=v0，i=0.(2)設(shè)Pi=v0e1v1e2…eivi已經(jīng)行遍如果E(G){e1,e2,…,ei}中沒(méi)有與vi關(guān)聯(lián)的邊，則計(jì)算停止；否則按下述條件從E(G){e1,e2,…,ei}中選取一條邊ei+1：

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

(b)除非無(wú)別的邊可供選擇，否則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).可以證明算法停止時(shí)所得簡(jiǎn)單回路

Pm

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

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

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

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

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

哈密頓圖定義15.2

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

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

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

d(vi)+d(vj)

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

d(vi)+d(vj)

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

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

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

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

b

c

d

e

f

g

h

i

j

k

l

m

no

p

q

r

s

t

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

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

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

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

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

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

=

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

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

=

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

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

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

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

=

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

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

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

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

u=t,i=i+1,goto2

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

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

貨郎擔(dān)問(wèn)題（旅行商問(wèn)題）：有n個(gè)城市，給定城市之間道路的長(zhǎng)度（長(zhǎng)度可以為∞，對(duì)應(yīng)這兩個(gè)城市之間無(wú)交通線(xiàn)）。一個(gè)旅行商從某個(gè)城市出發(fā)，要經(jīng)過(guò)每個(gè)城市一次且僅一次，最后回到出發(fā)的城市。問(wèn)如何走才能使他走的路線(xiàn)最短？這個(gè)問(wèn)題可以用圖論方法描述如下：23第二十三頁(yè)，共二十八頁(yè)，編輯于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可見(jiàn)C3是最短的，其權(quán)為9.圖(2)是所求的最短路線(xiàn)圖例6

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

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

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

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