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