第八章連通度，網(wǎng)絡(luò)，匹配與Petri網(wǎng)8.1連通度與塊8.2網(wǎng)絡(luò)最大流8.3圖與二分圖的匹配8.4獨(dú)立集，覆蓋8.5Petri網(wǎng)18.1連通度與塊一、點(diǎn)連通度與邊連通度衡量一個(gè)圖的連通程度圖8.1點(diǎn)邊21，定義8.1（點(diǎn)割/割點(diǎn)）設(shè)圖G的頂點(diǎn)子集V’，(G-V’)>(G)，稱V’為G的一個(gè)點(diǎn)割。|V’|=1時(shí)，V’中的頂點(diǎn)稱為割點(diǎn)。32，定義8.2（點(diǎn)連通度/連通度）設(shè)有圖G，為產(chǎn)生一個(gè)不連通圖或平凡圖需要從G中刪去的最少頂點(diǎn)數(shù)稱為G的點(diǎn)連通度，記為k(G)，簡(jiǎn)稱為G的連通度。不連通圖或平凡圖：k(G)=0；連通圖，有割點(diǎn)：k(G)=1；完全圖：k(G)=n-1；43，定義8.3（邊連通度）設(shè)有圖G，為產(chǎn)生一個(gè)不連通圖或平凡圖需要從G中刪去的最少邊數(shù)稱為G的邊連通度，記為

(G)。不連通圖或平凡圖：

(G)=0；連通圖，有一橋：

(G)=1；完全圖：

(G)=n-1；54，例8.1/圖8.2（點(diǎn)連通度和邊連通度的用處）

n個(gè)頂點(diǎn)表示n個(gè)站，e條邊表示鐵路或者電話線。為了使n個(gè)站連接得“最好”，必須構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)e條邊的連通圖，使其具有最大的點(diǎn)連通度和邊連通度。65，定理8.1（點(diǎn)連通度，邊連通度與最小頂點(diǎn)度數(shù)的關(guān)系）對(duì)任何一個(gè)圖G，k(G)

(G)(G)。證明方法：分而治之。7證明：（1）證明

(G)(G)。若G沒有邊，則

(G)=(G)=0；否則，存在頂點(diǎn)v，d(v)=(G)。刪除v的所有關(guān)聯(lián)邊，得到的圖必定不連通，所以

(G)(G)。8（2）證明k(G)

(G)。若G是不連通圖或平凡圖，則k(G)=

(G)=0。若G是連通圖，取斷集，記E’關(guān)聯(lián)于V1中的點(diǎn)集為V’，關(guān)聯(lián)于中的點(diǎn)集為V”，分三種情況分析。91)V1-V’或中至少有一個(gè)非空。不失一般性，設(shè)V1-V’

，則G-V’不連通，于是有k(G)|V’||E’|=(G)成立。2)但不失一般性，設(shè)=1，則G-V1為平凡圖。于是有k(G)|V1||E’|=(G)成立。3)V1-V’=-V”=

，但min(|V1|,)>1，則從V1和中各取若干與E’中邊關(guān)聯(lián)的頂點(diǎn)，這些頂點(diǎn)構(gòu)成子集V2，且使得V1-V2

，-V2

，V2中頂點(diǎn)關(guān)聯(lián)E’中全部邊，|V2||E’|，那么G-V2不連通。于是k(G)|V2||E’|=(G)成立。106，例8.2證明：設(shè)G是有n個(gè)頂點(diǎn)的簡(jiǎn)單圖，且n-2，則k(G)=

。證明方法：分而治之。證明：當(dāng)=n-1時(shí)G=Kn，所以k(G)=

。當(dāng)=n-2時(shí)，若頂點(diǎn)v1,v2不相鄰，則對(duì)任意第3個(gè)頂點(diǎn)v3，G中有邊{v1,v2},{v1,v3}。此時(shí)對(duì)任意n-3個(gè)頂點(diǎn)構(gòu)成的子集V’，均有G-V’連通（在G中刪去任意n-3個(gè)頂點(diǎn)依然連通）。所以k(G)n-2=

。由定理8.1，

(G)

，即得k(G)=

。116，定義8.4（k-連通的）若圖G的k(G)

