查找具有非常重要顶点的二分图顶点覆盖
我知道我可以通过首先找到最大匹配然后使用 Konig's Theorem 将这个匹配变成同阶的顶点覆盖。
然而，获得的结果只是可能的许多有效顶点覆盖之一。在下图中，{A,B}、{C,D} 和 {B,C} 都是有效封面。应用 Konig 方法产生覆盖层 {A,B}。
(A)=====(C)
/
/
/
(B)=====(D)
您如何检查是否存在包含给定重要顶点（例如顶点 D）的最小顶点覆盖？
我的第一个猜测是翻转图形并找到另一个最小顶点覆盖。在上述情况下，这将产生 {C,D}。如果两个解都不包含重要顶点，则它不是任何最小覆盖的一部分。然而，我还没有思考得足够深入，无法真正向自己证明这一点。
I know that I can find the minimum vertex cover of a bipartite graph by first finding the maximum matching and then using Konig's Theorem to turn this matching into a vertex cover of the same order.
However, the result obtained is only one of what could be many valid vertex covers. In the following graph, {A,B}, {C,D}, and {B,C} are all valid covers. Applying the Konig method yields the cover {A,B}.
(A)=====(C)
/
/
/
(B)=====(D)
How would you check for the existence of a minimum vertex cover that includes a given important vertex, say, vertex D?
My first guess is to flip the graph and find another minimum vertex cover. In the above case, this would yield {C,D}. If neither solution contains the important vertex, it's not part of any minimum cover. However, I haven't thought deeply enough to really prove this to myself.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我建议使用以下方法
If $|C' + V| = |C|$ 然后报告最小顶点覆盖，否则报告给定顶点不存在最小顶点覆盖。
我猜你的答案是一样的，证明也是同样的道理。
新的顶点覆盖不能更小，因为它会违反 $C$ 是最小顶点覆盖之一的条件。
$C'$ 也是覆盖图表其余部分的最小覆盖范围。
如果至少存在一个包括顶点 $V$ 的最小顶点覆盖，那么该集合中的其余顶点将覆盖除与 $V$ 相邻的顶点之外的所有顶点，但这意味着 $|C'|$ 是不大于 $|C|-1$，因此如果不这样做将意味着不存在最小顶点覆盖（包括 VIP 边）。
I would suggest the following method
If $|C' + V| = |C|$ then report the minimum vertex cover else report no minimum vertex cover exists with the given vertex.
I guess you have the same answer the proof is also along the same lines.
The new vertex cover cannot be smaller since it would violate the condition that $C$ was one of the minimum vertex cover.
Also $C'$ is the minimum cover covering the rest of the graph.
If there is atleast one minimum vertex cover including the vertex $V$ then the rest of the vertices in that set would cover all the vertices except the ones adjacent to $V$, but then it would mean that $|C'|$ is not larger than $|C|-1$ hence a faliure to do this would imply no minimum vertex cover exists including the VIP edge.
使用匈牙利算法计算初始匹配，为以该顶点结尾的所有边赋予较低的权重。
Compute the initial matching using the Hungarian algorithm, giving a lower weight to all the edges ending in that vertex.