1、信息學院信息技術教研室VsVtV2V4V3V12484279146V1V8V9V10V7V4V3V6V5V2王桂平王桂平第第7 7章支配集、覆蓋集、獨立集與匹配章支配集、覆蓋集、獨立集與匹配2本講內容會涉及以下容易相互混淆的內容：1.點支配集, 極小點支配集, 最小點支配集, ;v 支配的概念；2.點獨立集, 極大點獨立集, 最大點獨立集, ;3.點覆蓋集, 極小點覆蓋集, 最小點覆蓋集, ;v 覆蓋的概念；4.邊覆蓋集, 極小邊覆蓋集, 最小邊覆蓋集, ;5.邊獨立集(匹配), 極大邊獨立集(極大匹配), 最大邊獨立集(最大匹配), ;以上幾個量存在以下關系：3對二部圖，還有以下關系式：二部

2、圖的最小點覆蓋數等于最大匹配數二部圖的最大點獨立數頂點個數 最大匹配數47.1 點支配集、點覆蓋集、點獨立集(都是頂點的集合)定義定義7.1 設圖設圖G = , V* V, 若對于若對于 vi V - V*, vj V*, 使得使得: (vi, vj) E, 則稱則稱vjvi, 并稱并稱V*為為G的一個的一個;若支配集若支配集V*的任何真子集都不是支配集的任何真子集都不是支配集, 則稱則稱V*是是;頂點數最少的支配集稱為頂點數最少的支配集稱為;最小支配集中的頂點數稱為最小支配集中的頂點數稱為, 記作記作或簡記為或簡記為 。圖圖(a)中，中，V*= v1, v5 就是一個支配集。因為就是一個支配

3、集。因為V-V*=v2, v3, v4, v6, v7中的頂點都是中的頂點都是V*中頂點中頂點的鄰接頂點。的鄰接頂點。5在圖在圖(a)中中, v1, v5 , v3, v5 和和 v2, v4, v7 都是都是, v1, v5 , v4, v5 和和 v3, v6 都是都是, 。圖圖(b)為為7階星形圖階星形圖, v0 , v1, v2, ., v6 為為, v0 為為, 。圖圖(c)為輪圖為輪圖W6, v0 , v1, v3 , v1, v4 等都是等都是, 顯然顯然, 。6支配集的性質支配集的性質1.若若G中無孤立頂點中無孤立頂點(度數為度數為0的頂點的頂點)，則，則一個支配集一個支配集V

4、*，使得，使得G中除中除V*外的所有頂點也組成一個支配集外的所有頂點也組成一個支配集(即即V - V*也是一個支配集也是一個支配集)。2.若若G中無孤立頂點中無孤立頂點(度數為度數為0的頂點的頂點)，V1*為為支配集，則支配集，則G中除中除V1*外的所有頂點外的所有頂點組成一個支配集組成一個支配集(即即V V1*也是一也是一個支配集個支配集)。(證明略證明略)在圖在圖(a)中，取中，取V* v3, v5 , v6 , v7 ， V*是支配集，是支配集，但但V - V*是否是支配集？是否是支配集？7極小支配集的求解參見吳文虎編著的信息學奧林匹克競賽指導圖論的算法與程序設計(PASCAL版)P54

5、8 設圖設圖G = , V* V, 若若, 則稱則稱V*為為G的的, 或稱或稱;若在若在V*中加入任何頂點都不再是獨立集中加入任何頂點都不再是獨立集, 則稱則稱V*為為;頂點數最多的點獨立集稱為頂點數最多的點獨立集稱為;最大點獨立集的頂點數稱為最大點獨立集的頂點數稱為, 記作記作, 簡記為簡記為。定義定義7.2 圖圖(a)中，中，V*= v1, v5 就是一個點獨立集，因就是一個點獨立集，因為為v1和和v5是不相鄰的是不相鄰的9圖圖(a)中中, v1, v5 , v3, v6 , v2, v4, v7 等都是極大點等都是極大點獨立集獨立集, 其其 v2, v4, v7 等為最大點獨立集等為最大

6、點獨立集, 0 = 3;圖圖(b)中中, v0 , v1, v2, , v6 都是極大點獨立集都是極大點獨立集, 其其 v1, v2, , v6 是最大點獨立集是最大點獨立集, 0 = 6;圖圖(c)中中, v1, v3 , v1, v4 是極大點獨立集是極大點獨立集, 也都是最也都是最大點獨立集大點獨立集, 02。10 設設G = , V* V, 若對于若對于 e E, v V*, 使使得得: v與與e相關聯相關聯, 則稱則稱ve, 并稱并稱V*為為G的的或簡稱或簡稱;若點覆蓋若點覆蓋V*的任何真子集都不是點覆蓋的任何真子集都不是點覆蓋, 則稱則稱V*是是;頂點個數最少的點覆蓋稱為頂點個數最