k，稱G為k-連通的。127，定義8.5（k-邊連通的）若圖G的

(G)

k，稱G為k-邊連通的。13二、割點(diǎn)與塊1，定理8.2設(shè)v是連通圖G的一個(gè)頂點(diǎn)，下列論斷是等價(jià)的：(1)v是G的一個(gè)割點(diǎn)。(2)對(duì)于頂點(diǎn)v，存在兩個(gè)不同的頂點(diǎn)u和w，使頂點(diǎn)v在每一條從u到w的路上。(3)存在V-{v}的一個(gè)分成U和W的劃分，使對(duì)任意兩頂點(diǎn)u

U和w

W，頂點(diǎn)v在每一條從u到w的路上。14證明方法：(1)(3)(3)(2)(2)(1)/*參考定理7.1證明*/15證明：(1)(3)/*v是G的一個(gè)割點(diǎn)

存在V-{v}的一個(gè)分成U和W的劃分，使對(duì)任意兩頂點(diǎn)u

U和w

W，頂點(diǎn)v在每一條從u到w的路上*/

因?yàn)関是G的一個(gè)割點(diǎn)，G-{v}是不連通的，它至少有兩條分支。設(shè)U是由其中一個(gè)分支中的頂點(diǎn)，W由其余頂點(diǎn)組成，形成V-{v}的一個(gè)劃分。于是任意兩頂點(diǎn)uU和wW在G-{v}的不同分支中。因此G中每一條從u到w的路中包含頂點(diǎn)v。16證明：(3)(2)/*存在V-{v}的一個(gè)分成U和W的劃分，使對(duì)任意兩頂點(diǎn)u

U和w

W，頂點(diǎn)v在每一條從u到w的路上

對(duì)于頂點(diǎn)v，存在兩個(gè)不同的頂點(diǎn)u和w，使頂點(diǎn)v在每一條從u到w的路上。*/(2)是(3)的一個(gè)特殊情況，所以立即證得。17證明：(2)(1)/*對(duì)于頂點(diǎn)v，存在兩個(gè)不同的頂點(diǎn)u和w，使頂點(diǎn)v在每一條從u到w的路上

v是G的一個(gè)割點(diǎn)。*/若v在每一條從u到w的路上，則在G-{v}中不能有一條從u到w的路，因此G-{v}是不連通的，即v是G的一個(gè)割點(diǎn)。182，定義8.6（可分圖/不可分圖）有割點(diǎn)的非平凡連通圖稱為可分圖。沒有割點(diǎn)的非平凡連通圖稱為不可分圖。193，定理8.3設(shè)G是頂點(diǎn)數(shù)3的連通圖，下列論斷是等價(jià)的：(1)G中沒有割點(diǎn)。(2)G的任意兩個(gè)頂點(diǎn)在同一條回路上。(3)G的任意一個(gè)頂點(diǎn)和任意一條邊在同一條回路上。(4)G的任意兩條邊在同一條回路上。20證明方法：(1)(2)(2)(3)(3)(4)(4)(1)/*參考定理7.1,8.2證明*/21(1)(2)：歸納法證明設(shè)u,v是G的任意兩點(diǎn)，d(u,v)是從u到v的距離。對(duì)d(u,v)用歸納法。當(dāng)d(u,v)=1時(shí)，由于G中沒有割點(diǎn)且n3，因而G是2-連通的，k(G)2。由定理8.1，k(G)

(G)(G)。所以

