第二講 圖論基礎(chǔ)

第二講：圖論模型7月30日圖論基礎(chǔ)專題（老內(nèi)容）一圖的基本概念二三最短路問題及其算法四最小生成樹問題圖的矩陣表示新內(nèi)容歐拉圖與哈密頓圖匹配問題網(wǎng)絡(luò)流圖的染色

數(shù)學(xué)建模-圖論42023年2月5日

一、圖的基本概念若將圖G的每一條邊e都對應(yīng)一個實數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖,記為G=(V,E,F

).

設(shè)G=(V,E)是一個圖,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,則稱v0v1…

vk是G的一條通路.

如果通路中沒有相同的頂點,則稱此通路為路徑,簡稱路.始點和終點相同的路稱為圈或回路.

一、圖的基本概念數(shù)學(xué)建模-圖論頂點u與v稱為連通的，如果存在u到v通路，任二頂點都連通的圖稱為連通圖，否則，稱為非連通圖。極大連通子圖稱為連通分圖。

連通而無圈的圖稱為樹,常用T表示樹.樹中最長路的邊數(shù)稱為樹的高，度數(shù)為1的頂點稱為樹葉。其余的頂點稱為分枝點。樹的邊稱為樹枝。設(shè)G是有向圖，如果G的底圖是樹，則稱G是有向樹，也簡稱樹。

一、圖的基本概念數(shù)學(xué)建模-圖論鄰接矩陣（結(jié)點與結(jié)點的關(guān)系）關(guān)聯(lián)矩陣（結(jié)點與邊的關(guān)系）路徑矩陣（任意兩結(jié)點之間是否有路徑）可達性矩陣直達矩陣等等……二、圖的矩陣表示數(shù)學(xué)建模-圖論1有向圖的鄰接矩陣

A=(aij)n×n

（n為結(jié)點數(shù)）

例1：寫出右圖的鄰接矩陣：解：二、圖的矩陣表示數(shù)學(xué)建模-圖論2有向圖的權(quán)矩陣A=(aij)n×n

（n為結(jié)點數(shù)）

例2：寫出右圖的權(quán)矩陣：解：二、圖的矩陣表示數(shù)學(xué)建模-圖論3有向圖的關(guān)聯(lián)矩陣A=(aij)n×m

（n為結(jié)點數(shù)m為邊數(shù)）

有向圖：無向圖：

二、圖的矩陣表示數(shù)學(xué)建模-圖論例3：分別寫出右邊兩圖的關(guān)聯(lián)矩陣解：分別為：

二、圖的矩陣表示

數(shù)學(xué)建模-圖論

二、圖的矩陣表示（應(yīng)用實例及解法分析）數(shù)學(xué)建模-圖論商人過河問題：假如有三個商人各帶一名隨從要過河，只有一條船，每次最多只能坐兩個人。為安全起見，商人數(shù)不能少于隨從數(shù)，否則隨從會殺人越貨。船過一次河需要5分鐘，問最短幾分鐘能使他們都過去？用鄰接矩陣來解決：設(shè)(m,n,l)表示左岸商人m人，隨從n人；設(shè)(m,n,r)表示右岸有商人m人，隨從n人。從左岸到右岸去，所有可能的狀態(tài)為：v1=(3,3,l),v2=(3,2,l),v3=(3,1,l),v4=(3,0,l),v5=(2,2,l),v6=(1,1,l),v7=(0,3,l),v8=(0,2,l),v9=(0,1,l),v10=(3,3,r),v11=(3,2,r),v12=(3,1,r),v13=(3,0,r),v14=(2,2,r),v15=(1,1,r),v16=(0,3,r),v17=(0,2,r),v18=(0,1,r).

二、圖的矩陣表示（應(yīng)用實例及解法分析）數(shù)學(xué)建模-圖論V10v11v12v13v14v15v16v17v18v1

v2v3v4v5v6v7v8v9渡河可以理解為上面狀態(tài)的轉(zhuǎn)移，例如狀態(tài)v1渡河一次可以轉(zhuǎn)化為其他狀態(tài)v15v17v18，其他狀態(tài)也易列出。以V={v1,

v2,...v18}為頂點集，當兩種狀態(tài)可以互相轉(zhuǎn)化時，就在相應(yīng)的來那個頂點間連一邊，從而建立一個二分圖G=<V,E>，如右圖所示。G=<V,E>的鄰接矩陣為：

二、圖的矩陣表示（應(yīng)用實例及解法分析）數(shù)學(xué)建模-圖論V10v11v12v13v14v15v16v17v18v1

v2v3v4v5v6v7v8v9其中，矩陣B為：記a(k)ij為Ak中的（i,j）元，目標是使a(k)1,10不等于0的最小的自然數(shù)k.