7、少的點覆蓋稱為;最小點覆蓋的頂點數稱為最小點覆蓋的頂點數稱為, 記作記作, 簡記為簡記為。定義定義7.3 圖圖(a)中，中，V*= v1, v3, v5, v7 就是一個點覆蓋就是一個點覆蓋集集11圖圖(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,

8、 v5 都是極小點覆都是極小點覆蓋蓋, 也都是最小的點覆蓋也都是最小的點覆蓋, 0 = 4。12點支配集、點獨立集、點覆蓋集之間的聯系1)定理定理7.1：設設G = 中中，則，則G的的。逆命題不成立。逆命題不成立(即極小支配集未即極小支配集未必是極大獨立集必是極大獨立集)。2)一個獨立集是極大獨立集，當且僅當它是一個支配集。一個獨立集是極大獨立集，當且僅當它是一個支配集。3)定理定理7.2：設設G = 中無孤立點中無孤立點, V*(V* V)為為G的的, 當且僅當當且僅當。v 推論推論：設：設G是是n階無孤立點的圖，則階無孤立點的圖，則V*是是G的極小的極小(最小最小)點覆蓋，當且僅當點覆蓋，

9、當且僅當V-V*是是G的極大的極大(最大最大)點點獨立集，從而有獨立集，從而有 0 + 0 = n(頂點個數頂點個數)。13 設設G = 中中, 則則G的的。假設假設: V*是是G中的任意一個極大獨立集。中的任意一個極大獨立集。 v V - V*, 一定有一定有: v V*, 使得使得: (v, v) E。假設假設: u V-V*不與不與V*中任何頂點相鄰中任何頂點相鄰, 則則V* u 就是就是一個更大的獨立集一個更大的獨立集, 這與這與V*是極大獨立集相矛盾。是極大獨立集相矛盾。所以所以, V*是是G的支配集。的支配集。由由“V*是點獨立集是點獨立集”可知可知: V1* V*, V* - V

10、1*中的頂點中的頂點都不受都不受V1*中的頂點支配中的頂點支配, 即即: V1*不是支配集。不是支配集。所以所以, V*是極小支配集。是極小支配集。證：證：上面定理的上面定理的的。在右圖中的。在右圖中, v3, v5 是極小支配集是極小支配集, 但它不是獨立集但它不是獨立集, 更不更不是極大獨立集。是極大獨立集。定理定理7.114 設設G = 中無孤立點中無孤立點, V*(V* V)為為G的的, 當且僅當當且僅當。證：證：1) 必要性必要性假設假設: 存在存在vi, vj V - V*, 且且(vi, vj) E。由于頂點由于頂點vi和和vj都不在都不在V*中中, 這顯然與這顯然與“V*是點覆

11、蓋是點覆蓋”相相矛盾。矛盾。所以所以, V - V*為點獨立集。為點獨立集。 2) 充分性充分性假設假設: V - V*是點獨立集。是點獨立集。因此因此, 任意一條邊的兩個端點至少有一個在任意一條邊的兩個端點至少有一個在V*中。中。由定義可知由定義可知: V*是是G的點覆蓋。的點覆蓋。推論推論 設設G是是n階無孤立點的圖階無孤立點的圖, 則則V*是是G的極小的極小(最小最小)點覆點覆蓋蓋, 當且僅當當且僅當V-V*是是G的極大的極大(最大最大)點獨立集點獨立集, 從而有從而有 0 + 0 = n(頂點個數頂點個數)。定理定理7.215極大點獨立集與極小點覆蓋集的求解參見吳文虎編著的信息學奧林匹

12、克競賽指導圖論的算法與程序設計(PASCAL版)P58167.2 邊覆蓋集與匹配(都是邊的集合)定義定義7.4 設圖設圖G = , E* E, 若若 v V, e E*, 使得使得: v與與e相關聯相關聯, 則稱則稱ev, 并稱并稱E*為為, 或簡稱或簡稱;若邊覆蓋若邊覆蓋E*的任何真子集都不是邊覆蓋的任何真子集都不是邊覆蓋, 則稱則稱E*是是;邊數最少的邊覆蓋集稱為邊數最少的邊覆蓋集稱為;最小的邊覆蓋所含的邊數稱為最小的邊覆蓋所含的邊數稱為, 記作記作或簡記為或簡記為。圖圖(a)中，中，E*= e1, e4, e7 就是一個邊覆蓋集就是一個邊覆蓋集17圖圖(a)中中, e1, e4, e7

13、和和 e2, e5, e6, e7 都是極小邊覆蓋都是極小邊覆蓋, e1, e4, e7 是最小邊覆蓋是最小邊覆蓋, 1 = 3。圖圖(b)中中, e1, e3, e6 和和 e2, e4, e8 都是極小邊覆蓋都是極小邊覆蓋, 也也都是最小邊覆蓋都是最小邊覆蓋, 1 = 3。18 設設G = , 若若E*(E* E)中任何兩條邊均不相鄰中任何兩條邊均不相鄰, 則稱則稱E*為為G中中, 也稱也稱E*為為G中的中的(MatchingMatching);若在若在E*中加入任意一條邊所得集合都不是匹配中加入任意一條邊所得集合都不是匹配, 則稱則稱E*為為;邊數最多的匹配稱為邊數最多的匹配稱為;最大匹