(G)2。于是可知{u,v}不是橋，因此G-{u,v}仍連通，即從u到v有一條含有其他頂點(diǎn)的路，與{u,v}構(gòu)成一條回路，也即u,v在同一回路上。22假設(shè)d(u,v)=k-1時(shí)結(jié)論成立。當(dāng)d(u,v)=k時(shí)，令w是u到v長(zhǎng)度k的路上v的相鄰點(diǎn)。因d(u,w)=k-1，按歸納假設(shè)G中有一條包含u,w的回路C。又因G沒有割點(diǎn)，所以G-{w}是連通的，且含有一條u到v的路p。設(shè)x是p上與回路C相交的最后一個(gè)頂點(diǎn)，x也可能就是u。不失一般性，假設(shè)xC，于是G中有一條含有u和v的回路：在C上u到x的一條路，并上p上的x到v的一條路，并上邊{w,v}，再并上在C上w到u的一條路。23(2)(3)設(shè)u是任意一個(gè)頂點(diǎn)，{v,w}是任一邊，由（2）可知，存在包含u和v的回路C，若wC，則即得證；若wC，由（2），u,w在同一回路上，那么v一定不是割點(diǎn)。所以必存在不含頂點(diǎn)v的從w到u的路p。設(shè)x是p與C相交的第一個(gè)頂點(diǎn)，則w到x沿C經(jīng)u到v，最后回到w的回路即所要求的回路。24(3)(4)與(2)(3)的證明類似。25(4)(1)若G中有割點(diǎn)v，則存在頂點(diǎn)u和w，使v在每一條u到w的路上，在該路上邊{u,x}與{w,y}（x,y可能為v）必定不在同一回路上，與（4）假設(shè)矛盾。264，雙連通分支1)等價(jià)關(guān)系：對(duì)于E中任意兩邊e1和e2，e1和e2有關(guān)系

e1=e2或者e1和e2在同一回路上。2)等價(jià)類E1,E2,…,Ek導(dǎo)出的子圖G1,G2,…,Gk，每個(gè)子圖稱為G的一個(gè)塊，或稱雙連通分支。278.2網(wǎng)絡(luò)最大流一、基本概念1，定義8.7（網(wǎng)絡(luò)）設(shè)連通無自環(huán)的帶權(quán)有向圖中有兩個(gè)不同頂點(diǎn)s和t，且在弧集E上定義一個(gè)非負(fù)整數(shù)值函數(shù)C={cij}，稱該有向圖為網(wǎng)絡(luò)，記為N(V,E,C)。稱為s發(fā)點(diǎn)，t為收點(diǎn)，除s和t以外其他頂點(diǎn)稱為中間點(diǎn)。C稱為容量函數(shù)，弧(i,j)上的容量為cij。282，定義8.8（流量）在網(wǎng)絡(luò)N(V,E,C)的弧集E上定義一個(gè)非負(fù)整數(shù)值函數(shù)f={fij}，稱f為網(wǎng)絡(luò)N上的流，fij稱為弧(i,j)上的流量。若無弧(i,j)，則fij定義為0。設(shè)流f滿足下列條件：（1）容量限制條件：對(duì)每一條弧(i,j)，有fij

cij。（2）平衡條件：除s和t外的每個(gè)中間點(diǎn)k，有

iVfki=jVfjk，對(duì)于s和t有則稱f為網(wǎng)絡(luò)N的一個(gè)可行流，Vf為流f的值，或稱f的流量。若N中無可行流f’，使Vf’>Vf，則稱f為最大流。293，定義8.9（飽和的/未飽和的）若fij=cij，則稱弧(i,j)是飽和的；若fij<cij，則稱弧(i,j)是未飽和的。304，應(yīng)用網(wǎng)絡(luò)----運(yùn)輸網(wǎng)絡(luò)目的----找出它的最大流量的值315，定義8.10（割）設(shè)N(V,E,C)是有一個(gè)發(fā)點(diǎn)s和一個(gè)收點(diǎn)t的網(wǎng)絡(luò)。若V劃分為P和，使則從P中的點(diǎn)到中的點(diǎn)的所有弧集稱為分離s和t的割，記為若從網(wǎng)絡(luò)N中刪去任一個(gè)割，則從s到t之間不存在有向路。32（1）割的容量割的容量是它的每條弧的容量之和，記為，即對(duì)于不同的割，它的容量顯然不同。33（2）最小割若N中不存在割，使，則稱為最小割。34定理8.4對(duì)于給定的網(wǎng)絡(luò)N=(V,E,C)，設(shè)f是任一個(gè)可行流，是任一個(gè)割，則35證明：根據(jù)流的平衡條件可知：對(duì)于發(fā)點(diǎn)sP有

iVfsi-jVfjs=Vf.對(duì)于P中不是發(fā)點(diǎn)s的中間點(diǎn)k有

