離散數(shù)學及其應(yīng)用-第2版 課件 第9章特殊圖

第9章

特殊圖第9章特殊圖9.1歐拉圖與哈密頓圖9.2帶權(quán)圖9.3匹配和二分圖9.4平面圖9.1歐拉圖與哈密頓圖哥尼斯堡七橋問題、周游世界問題歐拉圖定義9.1.1

設(shè)G=（V，E）是無向圖或有向圖，若G中有一條包含所有邊（有向邊）的簡單回路，稱該回路為歐拉回路，稱圖G為歐拉圖。若G中有一條包含G中所有邊（有向邊）的簡單通路，稱它為歐拉通路，稱圖G為半歐拉圖。歐拉圖半歐拉圖例題b-c-d-b-e-c-a-b

b-d-c-e-b-a-c

例9.1.1

在下面的圖中，哪些有歐拉回路？沒有歐拉回路的圖中，哪些有歐拉通路？歐拉圖的判斷定理9.1.1

無向連通圖G是歐拉圖，當且僅當G的所有結(jié)點的度數(shù)都是偶數(shù)。定理9.1.2

連通無向圖G為半歐拉圖，當且僅當G中只有兩個奇度數(shù)的結(jié)點。定理9.1.1證明定理9.1.1

無向連通圖G是歐拉圖，當且僅當G的所有結(jié)點的度數(shù)都是偶數(shù)。證明：（必要性）設(shè)G是歐拉圖，則G有歐拉回路C。設(shè)a是圖G的任一結(jié)點，歐拉回路經(jīng)過和a關(guān)聯(lián)的邊到結(jié)點a后又經(jīng)過另一條和a關(guān)聯(lián)的邊離開到下一個結(jié)點b，因此每經(jīng)過一個結(jié)點a就給它的度數(shù)貢獻2度。若歐拉回路k次經(jīng)過結(jié)點a，則d（a）=2k。所以，歐拉圖的所有結(jié)點的度數(shù)都是偶數(shù)。（充分性）假設(shè)G中所有結(jié)點的度數(shù)都是偶數(shù)。從G中的任一結(jié)點v1開始，經(jīng)過任一和v1關(guān)聯(lián)的邊e1到另一結(jié)點v2，再經(jīng)過另一和v2關(guān)聯(lián)的邊e2到另一結(jié)點v3，

依此類推，可以得到一條包含G的邊的簡單回路C1：v1

e1

v2

e2

v3

em

v1。定理9.1.2證明定理9.1.2

連通無向圖G為半歐拉圖，當且僅當G中只有兩個奇度數(shù)的結(jié)點,其余結(jié)點的出度和入度相等。證明在連通無向圖G的兩個奇度數(shù)的結(jié)點之間加一條邊e得到圖G

，則圖G

的所有結(jié)點的度數(shù)都是偶數(shù)，有歐拉回路。在G

的歐拉回路中刪去這條邊e，則可得到一條包含G中所有邊的歐拉通路。因此圖G是半歐拉圖。例題例9.1.2

在下圖中，哪些是歐拉圖？哪些是半歐拉圖？歐拉圖歐拉圖半歐拉圖歐拉有向圖定義9.1.2

如果連通有向圖G中有一條包含G中所有有向邊的有向回路，稱它為歐拉有向回路，稱圖G為歐拉有向圖。如果連通有向圖G中有一條包含G中所有有向邊的有向通路，稱它為歐拉有向通路，稱圖G為半歐拉有向圖。歐拉有向圖半歐拉有向圖歐拉有向圖的判斷定理9.1.3

連通有向圖G是歐拉圖，當且僅當G中每個結(jié)點v的入度等于它的出度。定理9.1.4

連通有向圖G是半歐拉圖，當且僅當G中有且僅有兩個奇度數(shù)結(jié)點，其中一個結(jié)點的入度比出度大1，另一個結(jié)點的入度比出度小1。例題例9.1.3

在圖中，哪些是歐拉圖？哪些是半歐拉圖？歐拉圖半歐拉圖9.1.2哈密頓圖環(huán)游世界問題哈密頓圖定義9.1.3

設(shè)圖G=（V，E）是無向圖或有向圖。若G中有一條包含G的所有結(jié)點(僅一次)的回路，稱該回路為哈密頓回路，稱圖G為哈密頓圖。若圖G有一條包含G的所有結(jié)點的通路，稱該通路為哈密頓通路，稱圖G為半哈密頓圖。(1)是半哈密爾頓圖(2)為哈密爾頓圖(3)沒有哈密頓通路，也沒有哈

密頓回路哈密頓圖存在的必要條件定理9.1.5

設(shè)無向圖G=（V，E）是哈密頓圖，則對于結(jié)點集V的每一個真子集S均有：W(G-S)

|S|,其中，W(G-S)是G-S的導出子圖的連通分支數(shù)。例如：彼德森圖中對于結(jié)點集V的每一個真子集S均有：W(G-S)

|S|。但彼德森圖不是哈密頓圖。哈密頓圖存在的必要條件證明：設(shè)C為G中的一條哈密爾頓回路。對于V的任何一個非空子集S，在C中刪去S中任一結(jié)點v1，則C-v1是連通的非回路。若再刪去任一結(jié)點v2，分兩種情況討論：如v2

和v1鄰接，則C-v1-v2是連通的；如v2

