二分圖
二分圖二分圖又稱作二部圖，是圖論中的一種特殊模型。設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'為最小覆蓋。
17個頂點的二分圖考察如圖所示的具有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 -複雜問題。因此可能無法找到一個快速的算法來解決它，但是可以利用貪婪算法尋找一種快速啟發式方法。一種可能是分步建立覆蓋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循環則將這些頂點移到正確的表中。
構造貪婪覆蓋