iVfki-jVfjk=0.則得36對(duì)于任何割(P,)，流的值等于從P中的頂點(diǎn)到中的頂點(diǎn)的所有弧上流量之和減去從中的頂點(diǎn)到P中的頂點(diǎn)的所有弧上流量之和。37二、最大流最小割定理最大流的值小于或等于最小割的容量，所以如果找到一個(gè)可行流，使得Vf=C(P,)，則f是最大流。Ford,Falkerson，1956，最大流最小割定理381定理8.5（最大流最小割定理）在任一網(wǎng)絡(luò)N中，從s到t的最大流的值等于分離s和t的最小割的容量。構(gòu)造性證明：尋求最大流的方法，從s到t的關(guān)于f的增廣路39證明：設(shè)f是一個(gè)最大流，用以下方法定義P：令sP。如果iP且fij<cij,則jP；如果iP且fji>0,則jP。任何不在P中的頂點(diǎn)在中。40證明tP。/*反證*/假設(shè)tP，則得到一條從s到t的路

。定義路的方向是從s到t，如果

上弧的方向與路的方向一致，稱該弧為向前??；如果

上弧的方向與路的方向相反，稱該弧為向后弧。由的定義可知，在向前弧(i,j)上必有fij<cij，在向后弧(j,i)上必有fji>0。路

稱為從s到t的增廣路。設(shè)

1是路

上所有向前弧上ci,i+1-fi,i+1的最小值，

2是所有向后弧上fj+1,j的最小值，

=min(

1,

2),>0，在向前弧上可增加流量

，在向后弧上可減少流量

，使得流f修改后得到的流f’仍滿足流的條件，并且流的值增加

，這與f是最大流矛盾。因此tP，于是得到分離s和t的割(P,)。412定理8.6可行流f是最大流當(dāng)且僅當(dāng)不存在從s到t的關(guān)于f的增廣路。42三、最大流的標(biāo)號(hào)方法兩個(gè)過程：標(biāo)號(hào)過程和增廣過程通過標(biāo)號(hào)過程找一條增廣路，再由增廣過程確定網(wǎng)絡(luò)流量的增量，并且去掉標(biāo)號(hào)。431，標(biāo)號(hào)過程(1)給定初始流，不妨設(shè)初始流的值為0；給發(fā)點(diǎn)標(biāo)號(hào)(-,s)，其中s=+

。(2)選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn)p，對(duì)于p的所有未標(biāo)號(hào)的相鄰點(diǎn)q，按下列規(guī)則標(biāo)號(hào)：a)如果弧(q,p)，q未標(biāo)號(hào)，當(dāng)cpq>fpq時(shí)，則點(diǎn)q標(biāo)號(hào)(p+,

q)，其中

q=min{p,cpq-fpq}；當(dāng)cpq=fpq時(shí)，則q不標(biāo)號(hào)。b)如果弧(q,p)，q未標(biāo)號(hào)，當(dāng)fqp>0時(shí)，則點(diǎn)q標(biāo)號(hào)(p-,

q)，其中p=min{p,fqp}；當(dāng)fqp=0時(shí)，則q點(diǎn)不標(biāo)號(hào)。(3)重復(fù)第(2)步直到收點(diǎn)t被標(biāo)號(hào)為止，或不再有頂點(diǎn)可以標(biāo)號(hào)為止。44如果t點(diǎn)給出標(biāo)號(hào)，說明存在一條增廣路，則轉(zhuǎn)向增廣過程。如果t點(diǎn)未被標(biāo)號(hào)，說明不存在增廣路，則算法結(jié)束，所得的流為最大流。452，增廣過程如果在收點(diǎn)t已標(biāo)號(hào)(y+,t)，已知其中t=min{y,cyt-fyt}，則存在一條從s到t的增廣路

。(1)修改流f，使得沿增廣路

