支配集、覆蓋集、獨立集與匹配講義

第7章支配集、覆蓋集、獨立集與匹配本講內(nèi)容會涉及以下容易相互混淆的內(nèi)容：點支配集,極小點支配集,最小點支配集,點支配數(shù)

0(G);支配的概念；點獨立集,極大點獨立集,最大點獨立集,點獨立數(shù)

0(G);點覆蓋集,極小點覆蓋集,最小點覆蓋集,點覆蓋數(shù)

0(G);覆蓋的概念；邊覆蓋集,極小邊覆蓋集,最小邊覆蓋集,邊覆蓋數(shù)

1(G);邊獨立集(匹配),極大邊獨立集(極大匹配),最大邊獨立集(最大匹配),邊獨立數(shù)(或匹配數(shù))

1(G);以上幾個量存在以下關(guān)系：

0＋

0

＝n，即：點覆蓋數(shù)+點獨立數(shù)=n

1＋

1

＝n，即：邊覆蓋數(shù)+邊獨立數(shù)=n對二部圖，還有以下關(guān)系式：二部圖的最小點覆蓋數(shù)

0＝等于最大匹配數(shù)

1。ZOJ1364二部圖的最大點獨立數(shù)

0＝頂點個數(shù)n－最大匹配數(shù)

1。(前提是該二部圖沒有孤立頂點，如果有孤立頂點，對這些孤立頂點要單獨考慮)ZOJ11377.1點支配集、點覆蓋集、點獨立集

(都是頂點的集合)定義7.1

支配與支配集設(shè)圖G=<V,E>,V*

V,若對于

vi

V-V*,

vj

V*,使得:(vi,vj)

E,則稱vj支配vi,并稱V*為G的一個支配集;若支配集V*的任何真子集都不是支配集,則稱V*是極小支配集;頂點數(shù)最少的支配集稱為最小支配集;最小支配集中的頂點數(shù)稱為支配數(shù),記作

0(G)或簡記為

0。圖(a)中，V*={v1,v5}就是一個支配集。因為V-V*={v2,v3,v4,v6,v7}中的頂點都是V*中頂點的鄰接頂點。通俗地講，所謂支配集，就是V中的頂點要么是V*集合中的元素，要么與V*中的一個頂點相鄰。在圖(a)中,{v1,v5},{v3,v5}和{v2,v4,v7}都是極小支配集,{v1,v5},{v4,v5}和{v3,v6}都是最小支配集,

0=2。圖(b)為7階星形圖,{v0},{v1,v2,...,v6}為極小支配集,{v0}為最小支配集,

0=1。圖(c)為輪圖W6,{v0},{v1,v3},{v1,v4}等都是極小支配集,顯然,

0＝1。支配集的性質(zhì)若G中無孤立頂點(度數(shù)為0的頂點)，則存在一個支配集V*，使得G中除V*外的所有頂點也組成一個支配集(即V-V*也是一個支配集)。若G中無孤立頂點(度數(shù)為0的頂點)，V1*為極小支配集，則G中除V1*外的所有頂點也組成一個支配集(即V–V1*也是一個支配集)。(證明略)思考：在圖(a)中，取V*＝{v3,v5,v6,v7}，V*是支配集，但V-V*是否是支配集？極小支配集的求解參見吳文虎編著的《信息學奧林匹克競賽指導－圖論的算法與程序設(shè)計(PASCAL版)》P54有電子版

設(shè)圖G=<V,E>,V*

V,若V*中任何兩個頂點均不相鄰,則稱V*為G的點獨立集,或稱獨立集;若在V*中加入任何頂點都不再是獨立集,則稱V*為極大點獨立集;頂點數(shù)最多的點獨立集稱為最大點獨立集;最大點獨立集的頂點數(shù)稱為點獨立數(shù),記作

0(G),簡記為

0。定義7.2

