Re: [問題] Konig
※ 引述《pokia (幻影成風)》之銘言：
: ※ [本文轉錄自 C_and_CPP 看板]
: 作者: pokia (幻影成風) 看板: C_and_CPP
: 標題: [問題] Konig
: 時間: Fri Aug 14 12:25:45 2009
: Konig說 對bipartite graph而言
: matching的maximum size 就是 vertex cover的minimum size
: 這個證明有沒有人有簡單的解釋法 or 舉例？
: wiki和google出來的證明都難得讓我看不太懂...
: 如果對general graph來說 要找vertex cover set
: 做graph traversal時
: 大概怎麼pruning會比較快?
: 謝謝!!
令 M = 任意一個 Maximal Matching (注意:Maximal不一定是Maximum)
|M| <= Minimum Vertex Cover
令 V = Union of the two end points of each edge in M
V有兩個特性:
1. V is a Vertex Cover
2. |V|<= 2 * Minimum Vertex Cover
以上的 Time Complexity = O(e)
|M| = Lower Bound of Minimum Vertex Cover
|V| <= 2|M| = Upper Bound of Minimum Vertex Cover
希望這樣子可以增加你Branch and Bound的速度
題外話: Konig 寫了第一本Graph Theory的Textbook，他一輩子也到處演講介紹圖論。
由於那個年代，圖論的研究很零碎還沒有自己的一個系統，
所以沒有人重視圖論，他也受到主流數學家的輕視，但即使如此
他還是狂熱的研究及介紹圖論。
由於他的介紹，許多的匈牙利數學家對圖論產生了興趣，
也繼續在圖論上有所貢獻，奠定了部分圖論的基礎。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.104.88.125
討論串 (同標題文章)