在向前弧上流量增加t，在向后弧上流量減少t，于是得到新的流f’，且有Vf’=Vf+t。然后去掉頂點(diǎn)上標(biāo)號(hào)。(2)對(duì)流f’重新進(jìn)行標(biāo)號(hào)過程。如果在收點(diǎn)t沒有標(biāo)號(hào)，標(biāo)號(hào)算法結(jié)束，用P表示所有已標(biāo)號(hào)的頂點(diǎn)集，表示所有未標(biāo)號(hào)的頂點(diǎn)集，于是得到的便是最小割，它的容量等于最大流的值。46定理8.7（整數(shù)流定理）任一網(wǎng)絡(luò)中，若所有弧的容量是整數(shù)，則必存在整數(shù)最大流。478.3圖與二分圖的匹配問題1：m家公司到復(fù)旦大學(xué)來招聘，每家公司在復(fù)旦大學(xué)只招一人，有n名復(fù)旦大學(xué)學(xué)生，每個(gè)學(xué)生的心目中有自己可以接受的公司的一個(gè)清單。問：是否每個(gè)學(xué)生都能得到工作？如果不可能，最多可能有多少位學(xué)生能得到工作？48問題2：錯(cuò)插信箋問題給n位同學(xué)各寫好一封信的信箋，又寫好了給這n位同學(xué)的信封，問有多少種可能把信箋都插錯(cuò)了信封？498.3圖與二分圖的匹配一、匹配的概念1定義8.11在圖G=(V,E)中，M是邊集E的子集，并且M中沒有兩條邊相鄰，稱M是G的一個(gè)匹配。若M中的一邊關(guān)聯(lián)于頂點(diǎn)v，則稱v為關(guān)于M飽和的。M中的邊的兩個(gè)端點(diǎn)稱為在M下配對(duì)。若G中每一個(gè)頂點(diǎn)是關(guān)于M飽和的，則稱M為G的完美匹配。若G中不存在匹配M’，使|M’|>|M|，則稱M為G的最大匹配。502基本性質(zhì)對(duì)給定的圖可能有許多不同的最大匹配。完美匹配必是最大匹配，反之不一定。513定義8.12設(shè)M是G的一個(gè)匹配，若在G中有一條路，它的邊在E-M和M中交錯(cuò)地出現(xiàn)，則稱該路為關(guān)于M的交錯(cuò)路。若關(guān)于M的交錯(cuò)路的起點(diǎn)和終點(diǎn)不是關(guān)于M飽和的，則稱該路為關(guān)于M的增廣路。例圖8.952關(guān)于M的增廣路中屬于E-M的邊數(shù)比屬于M的邊數(shù)多1。若p是關(guān)于M的增廣路，則M’=M

p是一個(gè)匹配，并且|M’|=|M|+1。其中M

p=(Mp)-(Mp)稱為邊集與邊集的環(huán)和。534定理8.8（匹配的基本定理）在圖G中，M是最大匹配

G中不包含關(guān)于M的增廣路。54證明證明：/*M是最大匹配

G中不包含關(guān)于M的增廣路，用反證法證明*/55/*M是最大匹配

G中不包含關(guān)于M的增廣路，用反證法證明*/假設(shè)M不是最大匹配，則存在匹配M’，使|M’|>|M|。設(shè)由MM’導(dǎo)出的圖G(MM’)記為H，它的每個(gè)分支或者是交錯(cuò)路，或者是交錯(cuò)回路。因?yàn)镸和M’都是圖G的匹配，H中每個(gè)頂點(diǎn)度數(shù)至多為2，于是每個(gè)分支中的每個(gè)頂點(diǎn)度數(shù)至多是2，所以每個(gè)分支或者是回路，或者是路，并且其上的邊交錯(cuò)地屬于M和M’。由于|M’|>|M|，因而H中必有一條路p，它的起點(diǎn)和終點(diǎn)都是關(guān)于M未飽和的，也一定是G中關(guān)于M未飽和的頂點(diǎn)。因此在G中存在關(guān)于M的增廣路，這與假設(shè)矛盾。56定理8.8（匹配的基本定理）用于判定一個(gè)匹配不是最大匹配。575完美匹配與最大匹配最大匹配，并且所有頂點(diǎn)關(guān)于M飽和，則為完美匹配。58二、二分圖中的匹配問題：求二分圖中最大匹配和完美匹配。

