找到最低点覆盖的二分图中给出的最大匹配 [英] Find minimum vertex Cover for bipartite graph given the maximum matching

问题描述

我似乎找到了一种算法，但我有麻烦理解它，我想知道如果你们知道算法的一般轮廓。

I seem to have found an algorithm but am having trouble understanding it, I was wondering if any of you knew the generic outline of the algorithm.

下面是链接的算法，我发现第2页

Here is the link to the algorithm I found on page 2

http://www.cse.iitb.ac.in /~sundar/cs435​​/lecture23.pdf

推荐答案

算法就是这么简单：

1. 找到无与伦比的顶点，将其标记为不包括在最低顶点覆盖。
2. 标记此顶点作为包含在最低点覆盖所有匹配的邻居。
3. 在治疗顶点的所有队友从previous一步无与伦比的顶点，然后重复步骤1。
4. 如果递归结束，从第1步重复（即案件的图的几个连接组件）。
5. 如果没有无与伦比的顶点，采取所有剩余的对，它们标记任何你喜欢的方式（请记住，在对一个顶点有 被包括在最小的顶点盖，另一个必须是不 包括在内）。

1. Find unmatched vertex, mark it as not included in minimum vertex cover.
2. Mark all matched neighbours of this vertex as included in minimum vertex cover.
3. Treat all mates of vertexes from previous step as unmatched vertexes and repeat step 1.
4. If recursion ended, repeat from step 1 (that is case of several connected components of graph).
5. If there is no unmatched vertexes, take all remaining pairs and mark them any way you like (remember that one vertex in pair has to be included in minimum vertex cover, and other one has to be not included).

P.S。我知道这是necroposting。

P.S. I know this is necroposting.

这篇关于找到最低点覆盖的二分图中给出的最大匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！