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

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

2、圖的最小點(diǎn)覆蓋數(shù)等于最大匹配數(shù)二部圖的最大點(diǎn)獨(dú)立數(shù)頂點(diǎn)個(gè)數(shù) 最大匹配數(shù)47.1 點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集(都是頂點(diǎn)的集合)定義定義7.1 設(shè)圖設(shè)圖G = , V* V, 若對(duì)于若對(duì)于 vi V - V*, vj V*, 使得使得: (vi, vj) E, 則稱則稱vjvi, 并稱并稱V*為為G的一個(gè)的一個(gè);若支配集若支配集V*的任何真子集都不是支配集的任何真子集都不是支配集, 則稱則稱V*是是;頂點(diǎn)數(shù)最少的支配集稱為頂點(diǎn)數(shù)最少的支配集稱為;最小支配集中的頂點(diǎn)數(shù)稱為最小支配集中的頂點(diǎn)數(shù)稱為, 記作記作或簡(jiǎn)記為或簡(jiǎn)記為 。圖圖(a)中，中，V*= v1, v5 就是一個(gè)支配集。因?yàn)榫褪且粋€(gè)支配

3、集。因?yàn)閂-V*=v2, v3, v4, v6, v7中的頂點(diǎn)都是中的頂點(diǎn)都是V*中頂點(diǎn)中頂點(diǎn)的鄰接頂點(diǎn)。的鄰接頂點(diǎn)。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支配集的性質(zhì)支配集的性質(zhì)1.若若G中無孤立頂點(diǎn)中無孤立頂點(diǎn)(度數(shù)為度數(shù)為0的頂點(diǎn)的頂點(diǎn))，則，則一個(gè)支配集一個(gè)支配集V

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

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

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

7、少的點(diǎn)覆蓋稱為;最小點(diǎn)覆蓋的頂點(diǎn)數(shù)稱為最小點(diǎn)覆蓋的頂點(diǎn)數(shù)稱為, 記作記作, 簡(jiǎn)記為簡(jiǎn)記為。定義定義7.3 圖圖(a)中，中，V*= v1, v3, v5, v7 就是一個(gè)點(diǎn)覆蓋就是一個(gè)點(diǎn)覆蓋集集11圖圖(a)中中, v2, v3, v4, v6, v7 , v1, v3, v5, v7 等都是極小等都是極小點(diǎn)覆蓋點(diǎn)覆蓋, v1, v3, v5, v7 是最小點(diǎn)覆蓋是最小點(diǎn)覆蓋, 0 = 4;圖圖(b)中中, v0 , v1, v2, , v6 都是極小點(diǎn)覆蓋都是極小點(diǎn)覆蓋, v0 是最小點(diǎn)覆蓋是最小點(diǎn)覆蓋, 0 = 1;圖圖(c)中中, v0, v1, v3, v4 , v0, v1, v3,

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

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

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

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

12、克競(jìng)賽指導(dǎo)圖論的算法與程序設(shè)計(jì)(PASCAL版)P58167.2 邊覆蓋集與匹配(都是邊的集合)定義定義7.4 設(shè)圖設(shè)圖G = , E* E, 若若 v V, e E*, 使得使得: v與與e相關(guān)聯(lián)相關(guān)聯(lián), 則稱則稱ev, 并稱并稱E*為為, 或簡(jiǎn)稱或簡(jiǎn)稱;若邊覆蓋若邊覆蓋E*的任何真子集都不是邊覆蓋的任何真子集都不是邊覆蓋, 則稱則稱E*是是;邊數(shù)最少的邊覆蓋集稱為邊數(shù)最少的邊覆蓋集稱為;最小的邊覆蓋所含的邊數(shù)稱為最小的邊覆蓋所含的邊數(shù)稱為, 記作記作或簡(jiǎn)記為或簡(jiǎn)記為。圖圖(a)中，中，E*= e1, e4, e7 就是一個(gè)邊覆蓋集就是一個(gè)邊覆蓋集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 設(shè)設(shè)G = , 若若E*(E* E)中任何兩條邊均不相鄰中任何兩條邊均不相鄰, 則稱則稱E*為為G中中, 也稱也稱E*為為G中的中的(MatchingMatching);若在若在E*中加入任意一條邊所得集合都不是匹配中加入任意一條邊所得集合都不是匹配, 則稱則稱E*為為;邊數(shù)最多的匹配稱為邊數(shù)最多的匹配稱為;最大匹

