二分覆蓋

二分圖又稱作二部圖，是圖論中的一種特殊模，頂點集V可分割為兩個互不相交的子集，並且圖中每條邊依附的兩個頂點都分屬於這兩個互不相交的子集，兩個子集內的頂點不相鄰。在二分圖中尋找最小覆蓋的問題為二分覆蓋（bipartite - cover）問題。

基本介紹

• 中文名：二分覆蓋
• 外文名：bipartite  - cover
• 性質：N P -複雜問題
• 實質：在二分圖中尋找最小覆蓋
• 解決算法：貪婪算法
• 套用學科：計算機科學、機械工程

二分圖

二分圖又稱作二部圖，是圖論中的一種特殊模型。設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，並且圖中的每條邊（i，j）所關聯的兩個頂點i和j分別屬於這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。

二分圖

二分覆蓋簡介

在二分圖中尋找最小覆蓋的問題為二分覆蓋（bipartite - cover）問題。二分圖是一個無向圖，它的n個頂點可二分為集合A和集合B，且同一集合中的任意兩個頂點在圖中無邊相連（即任何一條邊都是一個頂點在集合A中，另一個在集合B中）。若且唯若B中的每個頂點至少與A中一個頂點相連時，A的一個子集A'覆蓋集合B（或簡單地說，A'是一個覆蓋）。覆蓋A'的大小即為A'中的頂點數目。若且唯若A'是覆蓋B的子集中最小的時，A'為最小覆蓋。

考察如圖所示的具有1 7個頂點的二分圖，A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集A' = { 1 , 1 6 , 1 7 }是B的最小覆蓋。

17個頂點的二分圖

算法

思路分析

二分覆蓋問題是N P -複雜問題。因此可能無法找到一個快速的算法來解決它，但是可以利用貪婪算法尋找一種快速啟發式方法。一種可能是分步建立覆蓋A'，每一步選擇A中的一個頂點加入覆蓋。頂點的選擇利用貪婪準則：從A中選取能覆蓋B中還未被覆蓋的元素數目最多的頂點。

偽代碼

可以證明：1)若且唯若初始的二分圖沒有覆蓋時，算法找不到覆蓋；2)啟發式方法可能找不到二分圖的最小覆蓋。

A' =φ

w h i l e（更多的頂點可被覆蓋）

把能覆蓋未被覆蓋的頂點數目最多的頂點加入A'

i f（有些頂點未被覆蓋）失敗

e l s e（找到一個覆蓋）

C++代碼示例

首先計算出集合A和B的大小、初始化必要的雙向鍊表結構、創建三個數組、初始化圖遍歷器、並創建一個棧。然後將數組C o v和C h a n g e初始化為f a l s e，並將A中的頂點根據它們覆蓋B中頂點的數目插入到相應的雙向鍊表中。

為了構造覆蓋，首先按SizeOfB遞減至1的順序檢查雙向鍊表。當發現一個非空的表時，就將其第一個頂點v加入到覆蓋中，這種策略即為選擇具有最大New值的頂點。將所選擇的頂點加入覆蓋數組C並檢查B中所有與它鄰接的頂點。若頂點j與v鄰接且還未被覆蓋，則將C o v [ j ]置為t r u e，表示頂點j現在已被覆蓋，同時將已被覆蓋的B中的頂點數目加1。由於j是最近被覆蓋的，所有A中與j鄰接的頂點的New值減1。下一個while循環降低這些New值並將New值被降低的頂點保存在一個棧中。當所有與頂點v鄰接的頂點的Cov值更新完畢後，New值反映了A中每個頂點所能覆蓋的新的頂點數，然而A中的頂點由於New值被更新，處於錯誤的雙向鍊表中，下一個while循環則將這些頂點移到正確的表中。

構造貪婪覆蓋

bool Undirected::BipartiteCover(int L[], int C[], int& m){// 尋找一個二分圖覆蓋// L 是輸入頂點的標號, L[i] = 1 若且唯若i 在A中// C 是一個記錄覆蓋的輸出數組// 如果圖中不存在覆蓋，則返回f a l s e// 如果圖中有一個覆蓋，則返回t r u e ;// 在m中返回覆蓋的大小; 在C [ 0 : m - 1 ]中返回覆蓋int n = Ve r t i c e s ( ) ;// 外掛程式結構int SizeOfA = 0;for (int i = 1; i <= n; i++) // 確定集合A的大小if (L[i] == 1) SizeOfA++;int SizeOfB = n - SizeOfA;CreateBins(SizeOfB, n);int *New = new int [n+1]; / /頂點i覆蓋了B中N e w [ i ]個未被覆蓋的頂點bool *Change = new bool [n+1]; // Change[i]為t r u e若且唯若New[i]已改變bool *Cov = new bool [n+1]; // Cov[i] 為true 若且唯若頂點i 被覆蓋I n i t i a l i z e P o s ( ) ;LinkedStack<int> S;// 初始化for (i = 1; i <= n; i++) {Cov[i] = Change[i] = false;if (L[i] == 1) {// i 在A中New[i] = Degree(i); // i 覆蓋了這么多InsertBins(New[i], i);}}// 構造覆蓋int covered = 0, // 被覆蓋的頂點MaxBin = SizeOfB; // 可能非空的最大箱子m = 0; // C的游標while (MaxBin > 0) { // 搜尋所有箱子// 選擇一個頂點if (bin[MaxBin]) { // 箱子不空int v = bin[MaxBin]; // 第一個頂點C[m++] = v; // 把v 加入覆蓋// 標記新覆蓋的頂點int j = Begin(v), k;while (j) {if (!Cov[j]) {// j尚未被覆蓋Cov[j] = true;c o v e r e d + + ;// 修改N e wk = Begin(j);while (k) {New[k]--; // j 不計入在內if (!Change[k]) {S.Add(k); // 僅入棧一次Change[k] = true;}k = NextVe r t e x ( j ) ; }}j = NextVe r t e x ( v ) ; }// 更新箱子while (!S.IsEmpty()) {S . D e l e t e ( k ) ;Change[k] = false;MoveBins(SizeOfB, New[k], k);}}else MaxBin--;}D e a c t i v a t e P o s ( ) ;D e s t r o y B i n s ( ) ;delete [] New;delete [] Change;delete [] Cov;return (covered == SizeOfB);}