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 掩盖了下限/上限问题，但我怀疑如果你包括它们，证明仍然有效。