作者hcsoso (索索)
看板Math
标题Re: [离散] 有关maximum matching 与edge cover
时间Sun Jan 2 17:19:27 2011
假如没有记错的话, 应该是这样找:
如果是个 perfect matching, 那就选少的那一边的点全部当作 vertex cover,
可以看出这样一定会盖住所有边.
如果至少有一个点没有被 match 到, 从他开始把他所有邻居都加进 vertex cover,
然後拿掉这个点以及他所有邻居, 重复以上的步骤.
这样每个在 matching 里的边一定正好只有一个端点在 vertex cover 里, (试证明之!)
因此会是一个大小跟 maximal matching 一样的 vertex cover.
用个图检查一下吧.
http://en.wikipedia.org/wiki/File:Koenigs-theorem-graph.svg
--
Chicken's Finite Playground
http://finiteplayground.wordpress.com/
Algorithms, Computational Complexity, Graph Theory, and Anything... FINITE!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.133.15.16