利用matlab容易計算出k=11，且a(11)1,10=4,即小船至少11次才能把所有人全部運到右岸，說明共有4種不同的過河方案。繼續(xù)計算可得出a(19)1,10=45060，如果允許小船過河19次的話，共有45060中不同的方案。若將圖G的每一條邊e都對應(yīng)一個實數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖,記為G=(V,E,F

).

設(shè)G=(V,E)是一個圖,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,則稱v0v1…

vk是G的一條通路.如果通路中沒有相同的頂點,則稱此通路為路徑,簡稱路.對于賦權(quán)圖，路的長度（即路的權(quán)）通常指路上所有邊的權(quán)之和。最短路問題：求賦權(quán)圖上指定點之間的權(quán)最小的路。

三、最短路問題及其算法數(shù)學(xué)建模-圖論重要性質(zhì)：若v0v1…

vm是G中從v0到vm的最短路,則對1≤k≤m,v0v1…

vk必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路。數(shù)學(xué)建模-圖論

三、最短路問題及其算法

設(shè)有給定連接若干城市的公路網(wǎng)，尋求從指定城市到各城市的最短路線。

2、應(yīng)用實例：最短路問題

問題的數(shù)學(xué)模型:

三、最短路問題及其算法172023年2月5日數(shù)學(xué)建模-圖論182023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論254647109137106648192023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論202023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論212023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論222023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論254647109137106648232023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論242023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論252023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論262023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論254647109137106648272023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論282023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論292023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論254647109137106648302023年2月5日

三、最短路問題及其算法數(shù)學(xué)建模-圖論312023年2月5日數(shù)學(xué)建模-圖論

三、最短路問題及其算法322023年2月5日數(shù)學(xué)建模-圖論求v1到v6的最短路問題.

三、最短路問題及其算法332023年2月5日數(shù)學(xué)建模-圖論從上圖中容易得到v1到v6只有兩條路：v1v3v6和v1v4v6.

而這兩條路都是v1到v6的最短路.

三、最短路問題及其算法頂點u與v稱為連通的，如果存在u-v通路，任二頂點都連通的圖稱為連通圖，否則，稱為不連通圖。極大連通子圖稱為連通分圖。

連通而無圈的圖稱為樹,常用T表示樹.樹中最長路的邊數(shù)稱為樹的高的度為1的頂點稱為樹葉。其余的頂點稱為分枝點。樹的邊稱為樹枝。設(shè)G是有向圖，如果G的底圖是樹，則稱G是有向樹，也簡稱樹。

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論若任意一個連通的圖G=<V,E>的生成子圖T=<V’,E’>(V’=V,E’為E的子集)為樹,這棵樹T稱為圖G的生成樹.設(shè)T是圖G的一棵生成樹,用F(T)表示樹T中所有邊的權(quán)數(shù)之和,F(T)稱為樹T的權(quán).一個連通圖G的生成樹一般不止一棵,圖G的所有生成樹中權(quán)數(shù)最小的生成樹稱為圖G的最小生成樹.數(shù)學(xué)建模-圖論

四、最小生成樹問題及其算法怎樣找出最小生成樹？？？G

T1T2T3T4T5T6T7T8T1至T8是圖G的生成樹數(shù)學(xué)建模-圖論

四、最小生成樹問題及其算法Kruskal算法思想：在不形成圈得條件下，優(yōu)先挑選權(quán)小的邊形成生成樹。76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7數(shù)學(xué)建模-圖論

四、最小生成樹問題及其算法注：算法構(gòu)造的最小生成樹的邊集為E1；標號l

具有性質(zhì)：當且僅當u、v之間有一條僅由E1

中的邊形成的路時，l(u)=l(v)，因此在步驟(2)發(fā)現(xiàn)l(u)=l(v)時，(u,v)不能放入E1，否則會形成一個圈。

數(shù)學(xué)建模-圖論

四、最小生成樹問題及其算法392023年2月5日

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論402023年2月5日

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論412023年2月5日

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論運行結(jié)果如下：T=135163266674c=26上述例題的matlab程序如下：b=[11223334556;26364677677;24458378376];Krusf(b,1);76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7422023年2月5日

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論

432023年2月5日

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論442023年2月5日

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論452023年2月5日

四、最小生成樹問題及其算法數(shù)學(xué)建模-圖論