點獨立集圖(a)中，V*={v1,v5}就是一個點獨立集，因為v1和v5是不相鄰的。圖(a)中,{v1,v5},{v3,v6},{v2,v4,v7}等都是極大點獨立集,其{v2,v4,v7}等為最大點獨立集,

0=3;圖(b)中,{v0},{v1,v2,…,v6}都是極大點獨立集,其{v1,v2,…,v6}是最大點獨立集,

0=6;圖(c)中,{v1,v3},{v1,v4}是極大點獨立集,也都是最大點獨立集,

0＝2。

設(shè)G=<V,E>,V*

V,若對于

e

E,

v

V*,使得:v與e相關(guān)聯(lián),則稱v覆蓋e,并稱V*為G的點覆蓋集或簡稱點覆蓋;若點覆蓋V*的任何真子集都不是點覆蓋,則稱V*是極小點覆蓋;頂點個數(shù)最少的點覆蓋稱為最小的點覆蓋;最小點覆蓋的頂點數(shù)稱為點覆蓋數(shù),記作

0(G),簡記為

0。定義7.3

覆蓋與點覆蓋集圖(a)中，V*={v1,v3,v5,v7}就是一個點覆蓋集。通俗地講，所謂點覆蓋集V*，就是G中所有的邊至少有一個頂點屬于V*(頂點覆蓋邊)。圖(a)中,{v2,v3,v4,v6,v7},{v1,v3,v5,v7}等都是極小點覆蓋,{v1,v3,v5,v7}是最小點覆蓋,

0=4;圖(b)中,{v0},{v1,v2,…,v6}都是極小點覆蓋,{v0}是最小點覆蓋,

0=1;圖(c)中,{v0,v1,v3,v4},{v0,v1,v3,v5}都是極小點覆蓋,也都是最小的點覆蓋,

0=4。點支配集、點獨立集、點覆蓋集之間的聯(lián)系定理7.1：設(shè)G=<V,E>中無孤立點，則G的極大點獨立集都是G的極小支配集。逆命題不成立(即極小支配集未必是極大獨立集)。一個獨立集是極大獨立集，當且僅當它是一個支配集。定理7.2：設(shè)G=<V,E>中無孤立點,V*(V*

V)為G的點覆蓋,當且僅當V-V*為G的點獨立集。推論：設(shè)G是n階無孤立點的圖，則V*是G的極小(最小)點覆蓋，當且僅當V-V*是G的極大(最大)點獨立集，從而有

0+

0=n(頂點個數(shù))。

設(shè)G=<V,E>中無孤立點,則G的極大點獨立集都是G的極小支配集。假設(shè):V*是G中的任意一個極大獨立集。

v

V-V*,一定有:

v’

V*,使得:(v,v’)

E。假設(shè):u

V-V*不與V*中任何頂點相鄰,則V*∪{u}就是一個更大的獨立集,這與V*是極大獨立集相矛盾。所以,V*是G的支配集。由“V*是點獨立集”可知:

V1*

V*,V*-V1*中的頂點都不受V1*中的頂點支配,即:V1*不是支配集。所以,V*是極小支配集。證：上面定理的逆命題是不成立的。在右圖中,{v3,v5}是極小支配集,但它不是獨立集,更不是極大獨立集。定理7.1

設(shè)G=<V,E>中無孤立點,V*(V*

V)為G的點覆蓋,當且僅當V-V*為G的點獨立集。證：1)必要性假設(shè):存在vi,vj

V-V*,且(vi,vj)

E。由于頂點vi和vj都不在V*中,這顯然與“V*是點覆蓋”相矛盾。所以,V-V*為點獨立集。2)充分性假設(shè):V-V*是點獨立集。因此,任意一條邊的兩個端點至少有一個在V*中。由定義可知:V*是G的點覆蓋。推論設(shè)G是n階無孤立點的圖,則V*是G的極小(最小)點覆蓋,當且僅當V-V*是G的極大(最大)點獨立集,從而有

0+