14、配的邊數稱為最大匹配的邊數稱為或或, 記作記作, 簡記為簡記為。定義定義7.5 圖圖(a)中，中，E*= e1, e4, e7 就是一個匹配就是一個匹配19圖圖(a)中中, e2, e6 , e3, e5 , e1, e4, e7 都是極大匹配都是極大匹配, e1, e4, e7 是最大匹配是最大匹配, 1 = 3。圖圖(b)中中, e1, e3 , e2, e4 , e4, e7 都是極大匹配都是極大匹配, 也也都是最大匹配都是最大匹配, 1 = 2。20例：飛行員搭配問題例：飛行員搭配問題1 1最大匹配問題最大匹配問題 飛行大隊有若干個來自各地的飛行員，專門駕駛一種型號的飛飛行大隊有若干個

15、來自各地的飛行員，專門駕駛一種型號的飛機，這種飛機每架有兩個飛行員。由于種種原因，例如互相配機，這種飛機每架有兩個飛行員。由于種種原因，例如互相配合的問題，有些飛行員不能在同一架飛機上飛行，問如何搭配合的問題，有些飛行員不能在同一架飛機上飛行，問如何搭配飛行員，才能使飛行員，才能使。 為簡單起見，設有為簡單起見，設有1010個飛行員，圖個飛行員，圖(a)(a)中的中的V V1 1,V,V2 2, ,V V1010就代表這就代表這1010個飛行員。如果個飛行員。如果，否則就不連。，否則就不連。V9V3V1V2V4V5V7V6V8V10(a) 圖圖(a)(a)中的中的3 3條藍色的粗線代表條藍色的

16、粗線代表一種搭配方案。由于一個飛行一種搭配方案。由于一個飛行員不能同時派往兩架飛機，因員不能同時派往兩架飛機，因此此。稱一個圖中沒有公共端點。稱一個圖中沒有公共端點的一組邊成為一個的一組邊成為一個“”。因此上述問題就轉化為：因此上述問題就轉化為：，這，這個問題叫圖的個問題叫圖的。21例：飛行員搭配問題例：飛行員搭配問題2 2二部圖的最大匹配問題二部圖的最大匹配問題在例在例1 1中，如果飛行員分成兩部分，一部分是正駕駛員，一中，如果飛行員分成兩部分，一部分是正駕駛員，一部分是副駕駛員。如何搭配正副駕駛員才能使得出航飛機部分是副駕駛員。如何搭配正副駕駛員才能使得出航飛機最多的問題可以歸結為一個二部

17、圖上的最大匹配問題。最多的問題可以歸結為一個二部圖上的最大匹配問題。例如，假設有例如，假設有4 4個正駕駛員，有個正駕駛員，有5 5個副駕駛員，飛機必須要個副駕駛員，飛機必須要有一名正駕駛員和一名副駕駛員才能起飛。正駕駛員和副有一名正駕駛員和一名副駕駛員才能起飛。正駕駛員和副駕駛員之間存在搭配的問題。駕駛員之間存在搭配的問題。Y1Y2Y3Y4Y5X1X2X3X4(b)圖圖(b)中，中，X1,X2,X3,X4表示表示4個個正駕駛員，正駕駛員，Y1,Y2,Y3,Y4,Y5表示表示5個副駕駛員。正駕駛員之間個副駕駛員。正駕駛員之間不能搭配，副駕駛員之間也不不能搭配，副駕駛員之間也不能搭配，所以這是一

18、個能搭配，所以這是一個。圖圖(b)中的中的4條藍色的粗線代表條藍色的粗線代表一種搭配方案。這個問題實際一種搭配方案。這個問題實際上是求一個二部圖的上是求一個二部圖的。22定義定義7.6 ：如果圖：如果圖G是一個簡單圖，它的頂點集合是一個簡單圖，它的頂點集合V是由兩個沒是由兩個沒有公共元素的子集有公共元素的子集X=X1,X2,.,Xm與子集與子集Y=Y1,Y2,Yn，并，并且且Xi與與Xj(1i,jm)之間，之間，Ys與與Yt(1s,tm)之間沒有邊連接，之間沒有邊連接，則則G稱為稱為。23 對于一個圖對于一個圖G與給定的一個匹配與給定的一個匹配M，如果圖，如果圖G中不存在中不存在M的未的未蓋點

19、蓋點(未蓋點的定義見未蓋點的定義見7.3節節)，則稱匹配，則稱匹配M為圖為圖G的的。圖圖(a)中中, M = e1, e4, e7 為完美匹配為完美匹配(最大匹配最大匹配), 它也是最小邊覆蓋。它也是最小邊覆蓋。圖圖(b)中不可能有完美匹配中不可能有完美匹配, 因此因此, 對對任何匹配都存在未蓋點。任何匹配都存在未蓋點。定義定義7.6 24任取一個最大匹配任取一個最大匹配, 比如比如: M = e2, e4 , 則則M e6 , M e8 , M e7 都都是圖的最小邊覆蓋。是圖的最小邊覆蓋。任取一個最小邊覆蓋任取一個最小邊覆蓋, 比如比如: W = e1, e3, e6 , 從中移去一條相鄰

