頻道欄目
首頁 > 資訊 > 其他 > 正文

二分圖匹配

16-08-05        來源:[db:作者]  
收藏   我要投稿

一、邊獨立集(匹配)

設無向圖為 G(V, E) ,邊的集合 E* ? E,若 E* 中的任何兩條邊均不相鄰,則稱 E* 為 G 的邊獨立集(edge independent set),也稱 E* 為 G 的匹配(matching)

所謂任何兩條邊均不相鄰,通俗的講,就是任何兩條邊都沒有公共頂點

例如,在圖(a)中,取 E* = {e1, e4, e7},則 E* 就是圖 G 的一個邊獨立集,因為 E* 中每兩條邊都沒有公共頂點

注意

在無向圖中存在將盡可能多的、相互獨立的邊包含到邊的集合 E* 中的問題,所以邊獨立集有極大和最大的概念

最小邊獨立集的概念是沒有意義的,因為對任何一個無向圖 G(V, E) ,取 E* = ? (空集),總是滿足邊獨立集的定義

若在 E* 中加入任意一條邊所得到的集合都不是匹配,則稱 E* 為極大匹配

邊數最多的匹配稱為最大匹配

最大匹配的邊數稱為邊獨立數匹配數,記為 β1(G),簡記為 β1

 

在圖(a)中,{e2, e6},{e3, e5} 和 {e1, e4, e7} 都是極大匹配,{e1, e4, e7} 是最大匹配。因此 β1 = 3

在圖(b)中,{e1, e4},{e2, e3} 和 {e4, e8} 都是極大匹配,也都是最大匹配,因此 β1 = 2

 

以下幾個概念都是針對無向圖 G(V, E) 中一個給定的匹配 M 而言的

在無向圖 G 中,若邊 (u, v) ∈ M,則稱頂點 u 與 v 被 M 所匹配

設 v 是圖 G 的一個頂點,如果 v 與 M 中的某條邊關聯,則稱 v 為 匹配 M 的蓋點

如果 v 不與任意一條屬于匹配 M 的邊關聯,則稱 v 為匹配 M 的未蓋點

所謂蓋點,就是被匹配中的邊蓋住了,而未蓋點就是沒有被匹配 M 中的邊“蓋住” 的頂點

例如,在圖(a)所示的無向圖中,取定 M = {e1, e4},M 中的邊用粗線標明,則頂點 v1 與 v2 被 M 所匹配

v1、v2、v3 和 v4 是 M 的蓋點,v5 和 v6 是 M 的蓋點

而在圖(b)中,取定 M = {e1, e4, e7},則 G 中不存在未蓋點


 

例 1 飛行員搭配問題 1 -- 最大匹配問題

飛行大隊有若干個來自各地的飛行員,專門駕駛一種型號的飛機,這種飛機每架有兩個飛行員

由于種種原因,例如互相配合的問題,有些飛行員不能在同一架飛機上飛行,問如何搭配飛行員,才能使出航的飛機最多

為簡單起見,設有 10 個飛行員,圖中的 v1, v2, … v10 就代表這 10 個飛行員

如果兩個人可以同機飛行,就在他們之間連一條線,否則就不連

圖中的 3 條粗線代表一種搭配方案

由于一個飛行員不能同時派往兩架飛機,因此任何兩條粗線不能有公共端點

因此該問題就轉化為:如何找一個包含最多邊的匹配,這個問題就是圖的最大匹配問題

 

二、二分圖(二部圖)匹配問題

例 2 飛行員搭配問題 2 -- 二分圖的最大匹配問題

在例 1 中,如果飛行員分成兩部分,一部分是正駕駛員,一部分是副駕駛員

如何搭配正副駕駛員才能使得出航飛機最多的問題可以歸結為一個二分圖上的最大匹配問題

例如,假設有 4 個正駕駛員,有 5 個副駕駛員,飛機必須要有一名正駕駛員和一名副駕駛員才能起飛

正駕駛員和副駕駛員之間存在搭配的問題