0=n(頂點個數(shù))。定理7.2極大點獨立集與極小點覆蓋集的求解參見吳文虎編著的《信息學奧林匹克競賽指導－圖論的算法與程序設(shè)計(PASCAL版)》P587.2邊覆蓋集與匹配

(都是邊的集合)定義7.4

覆蓋與邊覆蓋集

設(shè)圖G=<V,E>,E*

E,若

v

V,

e

E*,使得:v與e相關(guān)聯(lián),則稱e覆蓋v,并稱E*為邊覆蓋集,或簡稱邊覆蓋;若邊覆蓋E*的任何真子集都不是邊覆蓋,則稱E*是極小邊覆蓋;邊數(shù)最少的邊覆蓋集稱為最小的邊覆蓋;最小的邊覆蓋所含的邊數(shù)稱為邊覆蓋數(shù),記作

1(G)或簡記為

1。圖(a)中，E*={e1,e4,e7}就是一個邊覆蓋集。通俗地講，所謂邊覆蓋集E*，就是G中所有的頂點都是E*中邊的頂點(邊覆蓋頂點)。圖(a)中,{e1,e4,e7}和{e2,e5,e6,e7}都是極小邊覆蓋,{e1,e4,e7}是最小邊覆蓋,

1=3。圖(b)中,{e1,e3,e6}和{e2,e4,e8}都是極小邊覆蓋,也都是最小邊覆蓋,

1=3。

設(shè)G=<V,E>,若E*(E*

E)中任何兩條邊均不相鄰,則稱E*為G中邊獨立集,也稱E*為G中的匹配(Matching);若在E*中加入任意一條邊所得集合都不是匹配,則稱E*為極大匹配;邊數(shù)最多的匹配稱為最大匹配;最大匹配的邊數(shù)稱為邊獨立數(shù)或匹配數(shù),記作

1(G),簡記為

1。定義7.5

匹配圖(a)中，E*={e1,e4,e7}就是一個匹配。所謂任何兩條邊均不相鄰，通俗地講，就是任何兩條邊都沒有公共頂點。圖(a)中,{e2,e6},{e3,e5},{e1,e4,e7}都是極大匹配,{e1,e4,e7}是最大匹配,

1=3。圖(b)中,{e1,e3},{e2,e4},{e4,e7}都是極大匹配,也都是最大匹配,

1=2。例：飛行員搭配問題1－最大匹配問題飛行大隊有若干個來自各地的飛行員，專門駕駛一種型號的飛機，這種飛機每架有兩個飛行員。由于種種原因，例如互相配合的問題，有些飛行員不能在同一架飛機上飛行，問如何搭配飛行員，才能使出航的飛機最多。為簡單起見，設(shè)有10個飛行員，圖(a)中的V1,V2,…V10就代表這10個飛行員。如果兩個人可以同機飛行，就在他們之間連一條線，否則就不連。V9V3V1V2V4V5V7V6V8V10(a)圖(a)中的3條藍色的粗線代表一種搭配方案。由于一個飛行員不能同時派往兩架飛機，因此任何兩條粗線不能有公共端點。稱一個圖中沒有公共端點的一組邊成為一個“匹配”。因此上述問題就轉(zhuǎn)化為：如何找一個包含最多邊的匹配，這個問題叫圖的最大匹配問題。例：飛行員搭配問題2－二部圖的最大匹配問題在例1中，如果飛行員分成兩部分，一部分是正駕駛員，一部分是副駕駛員。如何搭配正副駕駛員才能使得出航飛機最多的問題可以歸結(jié)為一個二部圖上的最大匹配問題。例如，假設(shè)有4個正駕駛員，有5個副駕駛員，飛機必須要有一名正駕駛員和一名副駕駛員才能起飛。正駕駛員和副駕駛員之間存在搭配的問題。Y1Y2Y3Y4Y5X1X2X3X4(b)圖(b)中，X1,X2,X3,X4表示4個正駕駛員，Y1,Y2,Y3,Y4,Y5表示5個副駕駛員。正駕駛員之間不能搭配，副駕駛員之間也不能搭配，所以這是一個二部圖。圖(b)中的4條藍色的粗線代表一種搭配方案。這個問題實際上是求一個二部圖的最大匹配。定義7.6