20、的邊從中移去一條相鄰的邊, 則則 e1, e3 和和 e1, e6 都是圖的最大匹配。都是圖的最大匹配。我們通常這樣來做我們通常這樣來做: 用最大匹配通過增加關聯未蓋點的邊獲得最小邊覆蓋用最大匹配通過增加關聯未蓋點的邊獲得最小邊覆蓋;用最小邊覆蓋通過移去相鄰的一條邊獲得最大匹配。用最小邊覆蓋通過移去相鄰的一條邊獲得最大匹配。(詳見定理詳見定理7.3)25定理定理7.3 設設n階圖階圖G中無孤立點。中無孤立點。(1) 設設M為為G的一個最大匹配的一個最大匹配, 對于對于G中每個中每個M的未蓋點的未蓋點v, 由與由與v關聯關聯的邊所組成的邊集的邊所組成的邊集N, 則則W = MN為為G中最小邊覆蓋

21、中最小邊覆蓋;(2) 設設W1為為G的最小邊覆蓋的最小邊覆蓋, 若若G中存在相鄰的邊就移去其中的一條中存在相鄰的邊就移去其中的一條, 設移去的邊集為設移去的邊集為N1, 則則M1 = W1 - N1為為G中一個最大匹配中一個最大匹配;(3) G中邊覆蓋數中邊覆蓋數 1與匹配數與匹配數 1, 滿足滿足: 1+ 1 = n。由由“M為最大匹配為最大匹配”可知可知: |M| = 1。顯然顯然, G中含有中含有n-2 1個個M的未蓋點。的未蓋點。由由“邊覆蓋的定義邊覆蓋的定義”可知可知: W = MN為為G中的邊覆蓋中的邊覆蓋, 且且|W| = |M|+|N| = 1 + n - 2 1 = n -

22、1由由“W1是最小邊覆蓋是最小邊覆蓋”可知可知: W1中每條邊的兩個端點不可能都與中每條邊的兩個端點不可能都與W1中的其它邊相中的其它邊相關聯關聯, 因此因此, 在由在由W1構造構造M1時時, 每移去相鄰兩條邊中的一條時每移去相鄰兩條邊中的一條時, 將只產生一個將只產生一個M的未蓋點的未蓋點。所以所以, |N1| = |W1| - |M1| = M1的未蓋點數的未蓋點數 = n - 2|M1|。整理后整理后, 得得: |W1| = 1 = n - |M1|。又又M1是匹配是匹配, W是邊覆蓋是邊覆蓋, 所以所以, |M1| 1, |W| 1。通過比較可得通過比較可得: 1 = n-|M1| n

23、 - 1 = |W| 1。顯然上式中各等號成立顯然上式中各等號成立, 所以所以, |M1| = 1, |W| = 1, 且且 1+ 1 = n。由此可知由此可知: M1是最大匹配是最大匹配, W是最小邊覆蓋是最小邊覆蓋, 且結論且結論(3)成立。成立。證：證：26由定理由定理7.3中的中的(1)可知可知: 1 1。由定義可知由定義可知: |M| 1 1 |W|。所以所以, |M| |W|成立。成立。當等號成立時當等號成立時, 說明說明: M是最大匹配是最大匹配, W是最小邊覆蓋是最小邊覆蓋。由定理由定理7.3中中(3)可知可知: 1 + 1 = 2 1 = n。顯然顯然, G中無中無M的未蓋點

24、。的未蓋點。所以所以, M必為必為G中完美匹配。中完美匹配。推論推論 設設G是是n階無孤立點的圖階無孤立點的圖, M為為G中的匹配中的匹配, W是是G中中的邊覆蓋的邊覆蓋, 則則|M| |W|; (|M|表示表示M中邊的數目中邊的數目)當等號成立時當等號成立時, M為為G中完美匹配中完美匹配, W為為G中最小邊覆中最小邊覆蓋。蓋。證：證：27右圖右圖(a)中的中的 e1, e4, e7 為完美匹配為完美匹配, 也是最小邊覆蓋。也是最小邊覆蓋。在下圖在下圖(a)中中, M1 = e3, e7 和和M2 = e2, e4, e6 都是其極大匹配。都是其極大匹配。下圖下圖(b)和和(c)中實線邊所示

25、。中實線邊所示。M1不是不是最大匹配最大匹配, M2是最大匹配是最大匹配(也是完美匹配也是完美匹配)。 = e2e3e4e7e6是關于是關于M1的可增廣路徑。的可增廣路徑。M2沒有可增廣沒有可增廣路徑。路徑。287.3 匹配問題的求解為了求解各種匹配問題，必須引入一系列概念：為了求解各種匹配問題，必須引入一系列概念：V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 設設Vi是圖是圖G = 的一個頂點，的一個頂點，M是圖是圖G中一個給定的中一個給定的匹配，如果匹配，如果Vi不與任意一條屬于匹配不與任意一條屬于匹配M的邊相關聯，則稱

26、的邊相關聯，則稱Vi是匹配是匹配M的的。很形象：沒有被匹配。很形象：沒有被匹配M中的邊中的邊“蓋蓋住住”。取定取定M=e4, e6, e10(由粗線組由粗線組成的匹配成的匹配)，則圖，則圖(a)中，中，V10就就是是M的一個未蓋點。的一個未蓋點。29V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 設設P是圖是圖G的一條軌的一條軌(路徑路徑)，如果，如果P的任意兩條相鄰的邊一定是的任意兩條相鄰的邊一定是一條屬于匹配一條屬于匹配M而另一條不屬于而另一條不屬于M，則稱，則稱P是一條是一條。在圖在圖(a)中，取定中，取定M=e4, e