和v1不鄰接，則C-v1-v2是不連通的，W(C-v1-v2)=2。所以，刪去兩個結(jié)點時有W(C-v1-v2)

2。依此類推，顯然有W(C-S)

|S|。又因為C是G的生成子圖，所以C-S是G-S的生成子圖，因而W(G-S)

W(C-S)。因此有W(G-S)

|S|。例題例9.1.4

說明下圖

所示的無向圖G不是哈密頓圖。解

在圖中刪去結(jié)點集S={v2，v4，v6，v8}，W(G?S)=5，不滿足W(G-S)

|S|。所以G不是哈密頓圖。哈密頓圖存在的充分條件定理9.1.6

如果G是有n個結(jié)點的簡單無向圖，對于每一對不鄰接結(jié)點u和v，滿足d(u)+d(v)

n-1，那么G中存在哈密頓通路，圖G是半哈密頓圖。證明：首先用反證法證明圖G是連通的。假設(shè)圖G不連通，它至少有兩個連通分支G1=（V1，E1）和G2=（V2，E2）。取任意結(jié)點v1

V1，v2

V2，因為G是簡單無向圖，所以d（v1）

|V1|-1，d（v2）

|V2|-1，因而d（v1）+d（v2）

|V1|+|V2|-2=n-2，與已知條件矛盾，所以圖G是連通的。定理9.1.6證明（續(xù)1）證明：證明G中存在哈密頓通路。設(shè)L：v1v2

vk

是G的最長的基本通路，顯然k

n。因為L是G的最長的基本通路，所以v1

和

vk的鄰接點都在L上。若k=n，則L為G中經(jīng)過所有結(jié)點的通路，即為哈密頓通路。若k<n，說明G中存在不在L上的結(jié)點。此時可以證明存在僅經(jīng)過L上的所有結(jié)點的基本回路，證明如下：第一種情況：若在L上v1和vk相鄰，則v1v2

vkv1是經(jīng)過L上所有結(jié)點的基本回路。定理9.1.6證明（續(xù)2）第二種情況：若在L上v1和vk不相鄰，設(shè)v1與L上的結(jié)點

vj1=v2,vj2,

vjm相鄰（m

2，否則d(v1)+d(vk)

1+k-2<n-1），這時vk必與vj2

vjm

的鄰接結(jié)點vj2-1

vjm-1之一相鄰（否則d(v1)+d(vk)

m+k-2-(m-1)<n-1）。設(shè)vk與vjr-1（2

r

m）相鄰，如圖所示。在L中添加邊（v1,vjr），（vk，vjr-1），刪除邊（vjr，vjr-1）得基本回路C=v1v2

vjr-1vkvk-1

vjrv1，經(jīng)過L上的所有結(jié)點。定理9.1.6證明（續(xù)3）證明存在比L更長的通路。因為k

n，G中必有不在L上的結(jié)點vk+1。由于G是連通的，vk+1與L上的一個結(jié)點vt鄰接，在L上刪除邊（vt-1，vt），添加邊（vt，vk+1），于是可得到一條長度為k+1的基本通路vt-1

v1vjr

vkvjr-1

vtvk+1。重復（1）~（3），由于G中的結(jié)點數(shù)目有限，一定能在有限步內(nèi)得到一條哈密頓通路。哈密頓圖的充分條件推論1

如果圖G是有n個結(jié)點的簡單無向圖，對于每一對不鄰接結(jié)點u和v，滿足d(u)+d(v)

n，那么G中存在哈密頓回路，圖G是哈密頓圖。推論2

如果G是有n個結(jié)點的簡單無向圖，G中每個結(jié)點的度數(shù)都至少為n/2，那么圖G是哈密頓圖。例題半哈密頓圖哈密頓圖非哈密頓圖

非半哈密頓圖應(yīng)用1例9.1.5有7個人,A會講英語,B會講英語和漢語,C會講英語、意大利語和俄語,D會講日語和漢語,E會講德語和意大利語,F會講法語、日語和俄語,G會講法語和德語.問能否將他們沿圓桌安排就坐成一圈,使得每個人都能與兩旁的人交談?圖G的一條哈密頓回路是ABDFGECA，按這條哈密頓回路安排就坐成一圈,每個人都能與兩旁的人交談。應(yīng)用2-格雷碼例9.1.6

在一組數(shù)的編碼中，若任意兩個相鄰的代碼只有一位二進制數(shù)不同，則稱這種編碼為格雷碼。表9.1.1是2位格雷碼，表示數(shù)0~3，表9.1.2是3位格雷碼，表示數(shù)0~7。格雷碼用格雷碼表示的最大數(shù)與最小數(shù)之間也僅一位數(shù)不同，即“首尾相連”，因此這種編碼又稱循環(huán)碼。在數(shù)字系統(tǒng)中，常要求代碼按一定順序變化。例如，按自然數(shù)遞增計數(shù)，若采用8421碼，則數(shù)0111變到1000時四位均要變化，而在實際電路中，4位的變化不可能絕對同時發(fā)生，則計數(shù)中可能出現(xiàn)短暫的其它代碼（如0110、1111等）。在特定情況下可能導致電路狀態(tài)錯誤或輸入輸出錯誤。使用格雷碼，變化到下一狀態(tài)時只有1位不同，可以避免這種錯誤。格雷碼要找到格雷碼，可以用n立方體Qn來建模。在Qn圖上找一條哈密頓回路，按哈密頓回路上的結(jié)點順序?qū)?yīng)的二進制碼序列就是格雷碼。例如，9.2帶權(quán)圖設(shè)G=<V,E,W>，V={v1，v2，…，vn}是頂點集合，E是邊集合，W:VVR是賦值函數(shù)。旅行商問題(TSP)完全無向圖的每個結(jié)點表示一個城市，用兩個城市之間的距離作為邊的權(quán)，可以得到一個邊帶權(quán)的完全無向圖。旅行商問題是在這樣的圖中尋找一條旅行總距離最短的經(jīng)過每個城市一次且僅一次，又回到出發(fā)城市的旅行線路的問題。這個問題等價于求帶權(quán)完全圖中總權(quán)值最小的哈密頓回路。9.2.1旅行商問題47,36,35旅行商問題n個結(jié)點的圖上，以每個結(jié)點為起點的所有的哈密頓回路共有(n-1)!條，需要計算(n-1)!/2條回路的權(quán)值來求出答案。當結(jié)點較多時用這種方法解決旅行商問題是不切實際的，常用近似算法求解旅行商問題。

