图算法、近似算法
删除随机图的dfs树的叶子后，假设剩下的边数为|S|，我们能否证明该图的匹配将为|S|/2？
After removing the leaves of the dfs tree of a random graph , suppose the number of edges left is |S|, can we prove that the matching for that graph will be |S|/2?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一个证明。
定理：设
T为任何具有i叶子的树。T中有一个(|T|-i)/2匹配。证明：通过归纳法。如果
T是一棵有i个叶子的树，则令T'为从TT.T'有j <= i叶子。同样，让T''为从T'中删除所有叶子后生成的树。T''有k <= j叶子。通过归纳法将定理应用于
T''，因此存在大小匹配(|T''|-k)/2 = (|T|-ijk)/2T''中的代码>。边集TT'至少包含j条边，这些边不与T''中的任何边相关，也不与彼此相关（选择一个）关联于T'中的每个叶子），因此添加这些边以在T中进行大小为(|T|-i+jk)/2< 的匹配/代码>。由于j >= k，这至少是(|T|-i)/2边。量子ED。我已经掩盖了 /2 的地板/天花板问题，但我怀疑如果将它们包括在内，证明仍然有效。
Here's a proof.
Theorem: Let
Tbe any tree withileaves. There is a(|T|-i)/2matching inT.Proof: by induction. If
Tis a tree withileaves, letT'be the tree that results when removing all the leaves fromT.T'hasj <= ileaves. Similarly, letT''be the tree that results when removing all the leaves fromT'.T''hask <= jleaves.Apply the theorem by induction to
T'', so there exists a matching of size(|T''|-k)/2 = (|T|-i-j-k)/2inT''. The set of edgesT-T'contains at leastjedges that are not incident to any edge inT''or to each other (pick one incident to each leaf inT'), so add those edges to make a matching inTof size(|T|-i+j-k)/2. Sincej >= k, this is at least(|T|-i)/2edges. QED.I've glossed over the floor/ceiling issues with the /2, but I suspect the proof would still work if you included them.