27、6, e10(由粗線組成的匹配由粗線組成的匹配)，則圖，則圖(b)、(c)所示的路徑都是交錯軌。所示的路徑都是交錯軌。特別地，如果軌特別地，如果軌P僅含一條邊，那么無論這條邊是否屬于匹配僅含一條邊，那么無論這條邊是否屬于匹配M，P一定是一條交錯軌。一定是一條交錯軌。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)30V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 兩個端點都是未蓋點的兩個端點都是未蓋點的稱為稱為。圖圖(b)所示的交錯軌的兩個端點所示的交錯軌的兩個端點V2, V

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

29、V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d) 對于圖對于圖G的一個匹配的一個匹配M來說，如果能找到一條來說，如果能找到一條P，那，那么這個匹配么這個匹配M一定可以通過下述方法改進成一個包含多一條邊一定可以通過下述方法改進成一個包含多一條邊的匹配的匹配Ms(即匹配即匹配M擴充了擴充了)：如圖如圖(a)中圖中圖G的一個匹配的一個匹配M，找到圖，找到圖(b)所示的一條可增廣軌所示的一條可增廣軌，那么得到圖，那么得到圖(d)所示的新匹配所示的新匹配Ms。Ms比比M多一條邊。多一條邊。32證：證：1) 必要性必要性假設假設: M為為G中最大匹配。中最大匹配。若若G中

30、存在中存在M的可增廣路徑的可增廣路徑 , 則則 中在中在M中的邊比不中的邊比不在在M中的少中的少1。設設M = (M (E) - (M (E) = M(E), 則則M中邊中邊彼此不鄰彼此不鄰, 且且M比比M多一條邊多一條邊, 即即: M是比是比M多一條邊的多一條邊的匹配匹配, 這就與這就與“M是最大匹配是最大匹配”相矛盾。相矛盾。所以所以, M不含可增廣路徑。不含可增廣路徑。定理定理7.4 M為為G的最大匹配的最大匹配, 當且僅當當且僅當G不含不含M可增廣路徑?？稍鰪V路徑。332) 充分性充分性設設: M是是G中不含可增廣路徑的匹配中不含可增廣路徑的匹配, M1是是G中的最大匹配。中的最大匹配

31、。下面證明下面證明: |M| = |M1|。設設: H = GM1 M。當當H = 時時顯然顯然, M = M1, 所以所以, M為為G中最大匹配。中最大匹配。若若H 時時由于由于M和和M1都是匹配都是匹配, 所以所以, H各連通分支要么是由各連通分支要么是由M和和M1中的邊組成的交錯圈中的邊組成的交錯圈, 在交錯圈上在交錯圈上M和和M1中的邊數相等中的邊數相等, 要么為要么為由由M和和M1的邊組成的交錯路徑。的邊組成的交錯路徑。由已知條件可知由已知條件可知: M不含可增廣路徑不含可增廣路徑, M1是最大匹配。由必是最大匹配。由必要性可知要性可知: M1中也無可增廣的交錯路徑。中也無可增廣的交

32、錯路徑。所以所以, 在由在由M和和M1組成的交錯路徑上組成的交錯路徑上, M和和M1的邊也相等的邊也相等, 即即: M與與M1邊的個數相同。邊的個數相同。因此因此, M為最大匹配。為最大匹配。34求最大匹配的可行方法：給定一個初始匹配給定一個初始匹配M(如果沒有給定，則如果沒有給定，則M)，如果圖，如果圖G沒有未蓋點，則肯定不會有可增廣軌了，即沒有未蓋點，則肯定不會有可增廣軌了，即M就是最大匹就是最大匹配。配。對圖對圖G的所有未蓋點的所有未蓋點Vi，通過，通過搜索以搜索以Vi為端點的為端點的可增廣軌，從而通過可增廣軌逐漸把可增廣軌，從而通過可增廣軌逐漸把M擴大。擴大。(在擴大在擴大M的的過程當

33、中，某些未蓋點會逐漸被過程當中，某些未蓋點會逐漸被M蓋住蓋住)35尋找可增廣軌的方法 設設M是圖是圖G的一個匹配，的一個匹配，Vi是取定的未蓋點，如果存在從是取定的未蓋點，如果存在從Vi到到Vj的交錯軌，則稱的交錯軌，則稱。以圖以圖(d)為例，如果取定了未蓋點為例，如果取定了未蓋點V4，那么存在著交錯軌那么存在著交錯軌P=V4, V3, V7, V6，因此，因此，同樣，同樣V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d)尋找以尋找以Vi為端點的可增廣軌的方法：設法把由為端點的可增廣軌的方法：設法把由Vi交錯可達的頂點都找出交錯可

34、達的頂點都找出來，每找到一個，就檢查一下它是不是未蓋點，如果是，則可增廣軌就來，每找到一個，就檢查一下它是不是未蓋點，如果是，則可增廣軌就找到了。如果已經把所有由找到了。如果已經把所有由Vi交錯可達的頂點都找出來了，而其中沒有交錯可達的頂點都找出來了，而其中沒有一個是未蓋點，就可以肯定以一個是未蓋點，就可以肯定以Vi為一端的可增廣軌一定不存在了。為一端的可增廣軌一定不存在了。36為了把由為了把由Vi交錯可達的頂點都找出來，需要引入交錯樹的概念交錯可達的頂點都找出來，需要引入交錯樹的概念 設設M是圖是圖G=V,E的一個取定的匹配，的一個取定的匹配，T是圖是圖G的一個子圖，如的一個子圖，如果果T具