9.2.2最短路徑問題在一個無向簡單連通邊帶權(quán)圖G=（V，E，W）中，從u到v的一條通路中包含的各條邊的權(quán)值之和稱為這條通路的長度。從u到v的所有通路中長度最短的通路稱為u到v的最短路徑。求給定兩結(jié)點之間的長度最短的通路問題稱為最短路徑問題uadv是u到v的最短路徑Dijkstra算法算法思想：構(gòu)造一個結(jié)點集S。首先在圖中的除u外的所有結(jié)點中找到距離u最近的結(jié)點，把該結(jié)點加入結(jié)點集S后，在剩余的結(jié)點中再求距離u最近的結(jié)點，按和u距離由近到遠依次加入S，直到把結(jié)點v加入結(jié)點集S，即求得從u到v的最短路徑。Dijkstra算法方法：采用給結(jié)點標記距離值的方法構(gòu)造結(jié)點集S。加入到S中的結(jié)點標記為永久性標記，未加入到S中的結(jié)點標記為臨時性標記放在集合T中。一個結(jié)點的永久性標記值是從u到該點的最短路徑的長度。首先將u標記為0，其余結(jié)點為臨時標記，值為

，然后通過逐步修改臨時標記的結(jié)點的標記值，將其中的最小標記值的結(jié)點從集合T中移出，加入到集合S中。當結(jié)點v被加入到集合S中時，它的標記值就是從u到v的最短路徑的長度，則求得從u到v的最短路徑。Dijkstra算法若圖G的結(jié)點u=v0，v1，，vn=v，權(quán)為W（vi，vj），如果（vi，vj）不是圖G的邊則W（vi，vj）=

。引入一個“中轉(zhuǎn)點”標記t，如果兩個結(jié)點vi和vj間路徑長度，大于這兩點通過“中轉(zhuǎn)點”連接的路徑長度，那么就修改這兩點間的路徑為vi-t-vj.Dijkstra算法步驟（1）初始化標記值。起始結(jié)點u的標記值為0，其余結(jié)點臨時標記值為

，即L（u）=0，L（vi）=

，i=1，2，，n。S={u}，其余結(jié)點在集合T中。（2）修改集合T中和結(jié)點u相鄰的結(jié)點vi的標記值：L（vi）=L（u）+W（u，vi）。（3）將集合T中具有最小標記值的結(jié)點移出，添加到結(jié)點集S中，并將該結(jié)點記為中轉(zhuǎn)點t。（4）修改集合T中和中轉(zhuǎn)點t相鄰的結(jié)點vj的標記值：L（vj）=min（L（vj），L（t）+W（t，vj））。重復（3）和（4）直到結(jié)點v被添加到集合S中。Dijkstra算法9.2.3中國郵路問題一名郵遞員帶著要分發(fā)的郵件從郵局出發(fā)，經(jīng)過要分發(fā)的每個街道，送完郵件后又返回郵局．如果他必須至少一次走過他負責范圍內(nèi)的每一條街道，如何選擇投遞路線，郵遞員可以走盡可能少的路程？這個問題是由我國數(shù)學家管梅谷先生（山東師范大學數(shù)學系教授）在1962年首次提出的，因此在國際上稱之為中國郵路問題．用圖論的術(shù)語，在一個連通的帶權(quán)圖G=（V，E，W）中，要尋找一條回路，使該回路包含G中的每條邊至少一次，且該回路的總權(quán)值最小，也就是說要從包含G的每條邊的回路中找一條總權(quán)值最小的回路。中國郵路問題如果G是歐拉圖，只要求出圖G的一條歐拉回路即可。因此問題就轉(zhuǎn)化為：在一個連通的帶權(quán)圖G（V，E，W）中，要尋找一條回路，使該回路包含G中的每條邊至少一次（當圖G不是歐拉圖時可能包含一些邊超過一次），且該回路的總權(quán)值最小。中國郵路問題首先注意到，若圖G有奇數(shù)度結(jié)點，則G的奇數(shù)度結(jié)點必是偶數(shù)個．把奇數(shù)度結(jié)點配為若干對，每對結(jié)點之間在G中有相應(yīng)的最短路，將這些最短路畫在一起構(gòu)成一個附加的邊子集E1．令G1=G+E1，即把附加邊子集E1

