作者pokia (幻影成风)
看板Prob_Solve
标题[问题] Konig
时间Fri Aug 14 21:43:59 2009
※ [本文转录自 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会比较快?
谢谢!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.169.196.157
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.129.124.61
1F：推 raincole:matrix67对那个证明有非常清楚的解释 08/14 22:07
2F：→ pokia:感谢!!大概懂了! 08/15 22:08