支配集、覆蓋集、獨(dú)立集與匹配

第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ù)=n1＋1

＝n，即：邊覆蓋數(shù)+邊獨(dú)立數(shù)=n對二部圖，還有以下關(guān)系式：二部圖的最小點(diǎn)覆蓋數(shù)0＝等于最大匹配數(shù)1。ZOJ1364二部圖的最大點(diǎn)獨(dú)立數(shù)0＝頂點(diǎn)個(gè)數(shù)n－最大匹配數(shù)1。(前提是該二部圖沒有孤立頂點(diǎn)，如果有孤立頂點(diǎn)，對這些孤立頂點(diǎn)要單獨(dú)考慮)ZOJ11377.1點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集

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

支配與支配集設(shè)圖G=<V,E>,V*V,若對于viV-V*,vjV*,使得:(vi,vj)E,則稱vj支配vi,并稱V*為G的一個(gè)支配集;若支配集V*的任何真子集都不是支配集,則稱V*是極小支配集;頂點(diǎn)數(shù)最少的支配集稱為最小支配集;最小支配集中的頂點(diǎn)數(shù)稱為支配數(shù),記作0(G)或簡記為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中無孤立頂點(diǎn)(度數(shù)為0的頂點(diǎn))，則存在一個(gè)支配集V*，使得G中除V*外的所有頂點(diǎn)也組成一個(gè)支配集(即V-V*也是一個(gè)支配集)。若G中無孤立頂點(diǎn)(度數(shù)為0的頂點(diǎn))，V1*為極小支配集，則G中除V1*外的所有頂點(diǎn)也組成一個(gè)支配集(即V–V1*也是一個(gè)支配集)。(證明略)思考：在圖(a)中，取V*＝{v3,v5,v6,v7}，V*是支配集，但V-V*是否是支配集？極小支配集的求解參見吳文虎編著的《信息學(xué)奧林匹克競賽指導(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),簡記為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,若對于eE,vV*,使得:v與e相關(guān)聯(lián),則稱v覆蓋e,并稱V*為G的點(diǎ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),簡記為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>中無孤立點(diǎn)，則G的極大點(diǎn)獨(dú)立集都是G的極小支配集。逆命題不成立(即極小支配集未必是極大獨(dú)立集)。一個(gè)獨(dú)立集是極大獨(dú)立集，當(dāng)且僅當(dāng)它是一個(gè)支配集。定理7.2：設(shè)G=<V,E>中無孤立點(diǎn),V*(V*V)為G的點(diǎn)覆蓋,當(dāng)且僅當(dāng)V-V*為G的點(diǎn)獨(dú)立集。推論：設(shè)G是n階無孤立點(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>中無孤立點(diǎn),則G的極大點(diǎn)獨(dú)立集都是G的極小支配集。假設(shè):V*是G中的任意一個(gè)極大獨(dú)立集。vV-V*,一定有:v’V*,使得:(v,v’)E。假設(shè):uV-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>中無孤立點(diǎn),V*(V*V)為G的點(diǎn)覆蓋,當(dāng)且僅當(dāng)V-V*為G的點(diǎn)獨(dú)立集。證：1)必要性假設(shè):存在vi,vjV-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階無孤立點(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)覆蓋集的求解參見吳文虎編著的《信息學(xué)奧林匹克競賽指導(dǎo)－圖論的算法與程序設(shè)計(jì)(PASCAL版)》P587.2邊覆蓋集與匹配

(都是邊的集合)定義7.4

覆蓋與邊覆蓋集

設(shè)圖G=<V,E>,E*E,若vV,eE*,使得:v與e相關(guān)聯(lián),則稱e覆蓋v,并稱E*為邊覆蓋集,或簡稱邊覆蓋;若邊覆蓋E*的任何真子集都不是邊覆蓋,則稱E*是極小邊覆蓋;邊數(shù)最少的邊覆蓋集稱為最小的邊覆蓋;最小的邊覆蓋所含的邊數(shù)稱為邊覆蓋數(shù),記作1(G)或簡記為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),簡記為1。定義7.5

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