疊加在原圖G上形成一個多重圖G1，這時G1中沒有奇度數(shù)結(jié)點．顯然G1是一個歐拉圖，因而可以求出G1的歐拉回路．該歐拉回路不僅通過原圖G中每條邊，同時還通過E1

中的每條邊，且均僅一次．郵遞員問題的難點在于當G的奇數(shù)度節(jié)點較多時，可能有很多種配對方法，應(yīng)怎樣選擇配對，能使相應(yīng)的附加邊子集E1

的權(quán)數(shù)W(E1)為最小。中國郵路問題定理9.2.1設(shè)G（V，E，W）為一個連通的帶權(quán)圖，則使附加邊子集E1

的各條邊的權(quán)值和W(E1)為最小的充分必要條件是G+E1

中任意邊至多重復一次，且G+E1

中的任意回路中重復邊的權(quán)值之和不大于該回路各條邊的權(quán)值和的一半。證明

（略）中國郵路問題先找出奇結(jié)點；對奇結(jié)點進行配對，找到每對結(jié)點間的一個基本通路，給每條通路所含的邊加一條平行邊；刪去多于兩條的重復邊；檢查每一條回路，若一條回路中重復邊的權(quán)值和大于該回路權(quán)值的一半，把該回路的重復邊刪去，在沒有平行邊的邊上加上平行邊；若沒有任何回路的重復邊的權(quán)值之和大于該回路權(quán)值的一半，圖中的任意一條歐拉回路就是最優(yōu)郵路．中國郵路問題

（a)(b)