二部圖(二分圖)二部圖：如果圖G是一個簡單圖，它的頂點集合V是由兩個沒有公共元素的子集X={X1,X2,..,Xm}與子集Y={Y1,Y2,…,Yn}，并且Xi與Xj(1≤i,j≤m)之間，Ys與Yt(1≤s,t≤m)之間沒有邊連接，則G稱為二部圖。

對于一個圖G與給定的一個匹配M，如果圖G中不存在M的未蓋點(未蓋點的定義見7.3節(jié))，則稱匹配M為圖G的完美匹配。圖(a)中,M={e1,e4,e7}為完美匹配(最大匹配),它也是最小邊覆蓋。圖(b)中不可能有完美匹配,因此,對任何匹配都存在未蓋點。定義7.6完美(完備)匹配任取一個最大匹配,比如:M={e2,e4},則M∪{e6},M∪{e8},M∪{e7}都是圖的最小邊覆蓋。任取一個最小邊覆蓋,比如:W={e1,e3,e6},從中移去一條相鄰的邊,則{e1,e3}和{e1,e6}都是圖的最大匹配。我們通常這樣來做:用最大匹配通過增加關(guān)聯(lián)未蓋點的邊獲得最小邊覆蓋;用最小邊覆蓋通過移去相鄰的一條邊獲得最大匹配。(詳見定理7.3)定理7.3設(shè)n階圖G中無孤立點。(1)設(shè)M為G的一個最大匹配,對于G中每個M的未蓋點v,由與v關(guān)聯(lián)的邊所組成的邊集N,則W=M∪N為G中最小邊覆蓋;(2)設(shè)W1為G的最小邊覆蓋,若G中存在相鄰的邊就移去其中的一條,設(shè)移去的邊集為N1,則M1=W1-N1為G中一個最大匹配;(3)G中邊覆蓋數(shù)

1與匹配數(shù)

1,滿足:

1+

1=n。由“M為最大匹配”可知:|M|=

1。顯然,G中含有n-2

1個M的未蓋點。由“邊覆蓋的定義”可知:W=M∪N為G中的邊覆蓋,且

|W|=|M|+|N|=

1+n-2

1=n-

1由“W1是最小邊覆蓋”可知:W1中每條邊的兩個端點不可能都與W1中的其它邊相關(guān)聯(lián),因此,在由W1構(gòu)造M1時,每移去相鄰兩條邊中的一條時,將只產(chǎn)生一個M的未蓋點。所以,|N1|=|W1|-|M1|=M1的未蓋點數(shù)=n-2|M1|。整理后,得:|W1|=

1=n-|M1|。又M1是匹配,W是邊覆蓋,所以,|M1|

1,|W|

1。通過比較可得:

1=n-|M1|

n-

1=|W|

1。顯然上式中各等號成立,所以,|M1|=

1,|W|=

1,且

1+

1=n。由此可知:M1是最大匹配,W是最小邊覆蓋,且結(jié)論(3)成立。證：由定理7.3中的(1)可知:

1

1。由定義可知:|M|

1

1

|W|。所以,|M|

|W|成立。當?shù)忍柍闪r,說明:M是最大匹配,W是最小邊覆蓋。由定理7.3中(3)可知:

1+

1=2

1=n。顯然,G中無M的未蓋點。所以,M必為G中完美匹配。推論設(shè)G是n階無孤立點的圖,M為G中的匹配,W是G中的邊覆蓋,則|M|

|W|;(|M|表示M中邊的數(shù)目)

