PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Konig

看板Prob_Solve (計算數學 Problem Solving)作者cyhe (posimpible)時間15年前 (2009/08/15 15:52)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/3 (看更多)

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