14、配的邊數(shù)稱為最大匹配的邊數(shù)稱為或或, 記作記作, 簡(jiǎn)記為簡(jiǎn)記為。定義定義7.5 圖圖(a)中，中，E*= e1, e4, e7 就是一個(gè)匹配就是一個(gè)匹配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最大匹配問題最大匹配問題 飛行大隊(duì)有若干個(gè)來自各地的飛行員，專門駕駛一種型號(hào)的飛飛行大隊(duì)有若干個(gè)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

38、可增廣軌。(見下圖見下圖(a)Vk不是未蓋點(diǎn)，也就是說，有一條屬于匹配不是未蓋點(diǎn)，也就是說，有一條屬于匹配M的邊的邊 與與Vk關(guān)聯(lián)，這時(shí)，關(guān)聯(lián)，這時(shí)，在把在把e與與Vk加入到加入到T中后，還可以把中后，還可以把 以及它的端點(diǎn)以及它的端點(diǎn)Vm加入到加入到T中去中去，因?yàn)楹茱@然從，因?yàn)楹茱@然從Vi也交錯(cuò)可達(dá)也交錯(cuò)可達(dá) 的另一端點(diǎn)的另一端點(diǎn)Vm。另外，。另外，Vk應(yīng)該是內(nèi)應(yīng)該是內(nèi)點(diǎn)，而點(diǎn)，而Vm是外點(diǎn)。是外點(diǎn)。(見下圖見下圖(b)(b)Vi+Vje+VkVmeVi+未蓋點(diǎn)未蓋點(diǎn)Vje(a)Vk39V1(a)+(e)V5V4V3V2V1V8V7+V15V6+eeV3V2V1(b)+eeV5V4V3V2

39、V1V8V7(d)+eeV5V4V3V2V1(c)+ee下面圖下面圖(a)、(b)、(c)、(d)、(e)給出了從給出了從V1出發(fā)擴(kuò)展交錯(cuò)樹的具體過程。出發(fā)擴(kuò)展交錯(cuò)樹的具體過程。對(duì)于圖對(duì)于圖(e)所示的交錯(cuò)樹，不能再用上述方法擴(kuò)大了，因?yàn)檎也坏揭粭l所示的交錯(cuò)樹，不能再用上述方法擴(kuò)大了，因?yàn)檎也坏揭粭l不屬于不屬于T的邊的邊e，這條邊與，這條邊與T的某個(gè)外點(diǎn)關(guān)聯(lián)，且的某個(gè)外點(diǎn)關(guān)聯(lián)，且e的另一個(gè)端點(diǎn)的另一個(gè)端點(diǎn)Vk也不也不屬于屬于T。但能不能就此斷定以但能不能就此斷定以V1為一端的可增廣軌一定不存在呢？答案是否定為一端的可增廣軌一定不存在呢？答案是否定的的(見下頁見下頁)。40V15V6V5V4V3

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

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

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