當?shù)忍柍闪r,M為G中完美匹配,W為G中最小邊覆蓋。證：右圖(a)中的{e1,e4,e7}為完美匹配,也是最小邊覆蓋。在下圖(a)中,M1={e3,e7}和M2={e2,e4,e6}都是其極大匹配。下圖(b)和(c)中實線邊所示。M1不是最大匹配,M2是最大匹配(也是完美匹配)。

=e2e3e4e7e6是關(guān)于M1的可增廣路徑。M2沒有可增廣路徑。7.3匹配問題的求解為了求解各種匹配問題，必須引入一系列概念：V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)

未蓋點

設(shè)Vi是圖G=<V,E>的一個頂點，M是圖G中一個給定的匹配，如果Vi不與任意一條屬于匹配M的邊相關(guān)聯(lián)，則稱Vi是匹配M的未蓋點。很形象：沒有被匹配M中的邊“蓋住”。取定M={e4,e6,e10}(由粗線組成的匹配)，則圖(a)中，V10就是M的一個未蓋點。V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)

交錯軌

設(shè)P是圖G的一條軌(路徑)，如果P的任意兩條相鄰的邊一定是一條屬于匹配M而另一條不屬于M，則稱P是一條交錯軌。在圖(a)中，取定M={e4,e6,e10}(由粗線組成的匹配)，則圖(b)、(c)所示的路徑都是交錯軌。特別地，如果軌P僅含一條邊，那么無論這條邊是否屬于匹配M，P一定是一條交錯軌。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)

可增廣軌

兩個端點都是未蓋點的交錯軌稱為可增廣軌。圖(b)所示的交錯軌的兩個端點V2,V11都是匹配M的未蓋點，所以這條軌是可增廣軌，而圖(c)所示的交錯軌不是可增廣軌。特別地，如果兩個未蓋點之間僅含一條邊，那么單單這條邊也組成一條可增廣軌。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)V1V5V9V11V6V2e1e4e7e10e12(b)V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d)可增廣軌的含義

對于圖G的一個匹配M來說，如果能找到一條可增廣軌P，那么這個匹配M一定可以通過下述方法改進成一個包含多一條邊的匹配Ms(即匹配M擴充了)：把P中原來屬于匹配M的邊從匹配M中去掉(粗邊改成細邊)，而把P中原來不屬于M的邊加到匹配Ms中去(細邊改成粗邊)，變化后的匹配Ms恰好比原匹配M多一條邊。如圖(a)中圖G的一個匹配M，找到圖(b)所示的一條可增廣軌，那么得到圖(d)所示的新匹配Ms。Ms比M多一條邊。證：1)必要性假設(shè):M為G中最大匹配。若G中存在M的可增廣路徑

,則

中在M中的邊比不在M中的少1。設(shè)M’=(M∪

(E))-(M∩

(E))=M

(E),則M’中邊彼此不鄰,且M’比M多一條邊,即:M’是比M多一條邊的匹配,這就與“M是最大匹配”相矛盾。所以,M不含可增廣路徑。定理7.4M為G的最大匹配,當且僅當G不含M可增廣路徑。2)充分性設(shè):M是G中不含可增廣路徑的匹配,M1是G中的最大匹配。下面證明:|M|=|M1|。設(shè):H=G[M1

M]。當H=

時顯然,M=M1,所以,M為G中最大匹配。若H

時由于M和M1都是匹配,所以,H各連通分支要么是由M和M1中的邊組成的交錯圈,在交錯圈上M和M1中的邊數(shù)相等,要么為由M和M1的邊組成的交錯路徑。由已知條件可知:M不含可增廣路徑,M1是最大匹配。由必要性可知:M1中也無可增廣的交錯路徑。所以,在由M和M1組成的交錯路徑上,M和M1的邊也相等,即:M與M1邊的個數(shù)相同。因此,M為最大匹配。求最大匹配的可行方法：給定一個初始匹配M(如果沒有給定，則M＝?)，如果圖G沒有未蓋點，則肯定不會有可增廣軌了，即M就是最大匹配。對圖G的所有未蓋點Vi，通過一定的方法搜索以Vi為端點的可增廣軌，從而通過可增廣軌逐漸把M擴大。(在擴大M的過程當中，某些未蓋點會逐漸被M蓋住)尋找可增廣軌的方法