二部圖(二分圖)二部圖：如果圖G是一個(gè)簡單圖，它的頂點(diǎn)集合V是由兩個(gè)沒有公共元素的子集X={X1,X2,..,Xm}與子集Y={Y1,Y2,…,Yn}，并且Xi與Xj(1≤i,j≤m)之間，Ys與Yt(1≤s,t≤m)之間沒有邊連接，則G稱為二部圖。對于一個(gè)圖G與給定的一個(gè)匹配M，如果圖G中不存在M的未蓋點(diǎn)(未蓋點(diǎn)的定義見7.3節(jié))，則稱匹配M為圖G的完美匹配。圖(a)中,M={e1,e4,e7}為完美匹配(最大匹配),它也是最小邊覆蓋。圖(b)中不可能有完美匹配,因此,對任何匹配都存在未蓋點(diǎn)。定義7.6完美(完備)匹配任取一個(gè)最大匹配,比如:M={e2,e4},則M∪{e6},M∪{e8},M∪{e7}都是圖的最小邊覆蓋。任取一個(gè)最小邊覆蓋,比如:W={e1,e3,e6},從中移去一條相鄰的邊,則{e1,e3}和{e1,e6}都是圖的最大匹配。我們通常這樣來做:用最大匹配通過增加關(guān)聯(lián)未蓋點(diǎn)的邊獲得最小邊覆蓋;用最小邊覆蓋通過移去相鄰的一條邊獲得最大匹配。(詳見定理7.3)定理7.3設(shè)n階圖G中無孤立點(diǎn)。(1)設(shè)M為G的一個(gè)最大匹配,對于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-21個(gè)M的未蓋點(diǎn)。由“邊覆蓋的定義”可知:W=M∪N為G中的邊覆蓋,且 |W|=|M|+|N|=1+n-21=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。通過比較可得: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í),說明:M是最大匹配,W是最小邊覆蓋。由定理7.3中(3)可知:1+1=21=n。顯然,G中無M的未蓋點(diǎn)。所以,M必為G中完美匹配。推論設(shè)G是n階無孤立點(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沒有可增廣路徑。7.3匹配問題的求解為了求解各種匹配問題，必須引入一系列概念：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中的邊“蓋住”。取定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僅含一條邊，那么無論這條邊是否屬于匹配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)可增廣軌的含義