43、個(gè)源點(diǎn)S和匯點(diǎn)和匯點(diǎn)T；b)從從S向向X的每一個(gè)頂點(diǎn)都畫一條有向弧，從的每一個(gè)頂點(diǎn)都畫一條有向弧，從Y的每一個(gè)頂點(diǎn)的每一個(gè)頂點(diǎn)都向都向T畫一條有向??；畫一條有向?。籧)原來原來G中的邊都改成有向弧，方向是從中的邊都改成有向弧，方向是從X的頂點(diǎn)指向的頂點(diǎn)指向Y的頂?shù)捻旤c(diǎn)；點(diǎn)；d)令所有弧的容量都等于令所有弧的容量都等于1。2)求網(wǎng)絡(luò)求網(wǎng)絡(luò)G的最大流的最大流F。3)從從X的頂點(diǎn)指向的頂點(diǎn)指向Y的頂點(diǎn)的弧集合中，弧流量為的頂點(diǎn)的弧集合中，弧流量為1的弧對(duì)應(yīng)二部圖的的弧對(duì)應(yīng)二部圖的匹配邊，最大流值匹配邊，最大流值F對(duì)應(yīng)二部圖的最大匹配的邊數(shù)。對(duì)應(yīng)二部圖的最大匹配的邊數(shù)。為什么這樣構(gòu)造的網(wǎng)絡(luò)求出來的最為

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

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

46、邊上的容量均為1。當(dāng)。當(dāng)網(wǎng)絡(luò)流達(dá)到最大時(shí)，如果在最大流中網(wǎng)絡(luò)流達(dá)到最大時(shí)，如果在最大流中 上的流量為上的流量為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第一次標(biāo)號(hào)。第一次標(biāo)號(hào)。調(diào)整調(diào)整)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 (第二次標(biāo)號(hào)。第二次標(biāo)號(hào)。) 1 ,(sv) 1 ,(2x)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (再調(diào)整。再調(diào)整。491x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 (第三次標(biāo)號(hào)。第三次標(biāo)號(hào)。)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調(diào)整。調(diào)整。) 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、(第四次標(biāo)號(hào)。第四次標(biāo)號(hào)。)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 (調(diào)整調(diào)整) 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 (第五次標(biāo)號(hào)。第五次標(biāo)號(hào)。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標(biāo)號(hào)過程已無法再繼續(xù)。標(biāo)號(hào)過程已無法再繼續(xù)。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故最多安排四個(gè)人工作。故最多安排四個(gè)人工作。流量為流量為1的畫彩線即所求的最大匹配。的畫彩線即所求的最大匹配。562 匈牙利算法(Edmonds, 1965)匈牙利算法的原理為：從當(dāng)前匹配匈牙利算法的原理為：從當(dāng)前匹配(如果沒有匹配，則初如果沒有匹配，則初始匹配為始匹配為0)出發(fā)，檢查每一個(gè)未蓋點(diǎn)，然后從它出發(fā)尋找可增出發(fā)，檢查每一個(gè)未蓋點(diǎn)，然后從它出發(fā)尋找可增廣路，找到可增廣路，則沿著這條可增廣路進(jìn)行擴(kuò)充，直到廣路，找到可增廣路，則沿著這條可

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

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

55、已經(jīng)匹配了，已經(jīng)匹配了，/但從但從yv出發(fā)可以找到一條增廣路出發(fā)可以找到一條增廣路if(cyv = -1 | path(cyv)cxu = v; /把把v匹配給匹配給ucyv = u; /把把u匹配給匹配給vreturn 1; /找到可增廣路找到可增廣路return 0 ; /如果不存在從如果不存在從u出發(fā)的增廣路出發(fā)的增廣路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) /從每個(gè)未蓋點(diǎn)出發(fā)進(jìn)行尋找增廣路從每個(gè)未蓋點(diǎn)出發(fā)進(jìn)行尋找增廣路memset(mk , 0 , sizeof(mk) ;res += path(i) ; /每找到一條增廣路，可使得匹配數(shù)加每找到一條增廣路，可使得匹配數(shù)加1return res ;優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)潔，理解容易優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)潔，理解容易適用：稠密圖，由于邊多，適用：稠密圖，由于邊多，dfs找增廣路很快找增廣路很快復(fù)雜度：復(fù)雜度：O(n3)59例題：ZOJ 1654 解題報(bào)告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) ;適用：稀疏二分圖，邊少，增廣路短適用：稀疏二分圖，邊少，增廣路短復(fù)雜度：復(fù)雜度：O(n3)61 for (i = 0 ; i nx ; i+) predi = -1 ; for (opencur = tail = 0 = i ; cur = tail & cxi = -1 ; cur+) for