交錯可達設(shè)M是圖G的一個匹配，Vi是取定的未蓋點，如果存在從Vi到Vj的交錯軌，則稱由Vi交錯可達Vj。以圖(d)為例，如果取定了未蓋點V4，那么存在著交錯軌P={V4,V3,V7,V6}，因此由V4交錯可達V6，同樣由V4還交錯可達V7等等。V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d)尋找以Vi為端點的可增廣軌的方法：設(shè)法把由Vi交錯可達的頂點都找出來，每找到一個，就檢查一下它是不是未蓋點，如果是，則可增廣軌就找到了。如果已經(jīng)把所有由Vi交錯可達的頂點都找出來了，而其中沒有一個是未蓋點，就可以肯定以Vi為一端的可增廣軌一定不存在了。為了把由Vi交錯可達的頂點都找出來，需要引入交錯樹的概念

交錯樹設(shè)M是圖G={V,E}的一個取定的匹配，T是圖G的一個子圖，如果T具有下述性質(zhì)：

(1)T是一棵樹；

(2)T中存在一個頂點Vi，它是未蓋點；

(3)對于T的任意一個不同于Vi的頂點來說，T中連接Vi與Vj的唯一軌是交錯軌。那么稱T是一個以Vi為根的交錯樹。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(a)V5V4V3V2V1V8V7(b)T+–+––++圖(a)中粗邊代表一個匹配。圖(b)所示的子圖就是一個以V1為根的交錯樹。為了描述如何擴大一個交錯樹，需要介紹有關(guān)頂點分類的概念

