※ 引述《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