35、有下述性質：具有下述性質： (1) T是一棵樹；是一棵樹； (2) T中存在一個頂點中存在一個頂點Vi，它是未蓋點；，它是未蓋點； (3) 對于對于T的任意一個不同于的任意一個不同于Vi的頂點來說，的頂點來說，T中連接中連接Vi與與Vj的的唯一軌是交錯軌。唯一軌是交錯軌。 那么稱那么稱T是一個以是一個以Vi為根的為根的。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(a)V5V4V3V2V1V8V7(b) T+圖圖(a)中粗邊代表一個匹中粗邊代表一個匹配。圖配。圖(b)所示的子圖就所示的子圖就是一個以是一個以V1為根的交錯為根的交錯樹。樹。37為了描述如何擴大一個交錯

36、樹，需要介紹有關頂點分類的概念為了描述如何擴大一個交錯樹，需要介紹有關頂點分類的概念 交錯樹交錯樹T的頂點可以分成兩類：的頂點可以分成兩類： 外點：即圖外點：即圖(b)中標中標+號的頂點，如果號的頂點，如果Vj是外點，則連接根是外點，則連接根Vi與與Vj的交錯軌一定的交錯軌一定，且，且P上與上與Vj關聯的邊一定關聯的邊一定。 內點：即圖內點：即圖(b)中標中標號的頂點，如果號的頂點，如果Vj是內點，則連接根是內點，則連接根Vi與與Vj的交錯軌一定的交錯軌一定，且，且P上與上與Vj關聯的邊一定關聯的邊一定。V5V4V3V2V1V8V7(b) T+圖圖(b)中中V1、V3、V5、V7為外為外點，而

37、點，而V2、V4、V8為內點。為內點。38擴大以Vi為根的交錯樹的方法看看圖看看圖G中有沒有與交錯樹中有沒有與交錯樹T的外點關聯而不屬于的外點關聯而不屬于T的邊的邊e，如果，如果有，就看看有，就看看e的另一個端點的另一個端點Vk是不是屬于是不是屬于T(肯定不屬于肯定不屬于T)，如果，如果Vk不屬于不屬于T，那么就可以把，那么就可以把e和和Vk都加入到都加入到T中，使中，使T擴大。在擴擴大。在擴大的時候，還可以分為兩種情況：大的時候，還可以分為兩種情況：Vk是未蓋點，這時，把是未蓋點，這時，把e與與Vk加入到加入到T中后，中后，T中連接根中連接根Vi與與Vk的交錯路的交錯路是一條可增廣軌。是一條

38、可增廣軌。(見下圖見下圖(a)Vk不是未蓋點，也就是說，有一條屬于匹配不是未蓋點，也就是說，有一條屬于匹配M的邊的邊 與與Vk關聯，這時，關聯，這時，在把在把e與與Vk加入到加入到T中后，還可以把中后，還可以把 以及它的端點以及它的端點Vm加入到加入到T中去中去，因為很顯然從，因為很顯然從Vi也交錯可達也交錯可達 的另一端點的另一端點Vm。另外，。另外，Vk應該是內應該是內點，而點，而Vm是外點。是外點。(見下圖見下圖(b)(b)Vi+Vje+VkVmeVi+未蓋點未蓋點Vje(a)Vk39V1(a)+(e)V5V4V3V2V1V8V7+V15V6+eeV3V2V1(b)+eeV5V4V3V2

39、V1V8V7(d)+eeV5V4V3V2V1(c)+ee下面圖下面圖(a)、(b)、(c)、(d)、(e)給出了從給出了從V1出發擴展交錯樹的具體過程。出發擴展交錯樹的具體過程。對于圖對于圖(e)所示的交錯樹，不能再用上述方法擴大了，因為找不到一條所示的交錯樹，不能再用上述方法擴大了，因為找不到一條不屬于不屬于T的邊的邊e，這條邊與，這條邊與T的某個外點關聯，且的某個外點關聯，且e的另一個端點的另一個端點Vk也不也不屬于屬于T。但能不能就此斷定以但能不能就此斷定以V1為一端的可增廣軌一定不存在呢？答案是否定為一端的可增廣軌一定不存在呢？答案是否定的的(見下頁見下頁)。40V15V6V5V4V3

40、V2V1V12V13V14V11V8V7V9V10(f)對于圖對于圖(e)中的交錯樹，已經無法擴大了，但中的交錯樹，已經無法擴大了，但以以V1為一端的可增廣軌是存在的。在圖為一端的可增廣軌是存在的。在圖(f)中中用虛線標出的用虛線標出的(V1,V2,V3,V4,V5,V7,V8,V9)就是就是一條連接一條連接V1和和V9的可增廣軌。的可增廣軌。(e)V5V4V3V2V1V8V7+V15V6+ee41 如果發現了一條不屬于交錯樹如果發現了一條不屬于交錯樹T的邊的邊e，e的兩個端點都是的兩個端點都是T的外的外點，那么把點，那么把e加到加到T中去得到的圖叫做中去得到的圖叫做。(e)V5V4V3V2V

41、1V8V7+V15V6+ee例如在圖例如在圖(e)中，連接中，連接T的兩個頂點的兩個頂點V5與與V7的這條的這條邊邊e(圖中的紅邊圖中的紅邊)原不屬于原不屬于T，現在把，現在把e加到加到T中去中去，只不過是使，只不過是使T增加了一條邊，沒有擴大由增加了一條邊，沒有擴大由Vi交交錯可達的頂點的范圍，反而使得錯可達的頂點的范圍，反而使得T不再是樹了。不再是樹了。帶花樹的特點是，它恰好有一個圈，這唯一的圈帶花樹的特點是，它恰好有一個圈，這唯一的圈稱為帶花樹的花。圈內包含奇數條邊。稱為帶花樹的花。圈內包含奇數條邊。帶花樹的作用見帶花樹的作用見“7.3.4 任意圖的最大匹配任意圖的最大匹配”42匹配問題

42、匹配問題可以分為如下類型：匹配問題可以分為如下類型：1.二部圖的最大匹配；二部圖的最大匹配；2.二部圖的完備匹配；二部圖的完備匹配；3.二部圖的最佳匹配；二部圖的最佳匹配；4.任意圖的最大匹配；任意圖的最大匹配；每種匹配問題的解法不一樣，難度也不一樣。每種匹配問題的解法不一樣，難度也不一樣。437.3.1 二分圖的最大匹配求二部圖的最大匹配的算法有：求二部圖的最大匹配的算法有：1.網絡流解法網絡流解法2.匈牙利算法匈牙利算法3.Hopcroft-Karp算法算法(匈牙利算法的改進匈牙利算法的改進)441 網絡流解法1)從二部圖從二部圖G出發構造一個網絡出發構造一個網絡G：a)增加一個源點增加一