內(nèi)點、外點交錯樹T的頂點可以分成兩類：外點：即圖(b)中標‘+’號的頂點，如果Vj是外點，則連接根Vi與Vj的交錯軌一定含偶數(shù)條邊，且P上與Vj關(guān)聯(lián)的邊一定屬于匹配M。內(nèi)點：即圖(b)中標‘–’號的頂點，如果Vj是內(nèi)點，則連接根Vi與Vj的交錯軌一定含奇數(shù)條邊，且P上與Vj關(guān)聯(lián)的邊一定不屬于匹配M。V5V4V3V2V1V8V7(b)T+–+––++圖(b)中V1、V3、V5、V7為外點，而V2、V4、V8為內(nèi)點。擴大以Vi為根的交錯樹的方法看看圖G中有沒有與交錯樹T的外點關(guān)聯(lián)而不屬于T的邊e，如果有，就看看e的另一個端點Vk是不是屬于T(肯定不屬于T)，如果Vk不屬于T，那么就可以把e和Vk都加入到T中，使T擴大。在擴大的時候，還可以分為兩種情況：Vk是未蓋點，這時，把e與Vk加入到T中后，T中連接根Vi與Vk的交錯路是一條可增廣軌。(見下圖(a))Vk不是未蓋點，也就是說，有一條屬于匹配M的邊e'與Vk關(guān)聯(lián)，這時，在把e與Vk加入到T中后，還可以把e'以及它的端點Vm加入到T中去，因為很顯然從Vi也交錯可達e'的另一端點Vm。另外，Vk應該是內(nèi)點，而Vm是外點。(見下圖(b))(b)Vi+–+–––++Vje+VkVme'Vi+–+–––++未蓋點Vje(a)VkV1(a)+(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'eV3V2V1(b)+–+e'eV5V4V3V2V1V8V7(d)+–+––++ee'V5V4V3V2V1(c)+–+–+ee'下面圖(a)、(b)、(c)、(d)、(e)給出了從V1出發(fā)擴展交錯樹的具體過程。對于圖(e)所示的交錯樹，不能再用上述方法擴大了，因為找不到一條不屬于T的邊e，這條邊與T的某個外點關(guān)聯(lián)，且e的另一個端點Vk也不屬于T。但能不能就此斷定以V1為一端的可增廣軌一定不存在呢？答案是否定的(見下頁)。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(f)對于圖(e)中的交錯樹，已經(jīng)無法擴大了，但以V1為一端的可增廣軌是存在的。在圖(f)中用虛線標出的(V1,V2,V3,V4,V5,V7,V8,V9)就是一條連接V1和V9的可增廣軌。(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'e

帶花樹如果發(fā)現(xiàn)了一條不屬于交錯樹T的邊e，e的兩個端點都是T的外點，那么把e加到T中去得到的圖叫做帶花樹。(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'e例如在圖(e)中，連接T的兩個頂點V5與V7的這條邊e(圖中的紅邊)原不屬于T，現(xiàn)在把e加到T中去，只不過是使T增加了一條邊，沒有擴大由Vi交錯可達的頂點的范圍，反而使得T不再是樹了。帶花樹的特點是，它恰好有一個圈，這唯一的圈稱為帶花樹的花。圈內(nèi)包含奇數(shù)條邊。帶花樹的作用見“7.3.4任意圖的最大匹配”匹配問題匹配問題可以分為如下類型：二部圖的最大匹配；二部圖的完備匹配；二部圖的最佳匹配；任意圖的最大匹配；每種匹配問題的解法不一樣，難度也不一樣。7.3.1二分圖的最大匹配求二部圖的最大匹配的算法有：網(wǎng)絡(luò)流解法匈牙利算法Hopcroft-Karp算法(匈牙利算法的改進)1網(wǎng)絡(luò)流解法從二部圖G出發(fā)構(gòu)造一個網(wǎng)絡(luò)G’：增加一個源點S和匯點T；從S向X的每一個頂點都畫一條有向弧，從Y的每一個頂點都向T畫一條有向?。辉瓉鞧中的邊都改成有向弧，方向是從X的頂點指向Y的頂點；令所有弧的容量都等于1。求網(wǎng)絡(luò)G’的最大流F。從X的頂點指向Y的頂點的弧集合中，弧流量為1的弧對應二部圖的匹配邊，最大流值F對應二部圖的最大匹配的邊數(shù)。思考：為什么這樣構(gòu)造的網(wǎng)絡(luò)求出來的最大流就是最大匹配？Answer:網(wǎng)絡(luò)中所有的弧容量均為1。盡管在網(wǎng)絡(luò)中頂點Xi可能發(fā)出多條邊，但在最大流中只能選擇一條邊；盡管在網(wǎng)絡(luò)中可能有多條邊進入頂點Yi，但在最大流中只能選擇一條邊；以上第(2)、(3)點保證了最大流中二部圖中的邊不存在共同頂點。X1┊

Xi┊

XnSY1┊

Yi┊

YnT其中表示工人。表示工作。網(wǎng)絡(luò)流解法實例：

例：設(shè)有5位待業(yè)者，5項工作，他們各自能勝任工作的情況如下圖所示，要求設(shè)計一個就業(yè)方案，使盡量多的人能就業(yè)。按照前面描述的方法構(gòu)造網(wǎng)絡(luò)流(如上圖所示)：在二部圖中增加兩個頂點分別作為源點、匯點。并用有向邊把它們與原二部圖中頂點相連，令全部邊上的容量均為1。當網(wǎng)絡(luò)流達到最大時，如果在最大流中上的流量為1，就讓作工作，此即為最大匹配方案。第一次標號。調(diào)整第二次標號。再調(diào)整。第三次標號。調(diào)整。第四次標號。調(diào)整第五次標號。標號過程已無法再繼續(xù)。工人分別作故最多安排四個人工作。流量為1的畫彩線即所求的最大匹配。2匈牙利算法(Edmonds,1965)匈牙利算法的原理為：從當前匹配(如果沒有匹配，則初始匹配為0)出發(fā)，檢查每一個未蓋點，然后從它出發(fā)尋找可增廣路，找到可增廣路，則沿著這條可增廣路進行擴充，直到不存在可增廣路為止。根據(jù)從未蓋點出發(fā)尋找可增廣路搜索的方法，可以分為：1)DFS增廣2)BFS增廣3)多增廣路(Hopcroft-Karp算法)在算法中用到的一些變量如下：intnx,ny; //X和Y集合中頂點的個數(shù)intg[maxn][maxn]; //鄰接矩陣,X集合和Y集合中頂點間邊的信息intcx[maxn],cy[maxn];//cx[i]表示最終求得的最大匹配中與Xi匹配的Y頂點,cy[i]同理1)DFS增廣//DFS算法中記錄頂點訪問的狀態(tài)//如果mk[i]=0表示未訪問過，如果為1表示訪問過intmk[maxn];//從X集合中的頂點u出發(fā)用深度優(yōu)先的策略尋找增廣路//(這種增廣路只能使當前的匹配數(shù)增加1)intpath(intu){