運行結(jié)果如下：T=116663263574c=24336876788334245v1v2v3v4v5v6v7歐拉圖與哈密頓圖歐拉圖定義15.1通過圖（無向圖或有向圖）中所有邊一次且僅一次行遍圖中所有頂點的通路稱為歐拉通路，通過圖中所有邊一次并且僅一次行遍所有頂點的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖，具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。說明 歐拉通路是圖中經(jīng)過所有邊的簡單的生成通路(經(jīng)過所有頂點的通路稱為生成通路)。 歐拉回路是經(jīng)過所有邊的簡單的生成回路。舉例歐拉圖半歐拉圖無歐拉通路歐拉圖無歐拉通路無歐拉通路無向歐拉圖的判定定理定理15.1無向圖G是歐拉圖當且僅當G是連通圖，且G中沒有奇度頂點。證明 若G是平凡圖，結(jié)論顯然成立。下面設(shè)G為非平凡圖，設(shè)G是m條邊的n階無向圖，并設(shè)G的頂點集V＝{v1,v2,…,vn}。必要性。因為G為歐拉圖，所以G中存在歐拉回路，設(shè)C為G中任意一條歐拉回路，vi,vj∈V，vi,vj都在C上，因而vi,vj連通，所以G為連通圖。 又vi∈V，vi在C上每出現(xiàn)一次獲得2度， 若出現(xiàn)k次就獲得2k度，即d(vi)＝2k， 所以G中無奇度頂點。定理15.1的證明充分性。由于G為非平凡的連通圖可知，G中邊數(shù)m≥1。對m作歸納法。(1)m＝1時，由G的連通性及無奇度頂點可知，

G只能是一個環(huán)，因而G為歐拉圖。(2)設(shè)m≤k(k≥1)時結(jié)論成立，要證明m＝k+1時，結(jié)論也成立。 由G的連通性及無奇度頂點可知，δ(G)≥2。 無論G是否為簡單圖，都可以用擴大路徑法證明G中必含圈。定理15.1的證明設(shè)C為G中一個圈，刪除C上的全部邊，得G的生成子圖G，設(shè)G有s個連通分支G1,G2,…,Gs，每個連通分支至多有k條邊，且無奇度頂點，并且設(shè)Gi與C的公共頂點為v*ji，i＝1,2,…,s，由歸納假設(shè)可知，G1,G2,…,Gs都是歐拉圖，因而都存在歐拉回路Ci，i＝1,2,…,s。最后將C還原（即將刪除的邊重新加上），并從C上的某頂點vr開始行遍，每遇到v*ji，就行遍Gi中的歐拉回路Ci，i＝1,2,…,s，最后回到vr，得回路vr…v*j1…v*j1…v*j2…v*j2…v*js…v*js…vr，此回路經(jīng)過G中每條邊一次且僅一次并行遍G中所有頂點，因而它是G中的歐拉回路（演示這條歐拉回路），故G為歐拉圖。定理15.2無向圖G是半歐拉圖當且僅當G是連通的，且G中恰有兩個奇度頂點。證明

必要性。設(shè)G是m條邊的n階無向圖，因為G為半歐拉圖， 因而G中存在歐拉通路(但不存在歐拉回路)， 設(shè)Г＝vi0ej1vi1…vim-1ejmvim為G中一條歐拉通路，vi0≠vim。

v∈V(G)，若v不在Г的端點出現(xiàn)，顯然d(v)為偶數(shù)， 若v在端點出現(xiàn)過，則d(v)為奇數(shù)， 因為Г只有兩個端點且不同，因而G中只有兩個奇數(shù)頂點。 另外，G的連通性是顯然的。半歐拉圖的判定定理定理15.2無向圖G是半歐拉圖當且僅當G是連通的，且G中恰有兩個奇度頂點。證明

充分性。設(shè)G的兩個奇度頂點分別為u0和v0， 對G加新邊（u0,v0），得G＝G∪(u0,v0)， 則G是連通且無奇度頂點的圖， 由定理15.1可知，G為歐拉圖， 因而存在歐拉回路C，而C＝C-(u0,v0)為G中一條歐拉通路， 所以G為半歐拉圖。半歐拉圖的判定定理有向歐拉圖的判定定理定理15.3有向圖D是歐拉圖當且僅當D是強連通的且每個頂點的入度都等于出度。定理15.4有向圖D是半歐拉圖當且僅當D是單向連通的，且D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點的入度都等于出度。(舉例)定理15.5

G是非平凡的歐拉圖當且僅當G是連通的且為若干個邊不重的圈的并。例15.1例15.1設(shè)G是非平凡的且非環(huán)的歐拉圖，證明： (1)λ(G)≥2。 (2)對于G中任意兩個不同頂點u,v，都存在簡單回路C含u和v。證明(1)由定理15.5可知，e∈E(G)，存在圈C，e在C中， 因而p(G-e)＝p(G)，故e不是橋。 由e的任意性λ(G)≥2，即G是2邊-連通圖。(2)u,v∈V(G)，u≠v，由G的連通性可知，u,v之間必存在路徑Г1，設(shè)G＝G-E(Г1)，則在G中u與v還必連通， 否則，u與v必處于G的不同的連通分支中， 這說明在Г1上存在G中的橋，這與(1)矛盾。 于是在G中存在u到v的路徑Г2，顯然Г1與Г2邊不重， 這說明u,v處于Г1∪Г2形成的簡單回路上。求歐拉圖中歐拉回路的算法Fleury算法，能不走橋就不走橋