43、個源點S和匯點和匯點T；b)從從S向向X的每一個頂點都畫一條有向弧，從的每一個頂點都畫一條有向弧，從Y的每一個頂點的每一個頂點都向都向T畫一條有向??；畫一條有向?。籧)原來原來G中的邊都改成有向弧，方向是從中的邊都改成有向弧，方向是從X的頂點指向的頂點指向Y的頂的頂點；點；d)令所有弧的容量都等于令所有弧的容量都等于1。2)求網絡求網絡G的最大流的最大流F。3)從從X的頂點指向的頂點指向Y的頂點的弧集合中，弧流量為的頂點的弧集合中，弧流量為1的弧對應二部圖的的弧對應二部圖的匹配邊，最大流值匹配邊，最大流值F對應二部圖的最大匹配的邊數。對應二部圖的最大匹配的邊數。為什么這樣構造的網絡求出來的最為

44、什么這樣構造的網絡求出來的最大流就是最大匹配？大流就是最大匹配？(1) 網絡中所有的弧容量均為網絡中所有的弧容量均為1。(2) 盡管在網絡中頂點盡管在網絡中頂點Xi可能發出多條邊，但可能發出多條邊，但在最大流中只能選擇一條邊；在最大流中只能選擇一條邊；(3) 盡管在網絡中可能有多條邊進入頂點盡管在網絡中可能有多條邊進入頂點Yi，但在最大流中只能選擇一條邊；但在最大流中只能選擇一條邊；(4) 以上第以上第(2)、(3)點保證了最大流中二部圖中點保證了最大流中二部圖中的邊不存在共同頂點。的邊不存在共同頂點。X1 Xi XnSY1 Yi YnT45其中其中 表示工人。表示工人。 表示工作。表示工作。

45、1x2x3x4x5x1y2y3y4y5y51,xx 51,yy 例：設有例：設有5位待業者，位待業者，5項工作，他們各自能勝任工作的情況項工作，他們各自能勝任工作的情況如下圖所示，要求設計一個就業方案，使盡量多的人能就業。如下圖所示，要求設計一個就業方案，使盡量多的人能就業。461x2x3x4x5x1y2y3y4y5ysvtv按照前面描述的方法構造網絡流按照前面描述的方法構造網絡流(如上圖所示如上圖所示)：在二部圖中：在二部圖中增加兩個頂點增加兩個頂點 分別作為源點、匯點。并用有向邊把分別作為源點、匯點。并用有向邊把它們與原二部圖中頂點相連，令全部邊上的容量均為它們與原二部圖中頂點相連，令全部

46、邊上的容量均為1。當。當網絡流達到最大時，如果在最大流中網絡流達到最大時，如果在最大流中 上的流量為上的流量為1，就讓就讓 作作 工作，此即為最大匹配方案。工作，此即為最大匹配方案。,svtv),(jiyxixjy)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (471x2x3x4x5x1y2y3y4y5ysvtv),() 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(1x) 1 ,(1y第一次標號。第一次標號。調整調整)0 , 1 ()0 , 1 ()0 , 1 ()0 ,

