復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系-吳永輝-離散數(shù)學(xué)-連通度-網(wǎng)絡(luò)-匹配與Petri網(wǎng)省公開(kāi)課金獎(jiǎng)全國(guó)賽課

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

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

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

(G)=1；完全圖：

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

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

(G)(G)。證實(shí)方法：分而治之。7/110證實(shí)：（1）證實(shí)

(G)(G)。若G沒(méi)有邊，則

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

(G)(G)。8/110（2）證實(shí)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”，分三種情況分析。9/1101)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)組成子集V2，且使得V1-V2

，-V2

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

。證實(shí)方法：分而治之。證實(shí)：當(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)組成子集V’，都有G-V’連通（在G中刪去任意n-3個(gè)頂點(diǎn)依然連通）。所以k(G)n-2=

。由定理8.1，

(G)

，即得k(G)=

。11/1106，定義8.4（k-連通）若圖Gk(G)

k，稱(chēng)G為k-連通。12/1107，定義8.5（k-邊連通）若圖G

(G)

k，稱(chēng)G為k-邊連通。13/110二、割點(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/110證實(shí)方法：(1)(3)(3)(2)(2)(1)/*參考定理7.1證實(shí)*/15/110證實(shí)：(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/110證實(shí)：(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/110證實(shí)：(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)。18/1102，定義8.6（可分圖/不可分圖）有割點(diǎn)非平凡連通圖稱(chēng)為可分圖。沒(méi)有割點(diǎn)非平凡連通圖稱(chēng)為不可分圖。19/1103，定理8.3設(shè)G是頂點(diǎn)數(shù)3連通圖，以下論斷是等價(jià)：(1)G中沒(méi)有割點(diǎn)。(2)G任意兩個(gè)頂點(diǎn)在同一條回路上。(3)G任意一個(gè)頂點(diǎn)和任意一條邊在同一條回路上。(4)G任意兩條邊在同一條回路上。20/110證實(shí)方法：(1)(2)(2)(3)(3)(4)(4)(1)/*參考定理7.1,8.2證實(shí)*/21/110(1)(2)：歸納法證實(shí)設(shè)u,v是G任意兩點(diǎn)，d(u,v)是從u到v距離。對(duì)d(u,v)用歸納法。當(dāng)d(u,v)=1時(shí)，因?yàn)镚中沒(méi)有割點(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}組成一條回路，也即u,v在同一回路上。22/110假設(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沒(méi)有割點(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(chóng)到v一條路，并上邊{w,v}，再并上在C上w到u一條路。23/110(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/110(3)(4)與(2)(3)證實(shí)類(lèi)似。25/110(4)(1)若G中有割點(diǎn)v，則存在頂點(diǎn)u和w，使v在每一條u到w路上，在該路上邊{u,x}與{w,y}（x,y可能為v）必定不在同一回路上，與（4）假設(shè)矛盾。26/1104，雙連通分支1)等價(jià)關(guān)系：對(duì)于E中任意兩邊e1和e2，e1和e2相關(guān)系

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

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

iVfki=jVfjk，對(duì)于s和t有則稱(chēng)f為網(wǎng)絡(luò)N一個(gè)可行流，Vf為流f值，或稱(chēng)f流量。若N中無(wú)可行流f’，使Vf’>Vf，則稱(chēng)f為最大流。29/1103，定義8.9（飽和/未飽和）若fij=cij，則稱(chēng)弧(i,j)是飽和；若fij<cij，則稱(chēng)弧(i,j)是未飽和。30/1104，應(yīng)用網(wǎng)絡(luò)----運(yùn)輸網(wǎng)絡(luò)目標(biāo)----找出它最大流量值31/1105，定義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)全部弧集稱(chēng)為分離s和t割，記為若從網(wǎng)絡(luò)N中刪去任一個(gè)割，則從s到t之間不存在有向路。32/110（1）割容量割容量是它每條弧容量之和，記為，即對(duì)于不一樣割，它容量顯然不一樣。33/110（2）最小割若N中不存在割，使，則稱(chēng)為最小割。34/110定理8.4對(duì)于給定網(wǎng)絡(luò)N=(V,E,C)，設(shè)f是任一個(gè)可行流，是任一個(gè)割，則35/110證實(shí)：依據(jù)流平衡條件可知：對(duì)于發(fā)點(diǎn)sP有

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

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

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

上弧方向與路方向一致，稱(chēng)該弧為向前?。患偃?/p>

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

稱(chēng)為從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,)。41/11042/1102定理8.6可行流f是最大流當(dāng)且僅當(dāng)不存在從s到t關(guān)于f增廣路。43/110三、最大流標(biāo)號(hào)方法兩個(gè)過(guò)程：標(biāo)號(hào)過(guò)程和增廣過(guò)程經(jīng)過(guò)標(biāo)號(hào)過(guò)程找一條增廣路，再由增廣過(guò)程確定網(wǎng)絡(luò)流量增量，而且去掉標(biāo)號(hào)。44/1101，標(biāo)號(hào)過(guò)程(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)為止。45/110假如t點(diǎn)給出標(biāo)號(hào)，說(shuō)明存在一條增廣路，則轉(zhuǎn)向增廣過(guò)程。假如t點(diǎn)未被標(biāo)號(hào)，說(shuō)明不存在增廣路，則算法結(jié)束，所得流為最大流。46/1102，增廣過(guò)程假如在收點(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)過(guò)程。假如在收點(diǎn)t沒(méi)有標(biāo)號(hào)，標(biāo)號(hào)算法結(jié)束，用P表示全部已標(biāo)號(hào)頂點(diǎn)集，表示全部未標(biāo)號(hào)頂點(diǎn)集，于是得到便是最小割，它容量等于最大流值。47/110定理8.7（整數(shù)流定理）任一網(wǎng)絡(luò)中，若全部弧容量是整數(shù)，則必存在整數(shù)最大流。48/1108.3圖與二分圖匹配問(wèn)題1：m家企業(yè)到復(fù)旦大學(xué)來(lái)招聘，每家企業(yè)在復(fù)旦大學(xué)只招一人，有n名復(fù)旦大學(xué)學(xué)生，每個(gè)學(xué)生心目中有自己能夠接收企業(yè)一個(gè)清單。問(wèn)：是否每個(gè)學(xué)生都能得到工作？假如不可能，最多可能有多少位學(xué)生能得到工作？49/110問(wèn)題2：錯(cuò)插信箋問(wèn)題給n位同學(xué)各寫(xiě)好一封信信箋，又寫(xiě)好了給這n位同學(xué)信封，問(wèn)有多少種可能把信箋都插錯(cuò)了信封？50/1108.3圖與二分圖匹配一、匹配概念1定義8.11在圖G=(V,E)中，M是邊集E子集，而且M中沒(méi)有兩條邊相鄰，稱(chēng)M是G一個(gè)匹配。若M中一邊關(guān)聯(lián)于頂點(diǎn)v，則稱(chēng)v為關(guān)于M飽和。M中邊兩個(gè)端點(diǎn)稱(chēng)為在M下配對(duì)。若G中每一個(gè)頂點(diǎn)是關(guān)于M飽和，則稱(chēng)M為G完美匹配。若G中不存在匹配M’，使|M’|>|M|，則稱(chēng)M為G最大匹配。51/1102基本性質(zhì)對(duì)給定圖可能有許多不一樣最大匹配。完美匹配必是最大匹配，反之不一定。52/1103定義8.12設(shè)M是G一個(gè)匹配，若在G中有一條路，它邊在E-M和M中交織地出現(xiàn)，則稱(chēng)該路為關(guān)于M交織路。若關(guān)于M交織路起點(diǎn)和終點(diǎn)不是關(guān)于M飽和，則稱(chēng)該路為關(guān)于M增廣路。例圖8.953/110關(guān)于M增廣路中屬于E-M邊數(shù)比屬于M邊數(shù)多1。若p是關(guān)于M增廣路，則M’=M

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

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

G中不包含關(guān)于M增廣路。55/110證實(shí)證實(shí)：/*M是最大匹配

G中不包含關(guān)于M增廣路，用反證法證實(shí)*/56/110/*M是最大匹配

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

60/1101二分圖G(V1,V2)，有完美匹配必要條件是|V1|=|V2|，但并非充分。61/1101）例8.4殘缺棋盤(pán)問(wèn)題/*|V1|

|V2|*/把一個(gè)88國(guó)際象棋棋盤(pán)兩個(gè)對(duì)角剪去后，得到一個(gè)殘缺棋盤(pán)?，F(xiàn)有31張紙片，每一張紙片大小恰好就是棋盤(pán)上黑白兩個(gè)方格組成長(zhǎng)方形大小，問(wèn)能不能用這31張紙片不重合地完全蓋住這個(gè)殘缺棋盤(pán)？62/110解題分析：二分圖G(V1,V2)：每個(gè)頂點(diǎn)表示棋盤(pá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)中沒(méi)有完美匹配。63/1102）例8.5工作安排問(wèn)題/*|V1|=|V2|*/某單位有6個(gè)工人x1,x2,……,x6，現(xiàn)有6項(xiàng)工作y1,y2,……,y6需要有些人做。64/110解題分析：二分圖G(V1,V2)：xi表示工人，yi表示工作，工人xi能做工作yi，xi與yi之間有一邊。能否找到一個(gè)使y1,y2,……,y6飽和匹配，因?yàn)閨V1|=|V2|，所以飽和匹配一定是完美匹配。65/1102求二分圖最大匹配方法——標(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)，按以下標(biāo)準(zhǔn)擴(kuò)大標(biāo)號(hào)點(diǎn)：（1）假如V1中某頂點(diǎn)xj已標(biāo)號(hào)，而且存在一條以xj為一個(gè)端點(diǎn)不屬于匹配M邊(xj,yk)，yk沒(méi)有標(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沒(méi)有標(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)過(guò)程進(jìn)行不下去。66/110當(dāng)出現(xiàn)前一個(gè)情況時(shí)，得到一條關(guān)于M增廣路，于是能夠得到一個(gè)新匹配M’=M，而且|M’|=|M|+1，抹去全部標(biāo)號(hào)，對(duì)M’重新標(biāo)號(hào)，即將M’仍記為M，按上述標(biāo)準(zhǔn)標(biāo)號(hào)。出現(xiàn)后一個(gè)情況時(shí)，標(biāo)號(hào)停頓。67/110在V1中取定一個(gè)未飽和點(diǎn)xi開(kāi)始進(jìn)行標(biāo)號(hào)，假如標(biāo)號(hào)結(jié)束時(shí)，沒(méi)有找到增廣路，說(shuō)明以xi為一個(gè)端點(diǎn)增廣路不存在。對(duì)于V1每個(gè)未飽和點(diǎn)開(kāi)始進(jìn)行標(biāo)號(hào)，假如都沒(méi)有找到增廣路，則所得到匹配是最大匹配。68/110利用網(wǎng)絡(luò)中最大流標(biāo)號(hào)法來(lái)求二分圖中最大匹配方法。設(shè)G(V1,V2,E)是二分圖，今結(jié)構(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。69/1103定理8.9二分圖G(V1,V2)最大匹配邊數(shù)等于它對(duì)應(yīng)網(wǎng)絡(luò)N(G)中最大流值。70/110證實(shí)：設(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。71/110三、霍爾（Hall）定理霍爾婚姻定理，1935，霍爾72/1101定義8.13（鄰集）圖G任意一個(gè)頂點(diǎn)子集AV，全部與A中頂點(diǎn)相鄰頂點(diǎn)全體，稱(chēng)為A鄰集，記為(A)。73/1102，定義8.14（完全匹配）若M是二分圖G(V1,V2)一個(gè)匹配，使V1中每個(gè)頂點(diǎn)關(guān)于M飽和，則稱(chēng)M是從V1到V2完全匹配。顯然，若|V1|=|V2|，則從V1到V2完全匹配就是G完美匹配。74/1103，定理8.10（霍爾定理）設(shè)二分圖G(V1,V2)，G含有從V1到V2完全匹配對(duì)于任何AV1，有|(A)||A|。75/110證實(shí)：假設(shè)V1中每個(gè)頂點(diǎn)關(guān)于匹配M飽和，并設(shè)A是V1子集，因A每個(gè)頂點(diǎn)在M下和(A)中不一樣頂點(diǎn)配對(duì)，所以有|(A)||A|。76/110

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

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

0(G)。圖8.17(c)79/1103，定理8.11

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

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

0(G)+0(G)=n。82/110/*證實(shí)方法：直接推導(dǎo)*/證實(shí)：設(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。83/110二邊獨(dú)立與覆蓋1，圖G=(V,E)，最大匹配邊數(shù)為G邊獨(dú)立數(shù)，記為

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

1(G)。85/110G有邊覆蓋

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

(G)>0,則

1(G)+1(G)=n.87/110證實(shí)方法：分而治之（1）

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

1(G)+1(G)n88/110證實(shí):

1(G)+1(G)n證實(shí)：設(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組成邊集L，顯然L是一個(gè)邊覆蓋，且|L|=|M|+|F|,于是|M|+|L|=n.又|L|

1(G),所以

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

1(G)+1(G)n.89/110證實(shí):

1(G)+1(G)n證實(shí)：設(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。90/110三、科尼格（K?nig）定理科尼格（K?nig），1931，與霍爾定理相關(guān)91/1101，引理8.1設(shè)M是一個(gè)匹配，C是點(diǎn)覆蓋，且|M|=|C|，則M是最大匹配，C是最小點(diǎn)覆蓋。92/110證實(shí)：若M*是G最大匹配，?是G最小點(diǎn)覆蓋，

1(G)=|M*|，

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

1(G)0(G)|C|。因?yàn)閨M|=|C|，所以|M|=|M*|=1(G)，|C|=|?|=0(G)。93/1102，定理8.13（科尼格定理）在二分圖G(V1,V2)中，有

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

V1,T=Z

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

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

T，G中每一邊最少有一個(gè)頂點(diǎn)在?中，因?yàn)椴蝗蛔钌儆幸贿?，其一端點(diǎn)在A中，另一端點(diǎn)在V2-T中，這與

(A)=T矛盾，所以?是G一個(gè)點(diǎn)覆蓋。顯然，|?|=|M*|。又由