(1)任取v0∈V(G)，令P0＝v0。(2)設(shè)Pi＝v0e1v1e2…eivi已經(jīng)行遍，按下面方法來從

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}中的橋。(3)當(2)不能再進行時，算法停止。說明 可以證明，當算法停止時所得簡單回路

Pm＝v0e1v1e2…emvm(vm＝v0) 為G中一條歐拉回路。Fleury算法示例例15.2下圖是給定的歐拉圖G。某人用Fleury算法求G中的歐拉回路時，走了簡單回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(觀看他的錯誤走法)，無法行遍了，試分析在哪步他犯了錯誤?解答此人行遍v8時犯了能不走橋就不走橋的錯誤，因而他沒行遍出歐拉回路。 當他走到v8時，G-{e2,e3,e14,e10,e1,e8}為下圖所示。此時e9為該圖中的橋，而e7,e11均不是橋，他不應(yīng)該走e9，而應(yīng)該走e7或e11，他沒有走，所以犯了錯誤。注意，此人在行遍中，在v3遇到過橋e3，v1處遇到過橋e8，但當時除橋外他無別的邊可走，所以當時均走了橋，這是不會犯錯誤的。哈密頓圖定義15.2經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。經(jīng)過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。平凡圖是哈密頓圖。說明 哈密頓通路是圖中生成的初級通路， 哈密頓回路是生成的初級回路。 判斷一個圖是否為哈密頓圖，就是判斷能否將圖中所有頂點都放置在一個初級回路(圈)上，但這不是一件易事。 與判斷一個圖是否為歐拉圖不一樣，到目前為止，人們還沒有找到哈密頓圖簡單的充分必要條件。例題(1)(2)是哈密頓圖。(3)是半哈密頓圖。(4)既不是哈密頓圖，也不是半哈密頓圖。定理15.6定理15.6設(shè)無向圖G＝<V,E>是哈密頓圖，對于任意V1V，且V1≠，均有

p(G-V1)≤|V1| 其中，p(G-V1)為G-V1的連通分支數(shù)。證明

設(shè)C為G中任意一條哈密頓回路， 易知，當V1中頂點在C上均不相鄰時，

p(C-V1)達到最大值|V1|， 而當V1中頂點在C上有彼此相鄰的情況時， 均有p(C-V1)＜|V1|，所以有p(C-V1)≤|V1|。 而C是G的生成子圖，所以，有p(G-V1)≤p(C-V1)≤|V1|。說明 本定理的條件是哈密頓圖的必要條件，但不是充分條件。 可以驗證彼得松圖滿足定理中的條件，但不是哈密頓圖。 若一個圖不滿足定理中的條件，它一定不是哈密頓圖。推論推論設(shè)無向圖G＝<V,E>是半哈密頓圖，對于任意的V1V且V1≠，均有p(G-V1)≤|V1|+1證明 設(shè)P是G中起于u終于v的哈密頓通路， 令G＝G∪(u,v)(在G的頂點u,v之間加新邊)， 易知G為哈密頓圖， 由定理15.6可知，p(G-V1)≤|V1|。 因此，p(G-V1)＝p(G-V1-(u,v)) ≤p(G-V1)+1 ≤|V1|+1例15.3例15.3在下圖中給出的三個圖都是二部圖。它們中的哪些是哈密頓圖？哪些是半哈密頓圖？為什么？易知互補頂點子集

V1＝{a,f}

V2＝{b,c,d,e}設(shè)此二部圖為G1，則G1＝<V1,V2,E>。p(G1-V1)＝4>|V1|＝2，由定理15.6及其推論可知，G1不是哈密頓圖，也不是半哈密頓圖。例15.3設(shè)圖為G2，則G2＝<V1,V2,E>，其中V1＝{a,g,h,i,c}，V2＝{b,e,f,j,k,d}，易知，p(G2-V1)＝|V2|＝6>|V1|＝5，由定理15.6可知，G2不是哈密頓圖，但G2是半哈密頓圖。baegjckhfid為G2中一條哈密頓通路。設(shè)圖為G3。G3＝<V1,V2,E>，其中V1＝{a,c,g,h,e}，V2＝{b,d,i,j,f}，G3中存在哈密頓回路。如abcdgihjefa，所以G3是哈密頓圖。例15.3的說明哈密頓通路是經(jīng)過圖中所有頂點的一條初級通路。哈密頓回路是經(jīng)過圖中所有頂點的初級回路。對于二部圖還能得出下面結(jié)論： 一般情況下，設(shè)二部圖G＝<V1,V2,E>，|V1|≤|V2|，且|V1|≥2，|V2|≥2，由定理15.6及其推論可以得出下面結(jié)論： (1)若G是哈密頓圖，則|V1|＝|V2|。 (2)若G是半哈密頓圖，則|V2|＝|V1|+1。 (3)若|V2|≥|V1|+2，則G不是哈密頓圖，也不是半哈密頓圖。例15.4設(shè)G是n階無向連通圖。證明：若G中有割點或橋，則G不是哈密頓圖。證明可用定理15.6證明。定理15.7定理15.7設(shè)G是n階無向簡單圖，若對于G中任意不相鄰的頂點vi,vj，均有

