1

我已经阅读了这两个问题：link1 link2

还有这个维基百科

但我不明白如何解决最大匹配问题来解决最小路径覆盖。我知道解决方案是 nm，其中 n 是 G 中的顶点数，m 是最大匹配，但我找不到原因

4

2 回答 2

2

这是对这个事实的直观解释（它不是严格的证明）：让我们看一下路径覆盖中的每条路径。除了路径中的第一个顶点外，每个顶点都有一个唯一的前驱。此外，每个顶点都有一个后继节点（每条路径中的最后一个除外）。这就是为什么我们可以说每个顶点都与其前身相匹配。如果一个顶点不匹配任何东西，它就是某个路径中的第一个顶点。这就是为什么路径的数量等于不匹配的顶点的数量（每条路径只有一个第一个顶点）。不匹配的顶点数显然等于总的顶点数减去匹配的顶点数。这就是我们得到n - m公式的方式。不可能得到比最大匹配大小更少的路径（否则n - m1 < n - m=> m1 > m=>m不是最大值）。同时，我们可以n - m明确地构造一个带有路径的解决方案。

于 2014-12-18T16:10:32.187 回答
0
  • 左边有 n 个节点，右边有 m 个节点。
  • 匹配后计算 maxFlow f - 最大匹配数。
  • 左侧的 f 个节点和右侧的 f 个节点已经在最小边缘覆盖中。
  • 左边有 nf 个不匹配的节点，右边有 mf 个这样的节点。
  • 这些节点还没有在最小覆盖范围内，因为最大匹配不包括它们。
  • 这些节点中的每一个都可以连接到最小边缘覆盖。所以它增加了 (nf)+(mf) 边。
  • 所以总最小覆盖是 f+(nf)+(mf)=n+mf

这是一个最小边缘覆盖问题：https ://code.google.com/codejam/contest/11254486/dashboard#s=p2&a=2

于 2017-04-10T18:24:57.533 回答