對于圖G的一個(gè)匹配M來說，如果能找到一條可增廣軌P，那么這個(gè)匹配M一定可以通過下述方法改進(jìn)成一個(gè)包含多一條邊的匹配Ms(即匹配M擴(kuò)充了)：把P中原來屬于匹配M的邊從匹配M中去掉(粗邊改成細(xì)邊)，而把P中原來不屬于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[M1M]。當(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中也無可增廣的交錯(cuò)路徑。所以,在由M和M1組成的交錯(cuò)路徑上,M和M1的邊也相等,即:M與M1邊的個(gè)數(shù)相同。因此,M為最大匹配。求最大匹配的可行方法：給定一個(gè)初始匹配M(如果沒有給定，則M＝?)，如果圖G沒有未蓋點(diǎn)，則肯定不會(huì)有可增廣軌了，即M就是最大匹配。對圖G的所有未蓋點(diǎn)Vi，通過一定的方法搜索以Vi為端點(diǎn)的可增廣軌，從而通過可增廣軌逐漸把M擴(kuò)大。(在擴(kuò)大M的過程當(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)都找出來，每找到一個(gè)，就檢查一下它是不是未蓋點(diǎn)，如果是，則可增廣軌就找到了。如果已經(jīng)把所有由Vi交錯(cuò)可達(dá)的頂點(diǎn)都找出來了，而其中沒有一個(gè)是未蓋點(diǎn)，就可以肯定以Vi為一端的可增廣軌一定不存在了。為了把由Vi交錯(cuò)可達(dá)的頂點(diǎn)都找出來，需要引入交錯(cuò)樹的概念交錯(cuò)樹設(shè)M是圖G={V,E}的一個(gè)取定的匹配，T是圖G的一個(gè)子圖，如果T具有下述性質(zhì)：(1)T是一棵樹；(2)T中存在一個(gè)頂點(diǎn)Vi，它是未蓋點(diǎn)；(3)對于T的任意一個(gè)不同于Vi的頂點(diǎn)來說，T中連接Vi與Vj的唯一軌是交錯(cuò)軌。那么稱T是一個(gè)以Vi為根的交錯(cuò)樹。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(a)V5V4V3V2V1V8V7(b)T+–+––++圖(a)中粗邊代表一個(gè)匹配。圖(b)所示的子圖就是一個(gè)以V1為根的交錯(cuò)樹。為了描述如何擴(kuò)大一個(gè)交錯(cuò)樹，需要介紹有關(guān)頂點(diǎn)分類的概念內(nèi)點(diǎn)、外點(diǎn)交錯(cuò)樹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ò)樹的方法看看圖G中有沒有與交錯(cuò)樹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ò)路是一條可增廣軌。(見下圖(a))Vk不是未蓋點(diǎn)，也就是說，有一條屬于匹配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)。(見下圖(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ò)樹的具體過程。對于圖(e)所示的交錯(cuò)樹，不能再用上述方法擴(kuò)大了，因?yàn)檎也坏揭粭l不屬于T的邊e，這條邊與T的某個(gè)外點(diǎn)關(guān)聯(lián)，且e的另一個(gè)端點(diǎn)Vk也不屬于T。但能不能就此斷定以V1為一端的可增廣軌一定不存在呢？答案是否定的(見下頁)。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(f)對于圖(e)中的交錯(cuò)樹，已經(jīng)無法擴(kuò)大了，但以V1為一端的可增廣軌是存在的。在圖(f)中用虛線標(biāo)出的(V1,V2,V3,V4,V5,V7,V8,V9)就是一條連接V1和V9的可增廣軌。(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'e

帶花樹如果發(fā)現(xiàn)了一條不屬于交錯(cuò)樹T的邊e，e的兩個(gè)端點(diǎn)都是T的外點(diǎn)，那么把e加到T中去得到的圖叫做帶花樹。(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'e例如在圖(e)中，連接T的兩個(gè)頂點(diǎn)V5與V7的這條邊e(圖中的紅邊)原不屬于T，現(xiàn)在把e加到T中去，只不過是使T增加了一條邊，沒有擴(kuò)大由Vi交錯(cuò)可達(dá)的頂點(diǎn)的范圍，反而使得T不再是樹了。帶花樹的特點(diǎn)是，它恰好有一個(gè)圈，這唯一的圈稱為帶花樹的花。圈內(nèi)包含奇數(shù)條邊。帶花樹的作用見“7.3.4任意圖的最大匹配”匹配問題匹配問題可以分為如下類型：二部圖的最大匹配；二部圖的完備匹配；二部圖的最佳匹配；任意圖的最大匹配；每種匹配問題的解法不一樣，難度也不一樣。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畫一條有向弧；原來G中的邊都改成有向弧，方向是從X的頂點(diǎn)指向Y的頂點(diǎn)；令所有弧的容量都等于1。求網(wǎng)絡(luò)G’的最大流F。從X的頂點(diǎn)指向Y的頂點(diǎn)的弧集合中，弧流量為1的弧對應(yīng)二部圖的匹配邊，最大流值F對應(yīng)二部圖的最大匹配的邊數(shù)。思考：為什么這樣構(gòu)造的網(wǎng)絡(luò)求出來的最大流就是最大匹配？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)過程已無法再繼續(xù)。工人分別作故最多安排四個(gè)人工作。流量為1的畫彩線即所求的最大匹配。2匈牙利算法(Edmonds,1965)匈牙利算法的原理為：從當(dāng)前匹配(如果沒有匹配，則初始匹配為0)出發(fā)，檢查每一個(gè)未蓋點(diǎn)，然后從它出發(fā)尋找可增廣路，找到可增廣路，則沿著這條可增廣路進(jìn)行擴(kuò)充，直到不存在可增廣路為止。根據(jù)從未蓋點(diǎn)出發(fā)尋找可增廣路搜索的方法，可以分為：1)DFS增廣2)BFS增廣3)多增廣路(Hopcroft-Karp算法)在算法中用到的一些變量如下：int

nx,ny; //X和Y集合中頂點(diǎn)的個(gè)數(shù)intg[maxn][maxn]; //鄰接矩陣,X集合和Y集合中頂點(diǎn)間邊的信息int

cx[maxn],cy[maxn];//cx[i]表示最終求得的最大匹配中與Xi匹配的Y頂點(diǎn),cy[i]同理1)DFS增廣//DFS算法中記錄頂點(diǎn)訪問的狀態(tài)//如果mk[i]=0表示未訪問過，如果為1表示訪問過int

mk[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沒有匹配,或者如果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)//從每個(gè)未蓋點(diǎn)出發(fā)進(jìn)行尋找增廣路 {

memset(mk,0,

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

returnres;}優(yōu)點(diǎn)：實(shí)現(xià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

return

res;}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年提出，有非常優(yōu)秀的時(shí)間界。以下代碼由BFS的框架直接修改而來：

for(;cur<=tail;cur++){u=open[cur];

if(cx[src[u]]!=-1)continue;

for(v=0;v<ny;v++){if(g[u][v]&&mk[v]!=p){mk[v]=p;open[++tail]=cy[v];

if(open[tail]>=0){pred[open[tail]]=u;src[open[tail]]=src[u];continue;}for(tail--,flag=1,d=u,e=v;d!=-1;t=cx[d],cx[d]=e,cy[e]=d,e=t,d=pred[d]);}}}//endoffor}//endoffor

for(i=0;i<n;i++)res+=(cx[i]!=-1);

returnres;}還可以用DFS來找多增廣路。根據(jù)圖的稠密程度，來考慮用哪種實(shí)現(xiàn)。優(yōu)點(diǎn)：復(fù)雜度低，實(shí)現(xiàn)相對簡單復(fù)雜度：O(n^2.5)應(yīng)用：這種方法還可以應(yīng)用到類似二分圖的網(wǎng)絡(luò)中，或者多部的網(wǎng)絡(luò)中，求最大流?？梢詷O高的加快程序的運(yùn)行。7.3.2二部圖的完備匹配問題的提出：某公司有工作人員X1,X2,…,Xm，他們?nèi)プ龉ぷ鱕1,Y2,Y3,…,Yn，每個(gè)人適合做其中一項(xiàng)或幾項(xiàng)工作，問能否每個(gè)人都分配到一項(xiàng)合適的工作？定義7.7完備匹配設(shè)G=<V1,V2,E>為二部圖,|V1||V2|,M為G中一個(gè)最大匹配,且|M|=|V1|,則稱M為V1到V2的完備匹配;若|V1|=|V2|,則完備匹配為完美匹配;若|V1|<|V2|,則完備匹配為G中最大匹配。下圖(a)和(b)都存在完備匹配(實(shí)線邊所示)。圖(c)中沒有完備匹配,實(shí)線邊組成集合是最大匹配,但不是完備匹配。7.3.3二部圖的最佳匹配問題的提出：在第3節(jié)完備匹配中例舉的分工問題中，工作人員可以做各項(xiàng)工作，但效率未必一致，我們需要制定一個(gè)分工方案，使公司的總效益最大，這就是最佳分配問題。數(shù)學(xué)模型：G是加權(quán)二部圖，頂點(diǎn)劃分成兩個(gè)集合，工作人員集合X={X1,X2,..,Xm}，工作集合Y={Y1,Y2,…,Yn}，W(Xi,Yj)≥0表示工作人員Xi做工作Yj時(shí)的效益，求權(quán)值總和最大的完備匹配稱為二部圖的最佳匹配。KM算法(Kuhn和Munkres,1957)KM算法用來解決最大權(quán)匹配問題：在一個(gè)二分圖內(nèi)，左頂點(diǎn)為X，右頂點(diǎn)為Y，現(xiàn)對于每組左右連接XiYj有權(quán)wij，求一種匹配使得所有wij的和最大。

