[科普中國]-二分覆蓋

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

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

二分覆蓋簡介在二分圖中尋找最小覆蓋的問題為二分覆蓋（bipartite - cover）問題。二分圖是一個無向圖，它的n個頂點可二分為集合A和集合B，且同一集合中的任意兩個頂點在圖中無邊相連（即任何一條邊都是一個頂點在集合A中，另一個在集合B中）。當(dāng)且僅當(dāng)B中的每個頂點至少與A中一個頂點相連時，A的一個子集A'覆蓋集合B（或簡單地說，A'是一個覆蓋）。覆蓋A'的大小即為A'中的頂點數(shù)目。當(dāng)且僅當(dāng)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的最小覆蓋。

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

偽代碼可以證明：1)當(dāng)且僅當(dāng)初始的二分圖沒有覆蓋時，算法找不到覆蓋；2)啟發(fā)式方法可能找不到二分圖的最小覆蓋。

A' =φ

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

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

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

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

C++代碼示例首先計算出集合A和B的大小、初始化必要的雙向鏈表結(jié)構(gòu)、創(chuàng)建三個數(shù)組、初始化圖遍歷器、并創(chuàng)建一個棧。然后將數(shù)組C o v和C h a n g e初始化為f a l s e，并將A中的頂點根據(jù)它們覆蓋B中頂點的數(shù)目插入到相應(yīng)的雙向鏈表中。

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

構(gòu)造貪婪覆蓋

bool Undirected::BipartiteCover(int L[], int C[], int& m){// 尋找一個二分圖覆蓋// L 是輸入頂點的標(biāo)號, L[i] = 1 當(dāng)且僅當(dāng)i 在A中// C 是一個記錄覆蓋的輸出數(shù)組// 如果圖中不存在覆蓋，則返回f a l s e// 如果圖中有一個覆蓋，則返回t r u e ;// 在m中返回覆蓋的大小; 在C [ 0 : m - 1 ]中返回覆蓋int n = Ve r t i c e s ( ) ;// 插件結(jié)構(gòu)int SizeOfA = 0;for (int i = 1; i