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

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

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

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

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

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

0＋

0

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

1＋

1

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

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

1。ZOJ1364二部圖的最大點(diǎn)獨(dú)立數(shù)

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

1。(前提是該二部圖沒(méi)有孤立頂點(diǎn)，如果有孤立頂點(diǎn)，對(duì)這些孤立頂點(diǎn)要單獨(dú)考慮)ZOJ11377.1點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集

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

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

V,若對(duì)于

vi

V-V*,

vj

V*,使得:(vi,vj)

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

0(G)或簡(jiǎn)記為

0。圖(a)中，V*={v1,v5}就是一個(gè)支配集。因?yàn)閂-V*={v2,v3,v4,v6,v7}中的頂點(diǎn)都是V*中頂點(diǎn)的鄰接頂點(diǎn)。通俗地講，所謂支配集，就是V中的頂點(diǎn)要么是V*集合中的元素，要么與V*中的一個(gè)頂點(diǎn)相鄰。在圖(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中無(wú)孤立頂點(diǎn)(度數(shù)為0的頂點(diǎn))，則存在一個(gè)支配集V*，使得G中除V*外的所有頂點(diǎn)也組成一個(gè)支配集(即V-V*也是一個(gè)支配集)。若G中無(wú)孤立頂點(diǎn)(度數(shù)為0的頂點(diǎn))，V1*為極小支配集，則G中除V1*外的所有頂點(diǎn)也組成一個(gè)支配集(即V–V1*也是一個(gè)支配集)。(證明略)思考：在圖(a)中，取V*＝{v3,v5,v6,v7}，V*是支配集，但V-V*是否是支配集？極小支配集的求解參見(jiàn)吳文虎編著的《信息學(xué)奧林匹克競(jìng)賽指導(dǎo)－圖論的算法與程序設(shè)計(jì)(PASCAL版)》P54有電子版

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

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

0(G),簡(jiǎn)記為

0。定義7.2

點(diǎn)獨(dú)立集圖(a)中，V*={v1,v5}就是一個(gè)點(diǎn)獨(dú)立集，因?yàn)関1和v5是不相鄰的。圖(a)中,{v1,v5},{v3,v6},{v2,v4,v7}等都是極大點(diǎn)獨(dú)立集,其{v2,v4,v7}等為最大點(diǎn)獨(dú)立集,

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

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

0＝2。

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

V,若對(duì)于

e

E,

v

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

0(G),簡(jiǎn)記為

0。定義7.3

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

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

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

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

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

0+

0=n(頂點(diǎn)個(gè)數(shù))。

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

v

V-V*,一定有:

v’

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

E。假設(shè):u

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

V1*

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

設(shè)G=<V,E>中無(wú)孤立點(diǎn),V*(V*

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

V-V*,且(vi,vj)

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

0+

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

(都是邊的集合)定義7.4

覆蓋與邊覆蓋集

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

E,若

v

V,

e

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

1(G)或簡(jiǎn)記為

1。圖(a)中，E*={e1,e4,e7}就是一個(gè)邊覆蓋集。通俗地講，所謂邊覆蓋集E*，就是G中所有的頂點(diǎn)都是E*中邊的頂點(diǎn)(邊覆蓋頂點(diǎn))。圖(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中邊獨(dú)立集,也稱E*為G中的匹配(Matching);若在E*中加入任意一條邊所得集合都不是匹配,則稱E*為極大匹配;邊數(shù)最多的匹配稱為最大匹配;最大匹配的邊數(shù)稱為邊獨(dú)立數(shù)或匹配數(shù),記作

1(G),簡(jiǎn)記為

1。定義7.5

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

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

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

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

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

1與匹配數(shù)

1,滿足:

1+

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

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

1個(gè)M的未蓋點(diǎn)。由“邊覆蓋的定義”可知:W=M∪N為G中的邊覆蓋,且

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

1+n-2

1=n-

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

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

1,|W|

1。通過(guò)比較可得:

1=n-|M1|

n-

1=|W|

1。顯然上式中各等號(hào)成立,所以,|M1|=

1,|W|=

1,且

1+

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

1

1。由定義可知:|M|

1

1

|W|。所以,|M|

|W|成立。當(dāng)?shù)忍?hào)成立時(shí),說(shuō)明:M是最大匹配,W是最小邊覆蓋。由定理7.3中(3)可知:

1+

1=2

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

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

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

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

未蓋點(diǎn)

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

交錯(cuò)軌

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

可增廣軌

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

對(duì)于圖G的一個(gè)匹配M來(lái)說(shuō)，如果能找到一條可增廣軌P，那么這個(gè)匹配M一定可以通過(guò)下述方法改進(jìn)成一個(gè)包含多一條邊的匹配Ms(即匹配M擴(kuò)充了)：把P中原來(lái)屬于匹配M的邊從匹配M中去掉(粗邊改成細(xì)邊)，而把P中原來(lái)不屬于M的邊加到匹配Ms中去(細(xì)邊改成粗邊)，變化后的匹配Ms恰好比原匹配M多一條邊。如圖(a)中圖G的一個(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的最大匹配,當(dāng)且僅當(dāng)G不含M可增廣路徑。2)充分性設(shè):M是G中不含可增廣路徑的匹配,M1是G中的最大匹配。下面證明:|M|=|M1|。設(shè):H=G[M1

M]。當(dāng)H=

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

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

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

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

(1)T是一棵樹(shù)；

(2)T中存在一個(gè)頂點(diǎn)Vi，它是未蓋點(diǎn)；

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

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

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

Xi┊

XnSY1┊

Yi┊

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

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

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

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

//如果v沒(méi)有匹配,或者如果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匹配開(kāi)始增廣

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

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

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

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

returnres;}優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)潔，理解容易適用：稠密圖，由于邊多，dfs找增廣路很快復(fù)雜度：O(n^3)例題：ZOJ1654解題報(bào)告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));適用：稀疏二分圖，邊少，增廣路短復(fù)雜度：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;}這是一類方法，每次增廣同時(shí)尋找多條不相交增廣路，由Hopcroft和Karp于1973