algorithm - 图算法，近似算法

Question

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

Answer 1

这是一个证明。

定理：设T任何一棵有i叶子的树。中有一个(|T|-i)/2匹配项T。

证明：通过归纳。如果T是一棵有i叶子T'的树，设 是从 中移除所有叶子时产生的树T。 T'有j <= i叶子。类似地，让T''成为从 中删除所有叶子时产生的树T'。 T''有k <= j叶子。

通过归纳应用该定理到T''，因此存在 中的大小(|T''|-k)/2 = (|T|-i-j-k)/2匹配T''。边集T-T'至少包含j不与任何边T''或彼此相关的边（选择一个与 中的每个叶的事件T'），因此添加这些边以进行T大小为 的匹配(|T|-i+j-k)/2。因为j >= k，这至少是(|T|-i)/2边缘。QED。

我已经用 /2 掩盖了地板/天花板的问题，但我怀疑如果你把它们包括在内，证明仍然有效。