Re: [問題] Konig
看板Prob_Solve (計算數學 Problem Solving)作者suhorng (飛揚)時間15年前 (2009/08/19 07:45)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/3 (看更多)
※ 引述《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
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
