图算法，近似算法

Question

在去除随机图的dfs树的叶子节点后，假设剩下的边数为|S|，我们能否证明该图的匹配将是|S|/2？

- justin waugh

---

你说的 |S|/2 是指向下取整还是向上取整？ - kunigami

1. 在删除DFS树的叶子节点或原始随机图后，|S|是边的数量吗？
2. 你所说的匹配是指最大匹配还是任意匹配都可以？

- kunigami

@kunigami 1) |S|是在DFS树的叶子节点被移除后计算的。2) 任何最大匹配都可以，因此任何匹配都可以。为了更正我的问题，应该是向上取整(|S|/2)，而不仅仅是|S|/2。 - justin waugh

好的，现在我明白了。所以我认为Keith Randall回答了你的问题 :) - kunigami

Answer 1

以下是证明：

定理：假设 T 是一棵有 i 个叶子的树。那么在 T 中存在一个大小为 (|T|-i)/2 的匹配。

证明：采用归纳法。如果 T 是一棵有 i 个叶子的树，那么让 T' 成为从 T 中删除所有叶子后得到的树。 T' 有 j <= i 个叶子。同样地，让 T'' 成为从 T' 中删除所有叶子后得到的树。 T'' 有 k <= j 个叶子。

对 T'' 应用归纳法中的定理，因此在 T'' 中存在大小为 (|T''|-k)/2 = (|T|-i-j-k)/2 的匹配。边集合 T-T' 至少包含 j 条边，这些边不与 T'' 或彼此相接（选择与 T' 中每个叶子相接的边），因此将这些边添加到 T 中以形成大小为 (|T|-i+j-k)/2 的匹配。由于 j >= k，这至少是 (|T|-i)/2 条边。证毕。

我忽略了 /2 的取整问题，但如果您包括它们，我认为证明仍然有效。

- Keith Randall