（c)(d)9.2.4關(guān)鍵路徑定義9.2.1：在一個表示工程的帶權(quán)有向圖中，用結(jié)點表示事件（如v0），用有向邊表示活動（如<v0,v1>=a1），邊上的權(quán)值表示活動的持續(xù)時間，稱這樣的有向圖為邊表示的活動的網(wǎng)，簡稱AOE網(wǎng)（activityonedgenetwork）。在AOE網(wǎng)中，入度為0的結(jié)點稱為源點，出度為0的結(jié)點稱為匯點。定義9.2.2：在AOE網(wǎng)中，具有最大路徑長度的路徑稱為關(guān)鍵路徑，關(guān)鍵路徑上的活動稱為關(guān)鍵活動。。AOE網(wǎng)在AOE網(wǎng)中，假設(shè)源點是v0，從v0到vi的最長路徑長度叫做事件vi的最早發(fā)生時間，記為ve[i]。在AOE網(wǎng)中，只有結(jié)點vj代表的事件發(fā)生，以vj為起點的活動ai才能開始，即活動ai的最早開始時間等于該活動的起點表示的事件vj的最早開始時間?；顒觓i的最早開始時間記為ae[i]，ae[i]=ve[j]。在不推遲整個工程完成的前提下，活動ai最遲必須開始的時間是該活動的終點表示的事件的最遲發(fā)生時間和該活動的持續(xù)時間的差，稱為活動ai的最遲開始時間，記為al[i]。在不推遲整個工程完成（即保證結(jié)束結(jié)點vn在ve[n]時刻發(fā)生）的前提下，事件vi最遲必須發(fā)生的時間，稱為事件vi的最遲發(fā)生時間，記為vl[i]。關(guān)鍵活動al[i]=ae[i]的活動稱為關(guān)鍵活動，要識別AOE網(wǎng)的關(guān)鍵活動就是找al[i]=ae[i]的活動。求al[i]和ae[i]：首先應(yīng)求得事件的最早發(fā)生時間ve[i]和最遲發(fā)生時間vl[i]?；顒觓i由有向邊<vi,vj>表示，持續(xù)時間記為weight(<vi,vj>),則活動ai的最早開始時間等于事件vi的最早發(fā)生時間，即ae[i]=ve[i]。活動ai的最遲開始時間等于事件vj的最遲發(fā)生時間減去活動的持續(xù)時間，即al[i]=vl[i]-weight(<vi,vj>)。關(guān)鍵活動ve[i]和vl[i]可以用下面的遞推公式，分兩步計算。第一步：從源點向匯點方向遞推計算ve[i]。從指向事件vj的有向邊的活動中，取最晚完成的一個活動的完成時間作為vj的最早發(fā)生時間ve[i]，即：ve[源點]=0，ve[j]=max(ve[i]+weight<vi,vj>)，<vi,vj>為所有到達vj的有向邊。第二步：從匯點向源點方向遞推計算vl[i]。由上一步可以求得匯點的最早發(fā)生時間ve[匯點]。因為匯點就是結(jié)束點，最遲發(fā)生時間和最早發(fā)生時間相同，即vl[匯點]=ve[匯點]。從結(jié)點vi出發(fā)的有向邊表示的的活動中，取最早開始的活動的開始時間作為vi的最遲發(fā)生時間vl[i]，即：vl[匯點]=ve[匯點]，vl[i]=min(vl[j]-weight<vi,vj>)，<vi,vj>為所有從vi出發(fā)的有向邊。例題例9.2.3：求圖8.2.6的AOE網(wǎng)的關(guān)鍵路徑。解：從源點向匯點方向遞推計算事件的最早發(fā)生時間：ve[1]=0ve[2]=ve[1]+a1=0+3=3ve[3]=ve[1]+a2=0+2=2ve[4]=max(ve[2]+a3,ve[3]+a4)=max(3+2,2+4）=6ve[5]=ve[2]+a5=3+3=6ve[6]=max(ve[5]+a7,ve[4]+a6，ve[3]+a8)=max(6+2,6+1，2+6)=8從匯點向源點方向遞推計算事件的最遲發(fā)生時間：vl[6]=ve[6]=8vl[5]=vl[6]-a7=8-2=6vl[4]=vl[6]-a6=8-1=7vl[3]=min(vl[6]-a8，vl[4]-a4）=min(8-6，7-4)=2vl[2]=min(vl[5]-a5，vl[4]-a3)=min(6-3,7-2)=3vl[1]=min(vl[2]-a1，vl[3]-a2)=min(3-3,3-2)=0例題（續(xù)）活動的最早發(fā)生時間：ae[1]=ve[1]=0ae[2]=ve[1]=0ae[3]=ve[2]=3ae[4]=ve[3]=2ae[5]=ve[2]=3ae[6]=ve[4]=6ae[7]=ve[5]=6ae[8]=ve[3]=2活動的最遲發(fā)生時間：al[1]=vl[2]-a1=3-3=0al[2]=vl[3]-a2=2-2=0al[3]=vl[4]-a3=7-2=5al[4]=vl[4]-a4=7-4=3al[5]=vl[5]-a5=6-3=3al[6]=vl[6]-a6=8-1=7al[7]=vl[6]-a7=8-2=6al[8]=vl[6]-a8=8-6=2關(guān)鍵活動有：a1、a2、a5、a7、a8，所以關(guān)鍵路徑為v1-v2-v5-v6和v1-v3-v6。一個AOE網(wǎng)的關(guān)鍵路徑可能有多條。9.2.5網(wǎng)絡(luò)與網(wǎng)絡(luò)流定義9.2.3：設(shè)G=（V，E）是一個無多重邊和環(huán)的有向連通圖，V是結(jié)點集，E是弧集。若圖G滿足如下條件：只有一個結(jié)點的入度為0，記為s，稱為源點；只有一個結(jié)點的出度為0，記為t，稱為匯點；在弧集E上定義一個非負整數(shù)集合C={cij}，每條弧(vi,vj)

E都有一個非負的權(quán)值cij，稱之為弧的容量；則稱圖G是一個網(wǎng)絡(luò)或流網(wǎng)絡(luò)，記為G=（V，E，C）。稱源點和匯點以外的其他結(jié)點為中間點。有向邊也稱為弧。流網(wǎng)絡(luò)網(wǎng)絡(luò)與網(wǎng)絡(luò)流定義9.2.4：在網(wǎng)絡(luò)G=（V，E，C）的弧集E上定義一個非負整數(shù)值函數(shù)f:(vi,vj)→{fij=f(vi,vj)},f滿足下列條件：(1)容量限制：對

e=(vi,vj)

E，有fij≤cij；(2)流量守恒：對于除s和t外的每個中間點k，稱f為網(wǎng)絡(luò)G上的一個可行流，簡稱流，稱fij

為弧(vi,vj)上的流量。若無弧（i,j)，則fij

定義為0。如果弧e=(vi,vj)滿足fij

=cij，則稱e為飽和弧，若fij<cij，則稱e為非飽和??；稱fij

=0的弧為零流弧，fij>0的弧為非零流弧。網(wǎng)絡(luò)流圖用cij/fij表示弧(vi,vj)上的容量和流量。容量限制是流經(jīng)每條弧的流量值應(yīng)當不超過該弧的容量，流量守恒是對于除s和t外的每個中間點k，總流入量和總流出量應(yīng)當守恒，即流量不生成也不損耗。最大流定義8.2.5：設(shè)f是網(wǎng)絡(luò)G的一個流，源s的總流出量

，稱為流

f的流量或者值。若G中無可行流f'，使Vf'>Vf，則稱f為最大流。由于匯t的總流入量

，所以對于s和t有最小割定義9.2.6：設(shè)G=（V，E，C）是一個單源單匯網(wǎng)絡(luò)。S?V,

T=V-S.用(S,T)表示起點在S中而終點在T中的所有弧的集合。若(S,T)是圖G的弧割集，而且源點s∈S,匯點t∈T,則稱弧割集(S,T)為網(wǎng)絡(luò)G的一個s-t割。s-t割(S,T)的容量是指從S穿出，進入T的各條弧的容量之和，記為Cap(S,T)，即：定義8.2.7：對于網(wǎng)絡(luò)G的s-t割(S,T)，若不存在s-t割(S',T')，使得Cap(S',T')

Cap(S,T)，則稱(S,T)為最小割。定理定理9.2.2：對于給定的網(wǎng)絡(luò)G=（V，E，C），設(shè)f是一個可行流，(S,T)是任一s-t割，則Vf≤Cap(S,T)。定理9.2.2告訴我們，網(wǎng)絡(luò)G中任何可行流f的值小于等于任一割的容量，因而有最大流的值小于等于最小割的容量。定理定理9.2.3：對于給定的網(wǎng)絡(luò)G=（V，E，C），設(shè)f是一個流，(S,T)是一個s-t割。若Vf=

Cap(S,T),則f是一個最大流且(S,T)是一個最小s-t割。證明：假設(shè)f1是任意一個流，則由定理9.2.2有

，所以f是一個最大流。假設(shè)(S1,T1)是任意一個s-t割，則由定理9.2.2有所以(S,T)是一個最小割。最大流的標號算法(Ford,Fulkerson)1、標號過程給定網(wǎng)絡(luò)G，初始流為f，先給源點s標號（0，

），

(s)=

。選擇一個已標號的結(jié)點vi，對vi所有未標號的相鄰結(jié)點vj，按下列規(guī)則標號:(a)在弧(vi,vj)上,當fij<cij時，則給vj標號(vi,

(vj)),這里

(vj)=min[

(vi),cij-fij)，當fij=cij時，vj不標號。(b)在弧(vi,vj)上,當fji>0時，則給vj標號(-vi,

(vj)),這里

(vj)=min[

(vi),fji)，當fij=0時，vj不標號。重復第（2）步直到收點t被標號為止，或不再有結(jié)點可以標號為止。如果匯點t被標號,表明得到一條從s到t的可增廣路,轉(zhuǎn)入調(diào)整過程。若匯點t未被標號,標號過程進行不下去時,則算法結(jié)束,此時的可行流就是最大流.最大流的標號算法(Ford,Fulkerson)2、調(diào)整過程（1）尋找以t為匯點的可增廣路

若匯點t的第一個標號為vk（或-vk），則弧(vk,t)（相應(yīng)地(t,vk)）是可增廣路上的弧;接下來檢查vk的第一個標號，若為vi（或-vi），則弧(vi,vk)（相應(yīng)地(vk,vi)）是可增廣路上的?。灰来蜗氯?，直到s點為止。此時被找到的弧構(gòu)成可增廣路

。（2）修改流f。對于可增廣路

上的前向弧流量增加

(t),向后弧流量減少

(t),得到新的流f'。流f‘的值為（3）去掉結(jié)點上的標號，對流f'重新進行標號過程。如果在收點t沒有標號，不再有結(jié)點可以標號，算法結(jié)束。用P表示所有已標號的結(jié)點集，

表示所有未標號的結(jié)點集，得到的

是最小割，它的容量等于最大流的值。9.3匹配和二分圖定義9.3.1

在圖G=(V，E)中,若M

E,且M中任意兩條邊都不相鄰，則稱M為G的一個匹配。若在M中再加入任意其它的邊e，M

{e}有相鄰的邊，則稱M為G的極大匹配。若G中不存在匹配M1，使得|M1|>|M|，則稱M為G的最大匹配。定義9.3.2若M是G的一個匹配，M的邊和結(jié)點v關(guān)聯(lián)，則稱v為M飽和點，否則稱v為M非飽和點。若G=（V，E）的每個結(jié)點都是M飽和點，則稱M為G的一個完美匹配。匹配就是邊獨立集，極大匹配就是極大邊獨立集，最大匹配是最大邊獨立集，匹配數(shù)是邊獨立數(shù)。例題(1).{e1,e7}是圖的一個匹配，也是一個極大匹配，{e2,e4,e8}是圖的最大匹配，也是完美匹配。(2).{e2,e6}、{e3,e5}是圖的匹配，也是極大匹配，{e1,e4,e7}是圖的一個最大匹配，也是完美匹配。(3).{e3,e4}、{e1,e5}、{e2,e6}、{e4,e7}等都是極大匹配，也是最大匹配，沒有完美匹配。M交錯路和M可擴充路定義9.3.3若M是G=（V，E）的一個匹配，從G中的一個結(jié)點到另一個結(jié)點存在一條由屬于M的邊和不屬于M的邊交替出現(xiàn)組成的簡單路，則稱這條簡單路為M交錯路。若M交錯路的兩端點為M非飽和點時，稱這條M交錯路是M可擴充路。最大匹配的充分必要條件在圖（1）中，M={e1，e7}是圖的一個匹配，{e2,e1,e4,e7,e8}是M交錯路，而且是M可擴充路。匹配M1={e2,e4,e8}比M更大。

定理9.3.1

M是圖G=(V，E)的最大匹配的充分必要條件是G中不存在M可擴充路。例題求右圖的最大匹配。解

在圖中，M={（v2，v6），（v3，v5），（v4，v7）}是匹配，v1v5v3v6v2v7v4v8是M交錯路，而且是M可擴充路。因此，存在比M更大的匹配M1={（v1，v5），（v3，v6），（v2，v7），（v4，v8）}。由于不存在M1可擴充路，所以M1是最大匹配。9.3.2二分圖定義9.3.4

如果無（有）向圖G=（V，E）的結(jié)點集V能劃分成兩個子集V1和V2，使得G中任何一條邊的兩個端點一個屬于V1，另一個屬于V2，則稱G為二分（部）圖（或二部圖，偶圖），V1和V2稱為互補結(jié)點集，二分圖通常記為G=（V1，V2，E）。若V1中每一結(jié)點與V2中每一個結(jié)點均有且僅有一條邊相關(guān)聯(lián)，則稱二分圖G為完全二分圖。若|V1|=m

，|V2|=n

，則記完全二分圖G為Km，n。注意，n(n>=2）階零圖為二分圖。二分圖例如，一個單位有一些不同類型的工作空缺，有一些應(yīng)聘者申請這些空缺的工作崗位。每個應(yīng)聘者能勝任這些工作中的某些工作。如工作崗位集合為{u1，u2，u3}，應(yīng)聘者集合為{v1，v2，v3，v4，v5}。每個應(yīng)聘者能勝任的工作崗位可以圖9.3.3所示的二分圖表示，其中線uivj表示工作崗位ui適合應(yīng)聘者vj。二分圖完全二分圖二分圖的判斷定理9.3.2

一個無向簡單圖G=（V，E）是二分圖，當且僅當G中無奇數(shù)長度的回路。證明(必要性)設(shè)無向簡單圖G=（V，E）是二分圖，V1

V2=V，V1

V2=

。對于G中任一長度為n的回路可表示為v1e1v2e2

vnenv1。設(shè)v1

V1，則v2

V2，v3

V1，v4

V2

vn

V2。所以n必為偶數(shù)。（充分性）設(shè)無向簡單圖G=（V，E）的所有回路的長度都是偶數(shù)。u是圖G的任一結(jié)點，d（v，u）表示結(jié)點v到結(jié)點u的距離。二分圖的結(jié)點集V的兩個子集可以表示為：V1={v|d(v,u)為偶數(shù)}，V2=V-V1。如果存在一條邊e的兩端點vi和vj都在結(jié)點集V1中，則從vi到vj存在一條有偶數(shù)條邊的通路L。通路L和邊e可以構(gòu)成一條回路，回路的長度為奇數(shù)。和假設(shè)矛盾。同理可證，沒有一條邊的兩端點都在結(jié)點集V2中。由此可見，圖G的每條邊的端點，必定一個在結(jié)點集V1中，另一個在結(jié)點集V2中，而且V1和V2是G的互補結(jié)點集。所以圖G是二分圖。例題判斷圖9.3.6中的圖是否是二分圖。完備匹配和完美匹配定義9.3.5

設(shè)G=（V，E）是二分圖，V1和V2是G的互補結(jié)點集，若G的一個匹配M使得|M|=min{|V1|，|V2|}，稱匹配M是G的完備匹配。這時，若|V1|

|V2|，稱M是從V1到V2的一個完全匹配。如果|V1|=|V2|，稱M是G的完美匹配。完備匹配完美匹配沒有完全匹配完備匹配定理9.3.3（Hall定理）

設(shè)二分圖G=(V,E)，V1和V2

是G的互補結(jié)點集，存在從V1到V2的完備匹配,當且僅當對于V1中的任意k個結(jié)點（k=1,2,,|V1|）至少鄰接V2的k個結(jié)點。

定理9.3.3中的條件通常稱為相異性條件。定理9.3.4

設(shè)G=（V，E）是二分圖，V1和V2

是G的互補結(jié)點集。若存在正整數(shù)t，使（1）V1中的每個結(jié)點至少關(guān)聯(lián)t條邊，（2）V2中的每個結(jié)點至多關(guān)聯(lián)t條邊，則G中存在從V1到V2的完備匹配。定理9.3.4證明證明

由條件（1）可知，V1中的k個結(jié)點至少關(guān)聯(lián)kt條邊（1

k

|V1|）。由條件（2）可知，這些邊至少關(guān)聯(lián)V2中的k個結(jié)點。因此，V1中的k個結(jié)點至少鄰接V2中的k個結(jié)點。由Hall定理,G中存在完備匹配。定理9.3.4的條件常稱為t條件，是判斷二分圖存在完備匹配的充分條件，不是必要條件。

判斷條件t比較簡單，只需計算V1中結(jié)點的最小度數(shù)和V2中結(jié)點的最大度數(shù)。例題要分派5位教師A，B，C，D，E去上課。A可以上課的時間是星期二和星期三，B的時間是星期一和星期三，C的時間是星期四，和星期五，D的時間是星期二和星期五，E的時間是星期一和星期四。應(yīng)如何排課才可以使每天都只有一位教師上課？例題M={（A，p2），（B，p3），（C，p4），（D，p5），（E，p1）}9.4平面圖定義9.4.1

設(shè)G=（V，E）是一個無向圖，如果能把G畫在平面上，使得除結(jié)點處外，任意兩條邊都不相交，則稱G為可平面圖，簡稱平面圖。將一個平面圖G，畫成除結(jié)點處外，任意兩條邊都不相交的和它同構(gòu)的圖，稱這樣的圖為圖G的平面嵌入。例題判斷圖9.4.1中的各圖是否是平面圖。

（1）

（2）

（3）

（4）解

（1）（2）（4）不是平面圖，而(3)是平面圖。

平面圖定義9.4.2設(shè)G是一個平面嵌入，G的邊將G所在的平面劃分成若干個區(qū)域，每個區(qū)域稱為G的一個面。其中，面積無限的區(qū)域稱為無限面或外部面，記成f0，面積有限的區(qū)域稱為有限面或內(nèi)部面，記為f1，f2…，fk

。包圍每個面的所有邊所構(gòu)成的回路稱為該面的邊界。一個面的邊界包含的邊數(shù)稱為該面的次數(shù)，記為deg(f)。平面圖面f0的邊界回路是一個復雜回路，Deg(f0)=9，面f1的邊界回路是環(huán)，Deg(f1)=1，面f2和f3的邊界回路是簡單回路，Deg(f2)=3，Deg(f3)=3定理定理9.4.1

平面圖G的邊數(shù)為e，G的邊將G所在的平面劃分成l個面，所有面的次數(shù)之和等于邊數(shù)e的2倍，即證明

對圖G的每一條邊e，若e在兩個面的公共邊界上，則在計算這兩個面的次數(shù)時，e各提供1.當e只在一個面的邊界上出現(xiàn)時，它必在一個面的邊界上出現(xiàn)2次，如圖

所示，因而在計算這個面的次數(shù)時，e提供2.因此所有面的度數(shù)之和等于邊數(shù)e的2倍。

極大平面圖和極小非平面圖定義9.4.3：設(shè)G為簡單平面圖，若在G的任意兩個不相鄰的結(jié)點之間加一條邊，所得圖為非平面圖，則稱G為極大平面圖。K5和K3,3，刪去任意一條邊都是極大平面圖，另外，K1，K2，K3，K4都是極大平面圖，因為在這些圖中不存在兩個不相鄰的結(jié)點。定義9.4.4:若在非平面圖G中任意刪除一條邊，所得圖為平面圖，則稱圖G為極小非平面圖。K5和K3,3都是極小非平面圖。歐拉公式定理9.4.2

設(shè)G為任意的連通的平面圖，G中有n個結(jié)點，e條邊，f個面，則有公式n-e+f=2成立。該公式稱為歐拉公式。證明

對邊數(shù)e用歸納法。例9.4.2假定連通平面圖G有30條邊，若G的邊把圖分成20個區(qū)域，則這個圖有多少個結(jié)點？解

根據(jù)題意，連通平面圖G的邊數(shù)e=30，面數(shù)f=20，代入歐拉公式n-e+f=2得：n=2+e-f=2+30-20=12所以這個圖有12個結(jié)點。歐拉公式的推論推論1

設(shè)G是有n

（n

3）個結(jié)點，e條邊，f個面的簡單連通平面圖，邊數(shù)e

3n-6。證明

當n=3時，3個結(jié)點的簡單連通平面圖的邊數(shù)e

3,因此e

3n-6成立。當n

3時，G的每個面至少由3條邊圍成，即每個面的度數(shù)deg(fi)

3,所以所有面的總度數(shù)

deg(fi)

3f。而

deg(fi)=2e,因而有2e

3f,即f

2e/3。代入歐拉公式2=n-e+f

n-e+2e/3有e

3n-6成立。因此e

3n-6成立。歐拉公式的推論

定理定理9.4.3

設(shè)G是有n個結(jié)點，e條邊的簡單連通平面圖，則G中至少存在一個結(jié)點v，使得d（v）

5。證明

假設(shè)G中每個結(jié)點v，都有d（v）

6，則由握手定理有6n

d（v）=2e即有e

3n

3n-6，與推論1矛盾。歐拉公式的推廣定理9.4.4（歐拉公式的推廣）設(shè)G為任意的平面圖，G有k個連通分支，n個結(jié)點，e條邊，f個面，則有公式n-e+f=k+1成立。插入和刪去結(jié)點、同胚定義9.4.3

設(shè)e=（u，v）是圖G的一條邊，在G中刪去邊e，增加新的結(jié)點w，使u，v均與w相鄰，則稱在圖G中插入2度結(jié)點w；設(shè)w為G的一個度數(shù)為2的結(jié)點，w與u，v相鄰，刪去w及與w相關(guān)聯(lián)的邊(w，u)，(w，v)，同時增加新邊(u，v

)，則稱在圖G中刪去2度結(jié)點w。定義9.4.4

若兩個圖G1和G2同構(gòu)或通過反復插入或刪除2度結(jié)點后是同構(gòu)的，則稱G1和G2是同胚的。平面圖的充分必要條件定理9.4.5（庫拉托斯基定理）設(shè)G是無向圖，則G是平面圖的充分必要條件是圖G不含和K5或K3，3同胚的子圖。推論

設(shè)G是無向圖，則G是平面圖的充分必要條件是圖G沒有可收縮為K5或K3，的子圖。例題彼得森圖中刪去邊（7,8）和（4,5）的子圖，

和K3，3同胚。所以彼得森圖不是平面圖。9.4.3對偶圖與著色定義9.4.5

設(shè)G是平面圖。在圖G的每個面中指定一個新結(jié)點，對兩個面公共的邊，指定一條新邊與其相交。由這些新結(jié)點和新邊組成的圖稱為G的對偶圖G*。給定平面圖G，用如下的方法構(gòu)造G的對偶圖G*：在G的每一個面fi中任取一個結(jié)點vi*作為G*的結(jié)點；若ek是G的兩個面fi和fj的公共邊，有一條邊ek*=（vi*，vj*）作為G*的邊，且（vi*，vj*）與ek相交；若ek只是G的一個面fi的邊界時，以fi中的結(jié)點vi*為結(jié)點做環(huán)ek*，ek*與ek相交，ek*是G*的一個環(huán)。對偶圖定理

設(shè)n、e、f分別為平面圖G的結(jié)點數(shù)、邊數(shù)和面數(shù)，n*、e*、f*分別為G的對偶圖G*的結(jié)點數(shù)、邊數(shù)和面數(shù)，按照對偶圖的定義有n*=f,e*=e,f*=n。對偶圖平面圖G的一個平面嵌入的對偶圖G*具有如下性質(zhì)：(1)G*是平面圖，而且是平面嵌入。(2)G*是連通的。(3)同構(gòu)平面圖的對偶圖，不一定是同構(gòu)的。(4)G的對偶圖的對偶圖也不一定與G同構(gòu)。同構(gòu)的圖的對偶圖不一定同構(gòu)。G的對偶圖的對偶圖也不一定是與G同構(gòu)。面著