圖中, x1, x2, x3, x4 表示 4 個正駕駛員, y1, y2, y3, y4, y5 表示 5 個副駕駛員

正駕駛員之間不能搭配,副駕駛員之間也不能搭配,所以這是一個二分圖

圖中的 4 條粗線代表一種搭配方案。這個問題實際上是求一個二分圖的最大匹配

為方便敘述,我們總是把二分圖的兩個結點集稱為 X 和 Y,有時也稱為左邊和右邊,其中左邊是 X 集,右邊是 Y 集,如圖所示

這個問題可以用網絡流解決,但用增廣路算法更加簡潔

1、完美匹配

對于一個圖 G 與給定的一個匹配 M,如果圖 G 中不存在 M 的未蓋點,即所有點都是匹配點(匹配中的某一條邊的端點),則稱匹配 M 為圖 G 的完美匹配(perfect matching)

例如,在圖(a)所示的無向圖,取 M = {e1, e4, e7},則 M 是 G 的一個完美匹配

而在圖(b)中,不可能有完美匹配,因為對任何匹配都存在未蓋點

 

2、二分圖的完備匹配與完美匹配

設無向圖 G(V, E) 為二分圖,它的兩個頂點集合為 X 和 Y,且 |X| ≤ |Y|,M 為 G 中的一個最大匹配,且 |M| = |X|,則稱 M 為 X 到 Y 的二分圖 G 的完備匹配

若 |X| = |Y|,該完備匹配覆蓋住 G 的所有頂點,則該完備匹配也是完美匹配

例如,如圖所示的 3 個二分圖,其中圖(a)和圖(b)中取定的匹配 M 都是完備匹配,而圖(c)中不存在完備匹配

二分圖完備匹配的一個應用例子是:某公司有工作人員 x1, x2, …, xm,他們去做工作 y1, y2,y3, …, yn, n>m

每個人適合做其中一項或幾項工作,問能否恰當地安排使得每個人都分配到一項合適的工作

3、最佳匹配

繼續對上面的應用例子進行深化:

工作人員可以做各項工作,但效率未必一致,現在需要制定一個分工方案,使公司的總效益最大,這就是最佳分配問題

設 G(V, E) 為加權二分圖,它的兩個頂點集合反別為 X = {x1, x2, ..., xm}、Y = {y1, y2, ..., yn}

W(xi, yk) ≥ 0 表示工作人員 xi 做工作 yk 時的效益,權值總和最大的完備匹配稱為二分圖的最佳匹配

4、交錯路

設 P 是圖 G 的一條路徑,M 是圖 G 中一個給定的匹配,如果 P 的任意兩條相鄰的邊一定是一條屬于匹配 M 而另一條不屬于 M,則稱 P 是關于 M 的一條交錯路

例如,在圖(a)所示的圖中,取定 M = {e4, e6, e10},則圖(b)、(c)所示的路徑都是交錯路

特別地,如果路徑 P 僅含一條邊,那么無論這條邊是否屬于匹配 M,P 一定是一條交錯路

5、增廣路

對于一個給定的圖 G 和匹配 M,兩個端點都是未蓋點的交錯路稱為關于 M 的增廣路

例如,上面的圖(b)所示的交錯路的兩個端點 v2、v11 都是匹配 M 的未蓋點,所以這條路是增廣路,而上圖(c)所示的交錯路不是增廣路

特別地,如果兩個未蓋點之間僅含一條邊,那么單單這條邊也組成一條增廣路

在增廣路中,非匹配邊比匹配邊多一條

 

增廣路的作用是改進匹配

假設我們已經找到一個匹配,如何判斷它是不是最大匹配呢?

看增廣路

如果有一條增廣路,那么把此路上的匹配邊的非匹配邊互換,得到的匹配比剛才多一條邊

反過來,如果找不到增廣路,則當前匹配就是最大匹配

這就是增廣路定理,即一個匹配是最大匹配的充分必要條件是不存在增廣路

注意:這個充要條件適合于任意圖,不僅僅是二分圖

 

有個很有意思的游戲可以加深對增廣路算法的理解

