推 raincole:matrix67對那個證明有非常清楚的解釋 08/14 22:07
→ pokia:感謝!!大概懂了! 08/15 22:08
※ [本文轉錄自 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