d(vi)+d(vj)≥n-1 (15.1) 則G中存在哈密頓通路。證明

首先證明G是連通圖。 否則G至少有兩個連通分支， 設(shè)G1,G2是階數(shù)為n1,n2的兩個連通分支， 設(shè)v1∈V(G1)，v2∈V(G2)，因為G是簡單圖，所以

dG(v1)+dG(v2)＝dG1(v1)+dG2(v2)≤n1-1+n2-1≤n-2

這與(15.1)矛盾，所以G必為連通圖。定理15.7下面證G中存在哈密頓通路。設(shè)Г＝v1v2…vl為G中用“擴大路徑法”得到的“極大路徑”，即Г的始點v1與終點vl不與Г外的頂點相鄰。顯然有l(wèi)≤n。(1)若l＝n，則Г為G中哈密頓通路。(2)若l＜n，這說明Г不是哈密頓通路， 即G中還存在著Г外的頂點。 但可以證明G中存在經(jīng)過Г上所有頂點的圈。 (a) 若v1與vl相鄰，即(v1,vl)∈E(G)， 則Г∪(v1,vl)為滿足要求的圈。定理15.7(b)若v1與vl不相鄰，設(shè)v1與Г上的vi1＝v2,vi2,…,vik相鄰(k≥2) (否則d(v1)+d(vl)≤1+l-2=l-1<n-1，這與(15.1)矛盾) 此時，vl至少與vi2,…,vik相鄰的頂點vi2-1,…,vik-1之一相鄰 (否則d(v1)+d(vl)≤k+l-2-(k-1)＝l-1<n-1)

設(shè)vl與vir-1相鄰（2≤r≤k），見下圖所示。于是，回路

