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

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

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

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

(G)=1；完全圖：

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

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

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

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

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

(G)(G)。8/110（2）證實k(G)

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

(G)=0。若G是連通圖，取斷集，記E’關(guān)聯(lián)于V1中點集為V’，關(guān)聯(lián)于中點集為V”，分三種情況分析。9/1101)V1-V’或中最少有一個非空。不失普通性，設(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)頂點，這些頂點組成子集V2，且使得V1-V2

，-V2

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

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

。當(dāng)=n-2時，若頂點v1,v2不相鄰，則對任意第3個頂點v3，G中有邊{v1,v2},{v1,v3}。此時對任意n-3個頂點組成子集V’，都有G-V’連通（在G中刪去任意n-3個頂點依然連通）。所以k(G)n-2=

。由定理8.1，

(G)

，即得k(G)=

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

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

(G)

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

U和w

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

存在V-{v}一個分成U和W劃分，使對任意兩頂點u

U和w

W，頂點v在每一條從u到w路上*/

因為v是G一個割點，G-{v}是不連通，它最少有兩條分支。設(shè)U是由其中一個分支中頂點，W由其余頂點組成，形成V-{v}一個劃分。于是任意兩頂點uU和wW在G-{v}不一樣分支中。所以G中每一條從u到w路中包含頂點v。16/110證實：(3)(2)/*存在V-{v}一個分成U和W劃分，使對任意兩頂點u

U和w

W，頂點v在每一條從u到w路上

對于頂點v，存在兩個不一樣頂點u和w，使頂點v在每一條從u到w路上。*/(2)是(3)一個特殊情況，所以馬上證得。17/110證實：(2)(1)/*對于頂點v，存在兩個不一樣頂點u和w，使頂點v在每一條從u到w路上

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

(G)(G)。所以

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

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

cij。（2）平衡條件：除s和t外每個中間點k，有

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

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

iVfki-jVfjk=0.則得36/110對于任何割(P,)，流值等于從P中頂點到中頂點全部弧上流量之和減去從中頂點到P中頂點全部弧上流量之和。37/110二、最大流最小割定理最大流值小于或等于最小割容量，所以假如找到一個可行流，使得Vf=C(P,)，則f是最大流。Ford,Falkerson，1956，最大流最小割定理38/1101定理8.5（最大流最小割定理）在任一網(wǎng)絡(luò)N中，從s到t最大流值等于分離s和t最小割容量。結(jié)構(gòu)性證實：尋求最大流方法，從s到t關(guān)于f增廣路39/110證實：設(shè)f是一個最大流，用以下方法定義P：令sP。假如iP且fij<cij,則jP；假如iP且fji>0,則jP。任何不在P中頂點在中。40/110證實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,)。41/11042/1102定理8.6可行流f是最大流當(dāng)且僅當(dāng)不存在從s到t關(guān)于f增廣路。43/110三、最大流標(biāo)號方法兩個過程：標(biāo)號過程和增廣過程經(jīng)過標(biāo)號過程找一條增廣路，再由增廣過程確定網(wǎng)絡(luò)流量增量，而且去掉標(biāo)號。44/1101，標(biāo)號過程(1)給定初始流，不妨設(shè)初始流值為0；給發(fā)點標(biāo)號(-,s)，其中s=+

。(2)選擇一個已標(biāo)號頂點p，對于p全部未標(biāo)號相鄰點q，按以下規(guī)則標(biāo)號：a)假如弧(q,p)，q未標(biāo)號，當(dāng)cpq>fpq時，則點q標(biāo)號(p+,

q)，其中

q=min{p,cpq-fpq}；當(dāng)cpq=fpq時，則q不標(biāo)號。b)假如弧(q,p)，q未標(biāo)號，當(dāng)fqp>0時，則點q標(biāo)號(p-,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

V子集I是G獨立集

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

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

0，n-0=|V-C|

0，所以

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

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

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

>086/1103，定理8.12對于n個頂點圖G,且

(G)>0,則

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

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

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

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

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

1(G),所以

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

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

1(G)+1(G)n證實：設(shè)L是G最小邊覆蓋，L=1(G)。令H=G(L)，H有n個頂點。又設(shè)M是H最大匹配，顯然也是G匹配，且ML。以U表示H中關(guān)于M未飽和點集合，且有|U|=n-2|M|。因為M是H最大匹配，所以H中U頂點互不相鄰，即U中頂點關(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是一個匹配，C是點覆蓋，且|M|=|C|，則M是最大匹配，C是最小點覆蓋。92/110證實：若M*是G最大匹配，?是G最小點覆蓋，

1(G)=|M*|，

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

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

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

V1,T=Z

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

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

T，G中每一邊最少有一個頂點在?中，因為不然最少有一邊，其一端點在A中，另一端點在V2-T中，這與

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