看板 [ Prob_Solve ]
討論串[問題] Konig
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] Konig
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者pokia (幻影成風)時間15年前 (2009/08/14 21:44), 編輯資訊
2
0
0
內容預覽:
※ [本文轉錄自 C_and_CPP 看板]. 作者: pokia (幻影成風) 看板: C_and_CPP. 標題: [問題] Konig. 時間: Fri Aug 14 12:25:45 2009. Konig說 對bipartite graph而言. matching的maximum size
(還有118個字)
#2
Re: [問題] Konig
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者cyhe (posimpible)時間15年前 (2009/08/15 15:52), 編輯資訊
0
0
0
內容預覽:
令 M = 任意一個 Maximal Matching (注意:Maximal不一定是Maximum). |M| <= Minimum Vertex Cover. 令 V = Union of the two end points of each edge in M. V有兩個特性:. 1. V i
(還有321個字)
#3
Re: [問題] Konig
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者suhorng (飛揚)時間15年前 (2009/08/19 07:45), 編輯資訊
0
0
0
內容預覽:
偷一下黑書上的證明(反過來)：. 二分圖的最少點數(覆蓋數)就是最大匹配數M。. pf. (1) M個匹配是足夠的。因為如果有邊 e 不被覆蓋，那我們可以把 e. 加入後得到一個更大的匹配。. (2) M個是必須的。僅考慮形成最大匹配的這 M 條邊，由於他們兩兩. 無公共點，因此最少需要 M 個點才
首頁
上一頁
1
下一頁
尾頁