我似乎找到了一种算法，但无法理解它，我想知道你们中是否有人知道该算法的通用大纲。
这是我在第 2 页找到的算法的链接
问问题
14333 次
2 回答
11
算法很简单：
- 找到不匹配的顶点，将其标记为不包含在最小顶点覆盖中。
- 将此顶点的所有匹配邻居标记为包含在最小顶点覆盖中。
- 将上一步中顶点的所有配合视为不匹配的顶点并重复步骤 1。
- 如果递归结束，则从步骤 1 开始重复（即图的多个连接组件的情况）。
- 如果没有不匹配的顶点，请取出所有剩余的对并以您喜欢的方式标记它们（请记住，一对中的一个顶点必须包含在最小顶点覆盖中，而另一个必须不包括在内）。
于 2015-11-01T21:56:51.350 回答
-4
首先你应该知道二分图，两组顶点和边，好的，你现在知道了。
那么你需要从这两组中选择一些顶点来覆盖所有的边。只要选择一个顶点，链接到它的所有边都会被覆盖。现在您的任务是选择最少数量的顶点，以覆盖所有边。
原则意味着，您需要的最小数量等于最大匹配对的数量。
于 2012-09-16T19:01:40.000 回答