for(intv=0;v<ny;v++)//考慮所有Yi頂點v {

if(g[u][v]&&!mk[v]) { mk[v]=1;

//如果v沒有匹配,或者如果v已經(jīng)匹配了，

//但從y[v]出發(fā)可以找到一條增廣路

if(cy[v]==-1||path(cy[v])) { cx[u]=v;//把v匹配給u cy[v]=u;//把u匹配給v

return1;//找到可增廣路

} } }

return0;//如果不存在從u出發(fā)的增廣路}intMaxMatch()//求二部圖最大匹配的匈牙利算法{

intres(0); memset(cx,0xff,sizeof(cx));//從0匹配開始增廣

memset(cy,0xff,sizeof(cy));

for(inti=0;i<=nx;i++) {

if(cx[i]==-1)//從每個未蓋點出發(fā)進行尋找增廣路

{ memset(mk,0,sizeof(mk)); res+=path(i);//每找到一條增廣路，可使得匹配數(shù)加1 } }

returnres;}優(yōu)點：實現(xiàn)簡潔，理解容易適用：稠密圖，由于邊多，dfs找增廣路很快復雜度：O(n^3)例題：ZOJ1654解題報告2)BFS增廣intpred[maxn],mk[maxn],open[maxn];intMaxMatch(){

inti,u,v,t,d,e,cur,tail,res(0);memset(mk,0xff,sizeof(mk));memset(cx,0xff,sizeof(cx));memset(cy,0xff,sizeof(cy));適用：稀疏二分圖，邊少，增廣路短復雜度：O(n^3)for(i=0;i<nx;i++){pred[i]=-1;

for(open[cur=tail=0]=i;cur<=tail&&cx[i]==-1;cur++){

for(u=open[cur],v=0;v<ny&&cx[i]==-1;v++){

if(g[u][v]&&mk[v]!=i){mk[v]=i;open[++tail]=cy[v];

if(open[tail]>=0){pred[open[tail]]=u;continue;}

for(d=u,e=v;d!=-1;t=cx[d],cx[d]=e,cy[e]=d,e=t,d=pred[d]);}}}

if(cx[i]!=-1)res++;}//endoffor

returnres;}3)多增廣路：Hopcroft-Karp算法(1972)intpred[maxn],mk[maxn],open[maxn],src[maxn];intMaxMatch(){

inti,u,v,t,d,e,cur,tail,res(0),p,flag;memset(mk,0xff,sizeof(mk));memset(cx,0xff,sizeof(cx));memset(cy,0xff,sizeof(cy));

for(p=1,flag=1;flag;p++){flag=0;

for(cur=tail=0,i=0;i<nx;i++){

if(cx[i]==-1)open[++tail]=i,pred[i]=-1,src[i]=i;}這是一類方法，每次增廣同時尋找多條不相交增廣路，由Hopcroft和Karp于1973