作者suhorng (飞扬)
站内Prob_Solve
标题Re: [问题] Konig
时间Wed Aug 19 07:45:20 2009
※ 引述《pokia (幻影成风)》之铭言：
: 作者: pokia (幻影成风) 看板: C_and_CPP
: 标题: [问题] Konig
: 时间: Fri Aug 14 12:25:45 2009
: Konig说 对bipartite graph而言
: matching的maximum size 就是 vertex cover的minimum size
偷一下黑书上的证明(反过来)：
二分图的最少点数(覆盖数)就是最大匹配数M。
pf. (1) M个匹配是足够的。因为如果有边 e 不被覆盖，那我们可以把 e
加入後得到一个更大的匹配。
(2) M个是必须的。仅考虑形成最大匹配的这 M 条边，由於他们两两
无公共点，因此最少需要 M 个点才能全部覆盖。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.137.68.216