591二分圖G(V1,V2)，有完美匹配的必要條件是|V1|=|V2|，但并非充分。601）例8.4殘缺棋盤問題/*|V1|

|V2|*/把一個(gè)88國(guó)際象棋棋盤的兩個(gè)對(duì)角剪去后，得到一個(gè)殘缺棋盤?，F(xiàn)有31張紙片，每一張紙片的大小恰好就是棋盤上黑白兩個(gè)方格組成的長(zhǎng)方形的大小，問能不能用這31張紙片不重疊地完全蓋住這個(gè)殘缺的棋盤？61解題分析：二分圖G(V1,V2)：每個(gè)頂點(diǎn)表示棋盤中的一個(gè)方格，有62格。G中每?jī)蓚€(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)對(duì)應(yīng)的黑白格相鄰，得二分圖G(V1,V2)。|V1|=30，|V2|=32，|V1|

|V2|，所以G(V1,V2)中沒有完美匹配。622）例8.5工作安排問題/*|V1|=|V2|*/某單位有6個(gè)工人x1,x2,……,x6，現(xiàn)有6項(xiàng)工作y1,y2,……,y6需要有人做。63解題分析：二分圖G(V1,V2)：xi表示工人，yi表示工作，工人xi能做工作yi，xi與yi之間有一邊。能否找到一個(gè)使y1,y2,……,y6飽和的匹配，因?yàn)閨V1|=|V2|，所以飽和匹配一定是完美匹配。642求二分圖最大匹配的方法——標(biāo)號(hào)法設(shè)二分圖G(V1,V2)，V1={x1,x2,…,xn}，V2={y1,y2,…,ym}，給定一個(gè)匹配M（可取M=