C＝v1v2…vir-1vlvlr-1…vi…virv1過Г上的所有頂點。定理15.7(c)下面證明存在比Г更長的路徑。 因為l<n，所以C外還有頂點，由G的連通性可知， 存在vl+1∈V(G)-V(C)與C上某頂點vt相鄰，見下圖所示。刪除邊(vt-1,vt)得路徑Г＝vt-1…v1vir…vlvir-1…vtvl+1比Г長度大1，對Г上的頂點重新排序，使其成為Г＝v1v2…vlvl+1，對Г重復(fù)(a)～(c)，在有限步內(nèi)一定得到G的哈密頓通路。定理15.7的推論推論設(shè)G為n(n≥3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有d(vi)+d(vj)≥n (15.2) 則G中存在哈密頓回路，從而G為哈密頓圖。證明由定理15.7可知，G中存在哈密頓通路， 設(shè)Г＝v1v2…vn為G中一條哈密頓通路， 若v1與vn相鄰，設(shè)邊e＝(v1,vn)，則Г∪{e}為G中哈密頓回路。 若v1與vn不相鄰，應(yīng)用(15.2)，同定理15.7證明中的(2)類似，可證明存在過Г上各頂點的圈， 此圈即為G中的哈密頓回路。定理15.8定理15.8設(shè)u,v為n階無向圖G中兩個不相鄰的頂點，且d(u)+d(v)≥n，則G為哈密頓圖當且僅當G∪(u,v)為哈密頓圖((u,v)是加的新邊)。證明 (略)。例15.5例15.5在某次國際會議的預(yù)備會議中，共有8人參加，他們來自不同的國家。已知他們中任何兩個無共同語言的人中的每一個，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個人排在圓桌旁，使其任何人都能與兩邊的人交談。解答

設(shè)8個人分別為v1,v2,…,v8，作無向簡單圖G＝<V,E>， 其中V＝{v1,v2,…,v8}，vi,vj∈V，且i≠j， 若vi與vj有共同語言，就在vi,vj之間連無向邊(vi,vj)， 由此組成邊集合E，則G為8階無向簡單圖， vi∈V，d(vi)為與vi有共同語言的人數(shù)。 由已知條件可知，vi,vj∈V且i≠j，均有d(vi)+d(vj)≥8。 由定理15.7的推論可知，G中存在哈密頓回路， 設(shè)C＝vi1vi2…vi8為G中一條哈密頓回路， 按這條回路的順序安排座次即可。哈密頓圖是能將圖中所有頂點都能安排在某個初級回路上的圖。定理15.9定理15.9若D為n(n≥2)階競賽圖，則D中具有哈密頓通路。證明

對n作歸納法。

n＝2時，D的基圖為K2，結(jié)論成立。 設(shè)n＝k時結(jié)論成立。現(xiàn)在設(shè)n＝k+1。 設(shè)V(D)＝{v1,v2,…,vk,vk+1}。 令D1＝D-vk+1，易知D1為k階競賽圖， 由歸納假設(shè)可知，D1存在哈密頓通路， 設(shè)Г1＝v1v2…vk為其中一條。定理15.9下面證明vk+1可擴到Г1中去。若存在vr(1≤r≤k)，有<vi,vk+1>∈E(D)，i＝1,2,…,r-1，而<vk+1,vr>∈E(D)，見左圖所示，則Г＝v1v2…vr-1vk+1vr…vk為D中哈密頓通路。否則i∈{1,2,…,k}，均有<vi,vk+1>∈E(D)，見右圖所示，則Г＝Г∪<vi,vk+1>為D中哈密頓通路。例15.6下圖所示的三個圖中哪些是哈密頓圖？哪些是半哈密頓圖？(1)存在哈密頓回路，所以(1)為哈密頓圖。(2)取V1＝{a,b,c,d,e}，從圖中刪除V1得7個連通分支，由定理15.6和推論可知，不是哈密頓圖，也不是半哈密頓圖。(3)取V1＝{b,e,h}，從圖中刪除V1得4個連通分支，由定理15.6可知，它不是哈密頓圖。但存在哈密頓通路，所以是半哈密頓圖。15.3帶權(quán)圖與貨郎擔問題定義15.3給定圖G＝<V,E>(G為無向圖或有向圖)，設(shè)W：E→R(R為實數(shù)集)，對G中任意的邊e＝(vi,vj)(G為有向圖時，e＝<vi,vj>)，設(shè)W(e)＝wij，稱實數(shù)wij為邊e上的權(quán)，并將wij標注在邊e上，稱G為帶權(quán)圖，此時常將帶權(quán)圖G記作<V,E,W>。設(shè)GG，

稱W(e)為G的權(quán)，并記作W(G)，即W(G)＝帶權(quán)圖應(yīng)用的領(lǐng)域是相當廣泛的，許多圖論算法都是針對帶權(quán)圖的。貨郎擔問題設(shè)有n個城市，城市之間均有道路，道路的長度均大于或等于0，可能是∞（對應(yīng)關(guān)聯(lián)的城市之間無交通線）。一個旅行商從某個城市出發(fā)，要經(jīng)過每個城市一次且僅一次，最后回到出發(fā)的城市，問他如何走才能使他走的路線最短？ 這就是著名的旅行商問題或貨郎擔問題。這個問題可化歸為如下的圖論問題。 設(shè)G＝<V,E,W>，為一個n階完全帶權(quán)圖Kn，各邊的權(quán)非負，且有的邊的權(quán)可能為∞。求G中一條最短的哈密頓回路，這就是貨郎擔問題的數(shù)學(xué)模型。此問題中不同哈密頓回路的含義： 將圖中生成圈看成一個哈密頓回路，即不考慮始點(終點)的區(qū)別以及順時針行遍與逆時針行遍的區(qū)別。例15.7例15.7下圖為4階完全帶權(quán)圖K4。求出它的不同的哈密頓回路，并指出最短的哈密頓回路。解答

由于貨郎擔問題中不同哈密頓回路的含義可知，求哈密頓回路從任何頂點出發(fā)都可以。下面先求出從a點出發(fā)，考慮順時針與逆時針順序的不同的哈密頓回路。

C1＝abcda

C2＝abdca C3＝acbda

C4＝acdba

C5＝adbca

C6＝adcba帶權(quán)圖的說明n階完全帶權(quán)圖中共存在(n-1)!/2種不同的哈密頓回路，經(jīng)過比較，可找出最短哈密頓回路。n＝4時，有3種不同哈密頓回路。

n＝5時，有12種，

n＝6時，有60種，

n＝7時，有360種，…，

n＝10時，有5×9!=1814400種，…。由此可見貨郎擔問題的計算量是相當大的。對于貨郎擔問題，人們一方面還在尋找好的算法，另一方面也在尋找各種近似算法。中國郵遞員問題一名郵遞員帶著要分發(fā)的郵件從郵局出發(fā)，經(jīng)過要分發(fā)的每個街道，送完郵件后又返回郵局。如果他必須至少一次走過他管轄范圍內(nèi)的每一條街道，如何選擇投遞路線，使郵遞員走盡可能少的路程。這個問題是由我國數(shù)學(xué)家管梅谷先生（山東師范大學(xué)數(shù)學(xué)系教授）在1960年首次提出的，因此在國際上稱之為中國郵遞員問題。用圖論的述語，在一個連通的賦權(quán)圖G(V,E)中，要尋找一條回路，使該回路包含G中的每條邊至少一次，且該回路的權(quán)數(shù)最小。也就是說要從包含G的每條邊的回路中找一條權(quán)數(shù)最小的回路?；疽笊羁汤斫鈿W拉圖與半歐拉圖的定義及判別定理。會用Fleury算法求出歐拉圖中的歐拉回路。深刻理解哈密頓圖及半哈密頓圖的定義。會用破壞哈密頓圖應(yīng)滿足的某些必要條件的方法判斷某些圖不是哈密頓圖。會用滿足哈密頓圖的充分條件的方法判斷某些圖是哈密頓圖。嚴格地分清哈密頓圖必要條件和充分條件，千萬不能將必要條件當充分條件，同樣地，也不能將充分條件當成必要條件。歸納法證明示意圖例15.4例15.4設(shè)G是n階無向連通圖。證明：若G中有割點或橋，則G不是哈密頓圖。證明 (1)證明若G中有割點，則G不是哈密頓圖。

設(shè)v為連通圖G中一個割點，則V＝{v}為G中的點割集，而

p(G-V)≥2＞1＝|V| 由定理15.6可知G不是哈密頓圖。 (2)證明若G中有橋，則G不是哈密頓圖。 設(shè)G中有橋，e＝(u,v)為其中的一個橋。 若u,v都是懸掛邊，則G為K2，K2不是哈密頓圖。 若u,v中至少有一個，比如u，d(u)≥2，由于e與u關(guān)聯(lián)，e為橋，所以G-u至少產(chǎn)生兩個連通分支，于是u為G中割點。 由(1)的討論可知，G不是哈密頓圖。匹配§1最大匹配－1具體問題描述：有n個女士和n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女舞伴相識。f1f2m1f3f4f5m2m3m4m5§1匹配§1最大匹配－1下圖就是一種分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)

