如何在此图上运行二分匹配和最小顶点覆盖算法？

Question

嗨，所以我应该运行二分匹配和最小值。在此图上使用 Ford-Fulkerson 和 DFS/BFS 的顶点覆盖算法（s = 0 和 t = 6），“打破平局以支持较小的顶点”（基本上，如果您有两条有效路径，请选择一条经过的路径）较小的顶点）。

二分匹配

我添加了 s 并添加了连接到 1、3 和 5 的边，以及连接到 2 和 4 的边 t，然后用容量 1 初始化每条边。我选择的第一个增广路径是 0->1- >2->t 并用 1 填充。我选择的下一个增广路径是 0->3->2->5->4->6 并用 1 填充这些路径。此后不再有增广路径，因此最大流量为 2。接下来，我选择原始图中流量为 1 的边作为答案，即 (1,2), (2, 3)、(2,5) 和 (5,4)。然而，这是不正确的。正确答案是（1,2）、（2,5）。我知道如何得到它 - 第一个增广路径是 0->1->2->6，第二个增广路径是 0->5->4->6。但是，选择这些顶点不是“打破关系以支持较小的顶点”，这正是我被要求做的吗？我有点困惑，所以如果有人能澄清我做错了什么，我真的很感激。

最小顶点覆盖

对于顶点覆盖，我有同样的问题，因为我基本上使用了相同的增广路径。我得到的 s-t 切割是通过 (2,5) 和 (4,5) （因为它与最大流量 2 匹配，因为它们的容量均为 1），但这是否意味着 S = {0,1, 2,3,4,5}，因为我们需要返回的是 (L\S) U (R ∩ S)，我认为是 {2,4}。然而，这也是不正确的 - 实际答案是 {2,5}。

抱歉，如果这是一个非常简单的问题，我做了其他问题并做对了，并认为我理解如何做这些问题，但我想不是。如果有人可以帮助我，我将非常感激！谢谢！

Answer 1

用于解决顶点覆盖问题的算法如下：

LOOP V over vertices
  IF V is a leaf node ( degree 1 )
     Add V to to cover set
LOOP E over edges
  Set V1, and v2 to the vertices connected by E
  IF V1 and V2 are NOT in set
      Set v to V1
      IF V2 degree > V1 degree
           Set v to V2
      Add v to cover set.