分类：
2008-10-15 16:39:35
二分图是一个无向图，它的n 个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A\' 覆盖集合B（或简单地说，A\' 是一个覆盖）。覆盖A\' 的大小即为A\' 中的顶点数目。当且仅当A\' 是覆盖B的子集中最小的时，A\' 为最小覆盖。
例1-10 考察如图1 - 6所示的具有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的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（ b i p a r t i t e - c o v e r）问题。在例1 2 - 3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。
二分覆盖问题类似于集合覆盖（ s e t - c o v e r）问题。在集合覆盖问题中给出了k 个集合S= {S1 ， S2 ，。， Sk }，每个集合Si 中的元素均是全集U中的成员。当且仅当èi S\'Si =U时，S的子集S\' 覆盖U，S \'中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S\' 为最小覆盖。可以将集合覆盖问题转化为二分覆盖问题（反之亦然），即用A的顶点来表示S1 ， .， Sk ，B中的顶点代表U中的元素。当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。
例1 - 11 令S= {S1，。 . .，S5 }， U= { 4，5，。 . .，15}， S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }.S \' = {S1，S4，S5 }是一个大小为3的覆盖，没有更小的覆盖， S\' 即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，1 6和1 7分别表示集合S1，S2，S3，S4 和S5，顶点j 表示集合中的元素j，4≤j≤1 5。
集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A\' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。
例1-12 考察图1 - 6所示的二分图，初始化A\' = 且B中没有顶点被覆盖，顶点1和1 6均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和1 7分别覆盖四个。因此，在第一步往A\' 中加入顶点1或1 6，若加入顶点1 6，则它覆盖的顶点为{ 5 ， 6 ， 8 ， 1 2 ， 1 4 ， 1 5 }，未覆盖的顶点为{ 4 ， 7 ， 9 ， 1 0 ， 11 ， 1 3 }.顶点1能覆盖其中四个顶点（ { 4 ， 7 ， 9 ， 1 3 }），顶点2 覆盖一个（ { 4 } ），顶点3覆盖一个（{ 1 0 }），顶点1 6覆盖零个，顶点1 7覆盖四个{ 4 ， 9 ， 1 0 ， 11 }。下一步可选择1或1 7加入A\' .若选择顶点1，则顶点{ 1 0 ， 11} 仍然未被覆盖，此时顶点1，2，1 6不覆盖其中任意一个，顶点3覆盖一个，顶点1 7覆盖两个，因此选择顶点1 7，至此所有顶点已被覆盖，得A\' = { 1 6 ， 1 ， 1 7 }。
图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明：
1） 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；
2） 启发式方法可能找不到二分图的最小覆盖。
数据结构的选取及复杂性分析
为实现图13 - 7的算法，需要选择A\' 的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A\' 仅使用加法运算，则可用一维整型数组C来描述A \'，用m 来记录A\' 中元素个数。将A\' 中的成员记录在C[ 0 ：m-1] 中。对于A中顶点i，令N e wi 为i 所能覆盖的B中未覆盖的顶点数目。逐步选择N e wi 值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各N e wi 值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j 为这样的一个顶点，则A中所有覆盖j 的顶点的N e wi 值均减1。
[1]