匹配問題是運籌學(xué)的重要問題之一，也是圖論的重要內(nèi)容，它在所謂“人員分配問題”和“最優(yōu)分配問題”中有重要作用。假定有一個男生有窮集合，其中每個男生認識一些女生，在什么條件下每個男生都可以和他認識的女生配對？類似的工作分配問題：現(xiàn)有n個人，m份工作，每個人有其擅長的工作。在什么條件下每個人都可以得到一份他擅長的工作？如何分配？§1最大匹配－定義定義：若圖G=(V,E)的頂點可以分成X，Y兩個子集，每個子集里的頂點互不相鄰，這樣的圖稱為二分圖。f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義1定義：若M是圖G=(V,E)的邊子集，且M中的任意兩條邊在G中不相鄰，則稱M為G中的一個匹配，M中的每條邊的兩個端點稱為是M-飽和的的。f1f2m1f3f4f5m2m3m4m5M={(f1,m2),(f2,m1),(f3,m4),(f4,m5)}§1最大匹配－定義2定義：若圖G中每個頂點均被M許配時，稱M為G中的一個完美匹配。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－定義3定義：圖G中邊數(shù)最多的匹配M，稱為G中的一個最大匹配。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義4定義：若匹配M的某邊和頂點v關(guān)聯(lián)，稱v是M-飽和的，否則就是M-不飽和的。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5飽和的不飽和的§1最大匹配－定義5定義：若M是圖G的一個匹配，若從G中一個頂點到另一個頂點存在一條道路，此路徑由屬于M和不屬于M的邊交替出現(xiàn)組成的，則稱此路徑為M-交錯路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}P=f1m3f4m5f2m1f5m4§1最大匹配－定義6定義：若交錯路的兩個端點為關(guān)于M的不飽和頂點時，稱此交互道為可增廣道路。M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一條可增廣道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義8f1f2m1f3f4f5m2m3m4m5M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一條可增廣道路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－Berge定理定理7.1(Berge1957)：M為最大匹配的充要條件是：圖G中不存在可增廣道路。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5[引理]

設(shè)P是匹配Ｍ-可增廣道路，則PM是一個比M更大的匹配，且|PM｜＝|M|+1.[定理1](Berge)設(shè)G=(V,E)，M為G中匹配，則M為G的最大匹配當且僅當G中不存在M可增廣道。[證明]

必要性：如有M-可增廣道路，則有更大匹配。矛盾！充分性：如果有最大匹配M’,|M’|>|M|.考慮MM’，在可增廣路中，第一條邊與最后一條邊都不是中的邊，因而可增廣路中屬于的邊數(shù)比不在中邊數(shù)少一條。M實線邊，M’虛線邊MM’其中每個結(jié)點的最多與Ｍ邊和一個M’邊關(guān)聯(lián)，每條道路是M邊和M’邊交互道路。其中回路包含相同數(shù)目的M邊和M’邊。由|M’|>|M|,必存在M’邊開始，M‘邊終止的M交互道路，即M-可增廣道路，矛盾！§2Hall定理

設(shè)有m個人，n項工作，每個人會做其中的若干項工作，能不能適當安排，使得每個人都有工作做？w1w2m1w3w4w5m2m3m4§2Hall定理