這是一個無向圖上的游戲,Alice和 Bob 輪流操作,Alice 先走

第一次可以任選一個點放一枚棋子,以后每次把棋子移動到一個相鄰點上,并把棋子原先所在的點刪除,誰不能移動就算輸

若雙方都采取最優策略, 誰將取勝?

解:如果有完美匹配,則 Alice 輸,因為 Bob 只需沿著匹配邊走即可

否則 Alice 贏,因為任意求一個最大匹配,Alice 把棋子放在任一個未蓋點上,Bob 都只能把它移動到已蓋點上(否則得到增廣路)

Alice 沿著匹配邊移動,下一步 Bob 又只能把它移到另一個已蓋點上,只要 Bob 能移動,Alice 就能移動

6、增廣路算法

根據增廣路定理,最大匹配可以通過反復找增廣路來求解

如何找增廣路呢?

根據定義,首先需要選一個未蓋點 u 作為起點。不失一般性,設這個 u 是 X 的結點

接下來,需要選一個從 u 出發的非匹配邊 (u, v) ,到達 Y 結點 v

如果 v 是未蓋點,說明我們成功地找到了一條增廣路,否則說明 v 是匹配點,下一步得走匹配邊

因為一個匹配點恰好和一個匹配邊鄰接,這一步沒得選擇

設匹配點 v 鄰接的匹配邊的另一端為 left[v] ,則可以理解為從 u 直接走到了 left[v],而這個 left[v] 也是一個 X 結點

如果始終沒有找到未蓋點,最后會擴展出一顆所謂的匈牙利樹

 

這樣,我們得到了一個算法,即每次選一個未蓋點 u 進行 dfs

注意,如果找不到以 u 開頭的增廣路,則換一個未蓋點進行 dfs ,且以后再也不從 u 出發找增廣路

換句話說,如果以后存在一個從 u 出發的增廣路,那么現在就找得到

 

三、二分圖最佳完美匹配

假定有一個完全二分圖 G,每條邊有一個權值(可以是負數)

如何求出權值和最大的完美匹配?

Kuhn - Munkres 算法(KM 算法)可以解決這個問題

給每個頂點一個標號(稱為頂標),設頂點 x 的頂標為 l(x),頂點 y 的頂標為 l(y),頂點 x 與 y 之間的邊權為 w(x, y)

 

為了學習這個算法,我們先來看兩個概念

首先定義可行頂標(feasible vertex labling),它是一個結點函數 l,使得對于任意弧 (x, y),有 l(x) + l(y) ≥ w(x, y)

相等子圖(equality subgraph)是圖 G 的生成子圖,包含所有點,但只包含滿足 l(x) + l( y) = w(x, y) 的所有邊 w(x, y)

有一個極為重要的定理

如果相等子圖有完美匹配,則該匹配是原圖的最大權匹配


這個定理其實很容易證明

設 M* 是相等子圖的完美匹配,根據定義有 M* 的權和等于所有點的頂標之和

另一方面,任取 G 的一個完美匹配 M ,由于 M 中的邊只滿足不等式 l(x) + l(y) ≤ w(x, y),M 的權值不超過所有頂標之和,也就是 M* 的權和

這樣看來,問題的關鍵就是尋找好的可行頂標,使相等子圖有完美匹配

 

算法的思路是這樣的:

任意構造一個可行頂標(比如,X 結點的頂標為它出發所有邊的最大權值, Y 結點的頂標為 0),然后求相等子圖的最大匹配

如果存在完美匹配,算法終止,否則修改頂標使得相等子圖的邊變多,有更大機會存在完美匹配

相關TAG標簽
上一篇:臺積電:絕大多數7nm客戶都會轉向6nm_IT新聞_博客園
下一篇:最后一頁
相關文章
圖文推薦

關于我們 | 聯系我們 | 廣告服務 | 投資合作 | 版權申明 | 在線幫助 | 網站地圖 | 作品發布 | Vip技術培訓 | 舉報中心

版權所有: 紅黑聯盟--致力于做實用的IT技術學習網站

美女MM131爽爽爽毛片