47、 1 (481x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(4y) 1 , 1 () 1 , 1 (第二次標號。第二次標號。) 1 ,(sv) 1 ,(2x)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (再調整。再調整。491x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 (第三次標號。第三次標號。)0 , 1 ()0 , 1 ()0

48、 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 (501x2x3x4x5x1y2y3ysvtv),()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(5y) 1 , 1 () 1 ,(sv)0 , 1 ()0 , 1 () 1 ,(3x調整。調整。) 1 , 1 ()0 , 1 ()0 , 1 (5y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 (4y)0 , 1 (511x2x3x4x5x1y2y3y5ysvtv)0 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1

49、(第四次標號。第四次標號。)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 (4y) 1 , 1 (521x3x5x2y3y5ysvtv),()0 , 1 ()0 , 1 () 1 ,(2y) 1 , 1 ()0 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(4x) 1 ,(5y) 1 ,(3x) 1 ,(4y)0 , 1 () 1 ,(2x) 1 ,(1y) 1 ,(4x)0 , 1 (調整調整) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1

50、(1y4x) 1 , 1 (4y2x531x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (第五次標號。第五次標號。541x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,

51、1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(5y標號過程已無法再繼續。標號過程已無法再繼續。551x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1

52、 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (工人工人,1x,2x,3x4x分別作分別作,2y,1y,4y5y故最多安排四個人工作。故最多安排四個人工作。流量為流量為1的畫彩線即所求的最大匹配。的畫彩線即所求的最大匹配。562 匈牙利算法(Edmonds, 1965)匈牙利算法的原理為：從當前匹配匈牙利算法的原理為：從當前匹配(如果沒有匹配，則初如果沒有匹配，則初始匹配為始匹配為0)出發，檢查每一個未蓋點，然后從它出發尋找可增出發，檢查每一個未蓋點，然后從它出發尋找可增廣路，找到可增廣路，則沿著這條可增廣路進行擴充，直到廣路，找到可增廣路，則沿著這條可

53、增廣路進行擴充，直到不存在可增廣路為止。不存在可增廣路為止。根據從未蓋點出發尋找可增廣路搜索的方法，可以分為：根據從未蓋點出發尋找可增廣路搜索的方法，可以分為：1) DFS 增廣增廣2) BFS增廣增廣3) 多增廣路多增廣路(Hopcroft-Karp算法算法)在算法中用到的一些變量如下：在算法中用到的一些變量如下：int nx, ny;/X和和Y集合中頂點的個數集合中頂點的個數int gmaxnmaxn;/鄰接矩陣鄰接矩陣, X集合和集合和Y集合中頂點間邊的信息集合中頂點間邊的信息int cxmaxn , cymaxn;/cxi表示最終求得的最大匹配中與表示最終求得的最大匹配中與Xi匹配的匹

54、配的Y頂點頂點, cyi同理同理571) DFS 增廣/DFS算法中記錄頂點訪問的狀態算法中記錄頂點訪問的狀態/如果如果mki=0表示未訪問過，如果為表示未訪問過，如果為1表示訪問過表示訪問過int mkmaxn ;/從從X集合中的頂點集合中的頂點u出發用深度優先的策略尋找增廣路出發用深度優先的策略尋找增廣路/(這種增廣路只能使當前的匹配數增加這種增廣路只能使當前的匹配數增加1)int path(int u)for(int v = 0 ; v ny ; v+) /考慮所有考慮所有Yi頂點頂點vif(guv & !mkv)mkv = 1; /如果如果v沒有匹配沒有匹配,或者如果或者如果v

55、已經匹配了，已經匹配了，/但從但從yv出發可以找到一條增廣路出發可以找到一條增廣路if(cyv = -1 | path(cyv)cxu = v; /把把v匹配給匹配給ucyv = u; /把把u匹配給匹配給vreturn 1; /找到可增廣路找到可增廣路return 0 ; /如果不存在從如果不存在從u出發的增廣路出發的增廣路58int MaxMatch() /求二部圖最大匹配的匈牙利算法求二部圖最大匹配的匈牙利算法int res(0) ;memset(cx , 0 xff , sizeof(cx) ; /從從0匹配開始增廣匹配開始增廣memset(cy , 0 xff , sizeof(cy

56、) ;for(int i = 0 ; i = nx ; i+)if(cxi = -1) /從每個未蓋點出發進行尋找增廣路從每個未蓋點出發進行尋找增廣路memset(mk , 0 , sizeof(mk) ;res += path(i) ; /每找到一條增廣路，可使得匹配數加每找到一條增廣路，可使得匹配數加1return res ;優點：實現簡潔，理解容易優點：實現簡潔，理解容易適用：稠密圖，由于邊多，適用：稠密圖，由于邊多，dfs找增廣路很快找增廣路很快復雜度：復雜度：O(n3)59例題：ZOJ 1654 解題報告602) BFS 增廣int predmaxn , mkmaxn , openm

57、axn ;int MaxMatch() int i , u , v , t , d , e , cur , tail , res(0); memset(mk , 0 xff , sizeof(mk) ; memset(cx , 0 xff , sizeof(cx) ; memset(cy , 0 xff , sizeof(cy) ;適用：稀疏二分圖，邊少，增廣路短適用：稀疏二分圖，邊少，增廣路短復雜度：復雜度：O(n3)61 for (i = 0 ; i nx ; i+) predi = -1 ; for (opencur = tail = 0 = i ; cur = tail & cxi = -1 ; cur+) for