當m>n時，肯定是不可能的，即使是m≤n也不一定。但如果每個人能做的工作越多，越容易實現(xiàn)。w1w2m1w3w4w5m2m3m4§2Hall定理－1Hall定理(1935)：二分圖G存在一匹配M，使得X的所有頂點關(guān)于M飽和的充要條件是：對于X任一子集A，及與A鄰接的點集為N(A)，恒有：|N(A)|≥|A|。w1w2m1w3w4w5m2m3m4YX§3人員分派問題1965年，匈牙利著名數(shù)學(xué)家Edmonds設(shè)計了一種求最大匹配的算法，稱為匈牙利(Hungarian)算法。工作分配問題：現(xiàn)有n個人，n份工作，每個人有其擅長的工作。在什么條件下每個人都可以得到一份他擅長的工作？如何分配？§3匈牙利算法

匈牙利(Hungarian)算法：（1）任給一個初始匹配；（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；（3）在X中找一個非飽和點x0，V1={x0}，V2=空集；（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2；（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】§3匈牙利算法例用匈牙利算法求下圖的最大匹配：例x1x2y1x3x4x5y2y3y4y5§3匈牙利算法例解（1）任給一個初始匹配；（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}§3匈牙利算法例解1（3）在X中找一個非飽和點x0，V1={x0}，V2=空集（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2},V2=空集N(V1)={y2,

y3}§3匈牙利算法例解2（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1=V1∪{x5}={x2,x5}；V2=V2∪

{y3}

={y3}V1={x2},V2=空集§3匈牙利算法例解3（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}N(V1)={y2,y3,y4,y5}§3匈牙利算法例解4（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}；V1=V1∪{x3}={x2,x5,x3}；V2=V2∪

{y5}

={y3,y5}§3匈牙利算法例解5（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,

x3}；V2={y3,y5}；N(V1)={y2,y3,y4,y5}§3匈牙利算法例解6（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,x3}；V2={y3,y5}；x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}?§3匈牙利算法例解7（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；（3）在X中找一個非飽和點x0，V1={x0}，V2={}（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}N(V1)={y3}§3匈牙利算法例解8（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1=V1∪{x2}={x4,x2}；V2=V2∪{y3}

={y3}§3匈牙利算法例解9（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}N(V1)={y2,y3}§3匈牙利算法例解10（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}V1=V1∪{x3}={x4,x2,x3}；V2=V2∪{y2}

={y3,y2}§3匈牙利算法例解11（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}N(V1)={y2,y3,y5}§3匈牙利算法例解12（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}V1=V1∪{x5}={x4,x2,x3,x5}；V2=V2∪{y5}

={y3,y2,y5}§3匈牙利算法例解13（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,x5}；V2={y3,y2,y5}N(V1)={y2,y3,y5,y4}§3匈牙利算法例解14（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,

x5}；V2={y3,y2,y5}x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}?§3匈牙利算法例解15（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；解x1x2y1x3x4x5y2y3y4y5

這時，M={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}就是所求的最大匹配。§4最佳匹配

公司里有n名工作人員，他們每個人都能承擔n項工作的其中若干項，因為每個人的特長不同，所以對每項工作創(chuàng)造的價值也有所不同。問如何安排，使得他們總的創(chuàng)造價值最大？§4最佳匹配x對每項工作創(chuàng)造的價值的如右邊的矩陣所表示：x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5§5最佳匹配算法及例Kuhn和Munkras設(shè)計了求最佳匹配的有效算法，他們把求最佳匹配的問題轉(zhuǎn)化成可用匈牙利算法求另一個圖的完美匹配的問題?！?最佳匹配算法1

為此，他們對加權(quán)的二分圖每個頂點v給一個頂標l(v)，當xi∈X，yj∈Y，l(xi)+l(yj)≥cij時，稱這樣的頂標為可行頂點a標號（feasiblevertexlabelling）?！?最佳匹配算法2初始的時候，令l(xi)=maxci*；l(yi)=0；x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0最佳匹配定理設(shè)二分圖Kn,n=G是具有正常頂標l的加權(quán)圖，取G的邊子集El={eij|eij∈E(G),l(i)+l(j)=cij}。令Gl是以El為邊集的生成子圖，如果有Gl完美匹配M，則M即為G的最佳匹配。x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5§5最佳匹配算法3KM算法：（1）選定初始正常標頂l，構(gòu)作圖Gl，在Gl中用匈牙利算法求一個最大匹配；（2）若X飽和則結(jié)束，此時所得匹配就是最佳匹配，否則在X中任選一個非飽和點x0，令V1={x0}，V2={}；（3）若NGl(V1)=V2，則取α=min(l(xi)+l(yj)-cij)，其中xi∈V1，yj∈NG(V1)-V2，使得

l(v)-αv∈V1

l(v)=l(v)+αv∈V2

l(v)其他

重新構(gòu)作圖Gl，在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）；否則在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）§5最佳匹配算法4（4）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】§5最佳匹配算法例求下圖的最佳匹配例x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5§5最佳匹配算法例解1（1）選定初始正常標頂l，構(gòu)作圖Gl，在Gl中用匈牙利算法求一個最大匹配；解x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1