）。V1中取一個(gè)未飽和的點(diǎn)xi標(biāo)號(hào)(+,0)，按下列原則擴(kuò)大標(biāo)號(hào)點(diǎn)：（1）如果V1中某頂點(diǎn)xj已標(biāo)號(hào)，并且存在一條以xj為一個(gè)端點(diǎn)的不屬于匹配M的邊(xj,yk)，yk沒有標(biāo)號(hào)，則yk標(biāo)號(hào)(+,xj)。（2）如果V2中某頂點(diǎn)yl已標(biāo)號(hào)，并且存在一條以yl為一個(gè)端點(diǎn)的屬于匹配M的邊(yl,xr)，xr沒有標(biāo)號(hào)，則xr標(biāo)號(hào)(+,yl)。重復(fù)（1）和（2）?；蛘呤筕2中的某一個(gè)未飽和點(diǎn)得到標(biāo)號(hào)，或者V2中未飽和點(diǎn)均未能標(biāo)號(hào)，而使標(biāo)號(hào)過程進(jìn)行不下去。65當(dāng)出現(xiàn)前一種情況時(shí)，得到一條關(guān)于M的增廣路，于是可以得到一個(gè)新的匹配M’=M，并且|M’|=|M|+1，抹去所有的標(biāo)號(hào)，對(duì)M’重新標(biāo)號(hào)，即將M’仍記為M，按上述原則標(biāo)號(hào)。出現(xiàn)后一種情況時(shí)，標(biāo)號(hào)停止。66在V1中取定的一個(gè)未飽和點(diǎn)xi開始進(jìn)行標(biāo)號(hào)，如果標(biāo)號(hào)結(jié)束時(shí)，沒有找到增廣路，說明以xi為一個(gè)端點(diǎn)的增廣路不存在。對(duì)于V1的每個(gè)未飽和點(diǎn)開始進(jìn)行標(biāo)號(hào)，如果都沒有找到增廣路，則所得到的匹配是最大匹配。67利用網(wǎng)絡(luò)中最大流的標(biāo)號(hào)法來求二分圖中最大匹配的方法。設(shè)G(V1,V2,E)是二分圖，今構(gòu)造一個(gè)網(wǎng)絡(luò)N(V’,E’,C)又記為N(G)，它是一個(gè)帶權(quán)有向圖，其中V’=V1UV2U{s,t},E’={(s,x)|xV1}U{(y,t)|yV2}U{(x,y)|xV1,yV2,(x,y)E}。對(duì)任意xV1,yV2,令csx=cyt=1,對(duì)任意弧(x,y),xV1,yV2,令cxy=1，這個(gè)網(wǎng)絡(luò)的發(fā)點(diǎn)是s，收點(diǎn)是t。683定理8.9二分圖G(V1,V2)的最大匹配的邊數(shù)等于它對(duì)應(yīng)的網(wǎng)絡(luò)N(G)中最大流的值。69證明：設(shè)M是二分圖G(V1,V2)的最大匹配。在對(duì)應(yīng)網(wǎng)絡(luò)N(G)中，對(duì)于M的每條弧(x,y)，在N(G)中存在一條從s到t的有向路(s,x,y,t)，其上每條弧的流量為1，顯然這些有向路是點(diǎn)不相交的。設(shè)N(G)中最大流的值為Vf，則必有Vf|M|。由定理8.7，若網(wǎng)絡(luò)中所有弧的容量為整數(shù)，則存在整數(shù)最大流。不妨設(shè)f為整數(shù)流函數(shù)。由標(biāo)號(hào)法可知，從s到t的有向路形如(s,x,y,t)，其中xV1，yV2。這樣的有向路上每條弧流量為1，所以不存在有非零流量的弧(x,y’)或(x’,y)。因?yàn)閏sx=1，cyt=1，并且從s到V1中每個(gè)頂點(diǎn)x只有一條弧，從V2中每個(gè)頂點(diǎn)y到t也只有一條弧。于是弧集{(x,y)|fxy=1}是G的一個(gè)匹配M’。因此最大匹配M使|M||M’|=Vf，從而得到|V|=Vf。70三、霍爾（Hall）定理霍爾婚姻定理，1935，霍爾711定義8.13（鄰集）圖G的任意一個(gè)頂點(diǎn)子集AV，所有與A中頂點(diǎn)相鄰的頂點(diǎn)全體，稱為A的鄰集，記為(A)。722，定義8.14（完全匹配）若M是二分圖G(V1,V2)的一個(gè)匹配，使V1中每個(gè)頂點(diǎn)關(guān)于M飽和，則稱M是從V1到V2的完全匹配。顯然，若|V1|=|V2|，則從V1到V2的完全匹配就是G的完美匹配。733，定理8.10（霍爾定理）設(shè)二分圖G(V1,V2)，G含有從V1到V2的完全匹配對(duì)于任何AV1，有|(A)||A|。74證明：假設(shè)V1中每個(gè)頂點(diǎn)關(guān)于匹配M飽和，并設(shè)A是V1的子集，因A的每個(gè)頂點(diǎn)在M下和(A)中不同頂點(diǎn)配對(duì)，所以有|(A)||A|。75

768.4獨(dú)立集,覆蓋一、點(diǎn)的獨(dú)立集與覆蓋1，定義8.15（獨(dú)立集）設(shè)無自環(huán)圖G=(V,E)，若V的一個(gè)子集I中任意兩個(gè)頂點(diǎn)在G中都不相鄰，則稱I是G的一個(gè)獨(dú)立集。若G中不含有滿足|I’|>|I|的獨(dú)立集I’，則稱I為G的最大獨(dú)立集。它的頂點(diǎn)數(shù)稱為G的獨(dú)立數(shù)，記為

0(G)。圖8.17(a)(b)772，定義8.16（點(diǎn)覆蓋）設(shè)無自環(huán)圖G=(V,E)，若V的一個(gè)子集C使得G的每一條邊至少有一個(gè)端點(diǎn)在C中，則稱C是G的一個(gè)點(diǎn)覆蓋。若G中不含有滿足|C’|<|C|的點(diǎn)覆蓋C’，則稱C是G的最小點(diǎn)覆蓋。它的頂點(diǎn)數(shù)稱為G的點(diǎn)覆蓋數(shù)，記為

0(G)。圖8.17(c)783，定理8.11

V的子集I是G的獨(dú)立集

V-I是G的點(diǎn)覆蓋.79/*證明方法：直接推導(dǎo)*/證明：由獨(dú)立集的定義，I是G的獨(dú)立集當(dāng)且僅當(dāng)G中每一條邊至少有一個(gè)端點(diǎn)在V-I中，即，V-I是G的點(diǎn)覆蓋。804，推論8.1對(duì)于n個(gè)頂點(diǎn)的圖G，有

