二分图是一个无向图,它的n个顶点可二分为集合a和集合b,

《二分图是一个无向图,它的n个顶点可二分为集合a和集合b,》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二分图是一个无向图，它的n个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A'覆盖集合B（或简单地说，A'是一个覆盖）。覆盖A'的大小即为A'中的顶点数目。当且仅当A'是覆盖B的子集中最小的时，A'为最小覆盖。　　例1-10考察如图1-6所示的具有17个顶点的二分图，A={1,2,3,16,17}和B={4,5,6,7,8,9,10,11,12,13,14,1

2、5}，子集A'={1,16,17}是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（bipartite-cover）问题。在例12-3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。　　二分覆盖问题类似于集合覆盖（set-cover）问题。在集合覆盖问题中给出了k个集合S={S1,S2,.,Sk}，每个集合Si中的元素均是全集U中的成员。当且仅当èiS'Si=U时，S的子集S'覆盖U，S'中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合

3、时，称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，13}，S2={4，5，6，8}，S3={8，10，12，14，15}，S4={5，6，8，12，14，15}，S5={4，9，10，11}。S'={S1，S4，S5}是一个大小为3的覆盖，没有

4、更小的覆盖，S'即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，16和17分别表示集合S1，S2，S3，S4和S5，顶点j表示集合中的元素j，4≤j≤15。　　集合覆盖问题为NP-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是NP-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A'，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的

5、顶点。　　例1-12考察图1-6所示的二分图，初始化A'=且B中没有顶点被覆盖，顶点1和16均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和17分别覆盖四个。因此，在第一步往A'中加入顶点1或16，若加入顶点16，则它覆盖的顶点为{5,6,8,12,14,15}，未覆盖的顶点为{4,7,9,10,11,13}。顶点1能覆盖其中四个顶点（{4,7,9,13}），顶点2覆盖一个({4})，顶点3覆盖一个（{10}），顶点16覆盖零个，顶点17覆盖四个{4,9,10,11}。下一步可选择1或17加入A'

6、。若选择顶点1，则顶点{10,11}仍然未被覆盖，此时顶点1，2，16不覆盖其中任意一个，顶点3覆盖一个，顶点17覆盖两个，因此选择顶点17，至此所有顶点已被覆盖，得A'={16,1,17}。图1-7给出了贪婪覆盖启发式方法的伪代码，可以证明：1)当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2)启发式方法可能找不到二分图的最小覆盖。　　1.数据结构的选取及复杂性分析　　为实现图13-7的算法，需要选择A'的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A'仅使用加法运

7、算，则可用一维整型数组C来描述A'，用m来记录A'中元素个数。将A'中的成员记录在C[0:m-1]中。对于A中顶点i，令Newi为i所能覆盖的B中未覆盖的顶点数目。逐步选择Newi值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各Newi值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j为这样的一个顶点，则A中所有覆盖j的顶点的Newi值均减1。　　例1-13考察图1-6，初始时(New1,New2,New3,New16,New17)=(6,4,5,6,4)。假设在例1-12

8、中，第一步选择顶点16，为更新Newi的值检查B中所有最近被覆盖的顶点，这些顶点为5,6,8,12,14和15。当检查顶点5时，将顶点2和16的Newi值分别减1，因为顶点5不再是被顶点2和16覆盖的未覆盖节点；当检查顶点6时，顶点1,2,和16的相应值分别减1；同样，检查顶点8时，1，2，3和16的值分别减1；当检查完所有最近被覆盖的顶点，得到的Newi值为（4，1，0，4）。下一步选择顶点1，最新被覆盖的顶点为4，7，9和13；检查顶点4时，New1,New2,和New17的值