該算法是通過給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)（叫做頂標(biāo)）來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題的。設(shè)頂點(diǎn)Xi的頂標(biāo)為A[i]，頂點(diǎn)Yj的頂標(biāo)為B[j]，頂點(diǎn)Xi與Yj之間的邊權(quán)為w[i,j]。在算法執(zhí)行過程中的任一時(shí)刻，對于任一條邊(i,j)，A[i]+B[j]>=w[i,j]始終成立。

7.3.4KMKM算法的正確性基于以下定理：

若由二分圖中所有滿足A[i]+B[j]=w[i,j]的邊(i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個(gè)完備匹配就是二分圖的最大權(quán)匹配。

首先解釋下什么是完備匹配，所謂的完備匹配就是在二部圖中，X點(diǎn)集中的所有點(diǎn)都有對應(yīng)的匹配或者是

Y點(diǎn)集中所有的點(diǎn)都有對應(yīng)的匹配，則稱該匹配為完備匹配。

這個(gè)定理是顯然的。因?yàn)閷τ诙謭D的任意一個(gè)匹配，如果它包含于相等子圖，那么它的邊權(quán)和等于所有頂點(diǎn)的頂標(biāo)和；如果它有的邊不包含于相等子圖，那么它的邊權(quán)和小于所有頂點(diǎn)的頂標(biāo)和。所以相等子圖的完備匹配一定