0(G)+0(G)=n。81/*證明方法：直接推導(dǎo)*/證明：設(shè)I是G的最大獨(dú)立集，C是G的最小點(diǎn)覆蓋，則V-C是G的獨(dú)立集，V-I是G的點(diǎn)覆蓋，所以n-0=|V-I|

0，n-0=|V-C|

0，因此

0+0=n。82二邊的獨(dú)立與覆蓋1，圖G=(V,E)，最大匹配的邊數(shù)為G的邊獨(dú)立數(shù)，記為

1(G)。832，定義8.17（邊覆蓋）若E的一個(gè)子集L使得G的每一個(gè)頂點(diǎn)至少與L中一條邊關(guān)聯(lián)，稱L是G的一個(gè)邊覆蓋。若G中不含有滿足|L’|<|L|的點(diǎn)覆蓋L’，則稱L是G的最小邊覆蓋。它的邊數(shù)稱為G的邊覆蓋數(shù)，記為

1(G)。84G有邊覆蓋

>0853，定理8.12對(duì)于n個(gè)頂點(diǎn)圖G,且

(G)>0,則

1(G)+1(G)=n.86證明方法：分而治之（1）

1(G)+1(G)n（2）

1(G)+1(G)n87證明:

1(G)+1(G)n證明：設(shè)M是G的最大匹配，|M|=

1(G)。設(shè)F是關(guān)于M的未飽和點(diǎn)集合，有|F|=n-2|M|。又>0，對(duì)于F中每個(gè)頂點(diǎn)v，取一條與v關(guān)聯(lián)的邊，這些邊與M構(gòu)成邊集L，顯然L是一個(gè)邊覆蓋，且|L|=|M|+|F|,于是|M|+|L|=n.又|L|

1(G),所以

1(G)n-1(G),即

1(G)+1(G)n.88證明:

1(G)+1(G)n證明：設(shè)L是G的最小邊覆蓋，L=1(G)。令H=G(L)，H有n個(gè)頂點(diǎn)。又設(shè)M是H的最大匹配，顯然也是G的匹配，且ML。以U表示H中關(guān)于M的未飽和點(diǎn)集合，且有|U|=n-2|M|。因?yàn)镸是H的最大匹配，所以H中U的頂點(diǎn)互不相鄰，即U中頂點(diǎn)關(guān)聯(lián)的邊在L-M中。因此|L|-|M|=|L-M||U|=n-2|M|。于是

1(G)+1(G)n。89三、科尼格（K?nig）定理科尼格（K?nig），1931，與霍爾定理相關(guān)901，引理8.1設(shè)M是一個(gè)匹配，C是點(diǎn)覆蓋，且|M|=|C|，則M是最大匹配，C是最小點(diǎn)覆蓋。91證明：若M*是G的最大匹配，?是G的最小點(diǎn)覆蓋，

1(G)=|M*|，

0(G)=|?|，則|M|

1(G)0(G)|C|。由于|M|=|C|，所以|M|=|M*|=1(G)，|C|=|?|=0(G)。922，定理8.13（科尼格定理）在二分圖G(V1,V2)中，有

1(G)=0(G)。/*邊獨(dú)立數(shù)=點(diǎn)覆蓋數(shù)*/93證明：設(shè)M*是G的最大匹配，U是V1中關(guān)于M*未飽和點(diǎn)集合。又設(shè)Z表示與U中每一個(gè)頂點(diǎn)有關(guān)于M*交錯(cuò)路相連的頂點(diǎn)集合，因?yàn)镸*是最大匹配，所以G中不包含M*的增廣路，由定理8.8，U是Z中僅有的未被M*飽和的頂點(diǎn)集合。令A(yù)=Z

V1,T=Z

V2，由定理8.10的證明，可知T中頂點(diǎn)關(guān)于M*是飽和的，并且

(A)=T。定義?=(V-A)

T，G中每一邊至少有一個(gè)頂點(diǎn)在?中，因?yàn)榉駝t至少有一邊，其一端點(diǎn)在A中，另一端點(diǎn)在V2-T中，這與