假如沒有記錯的話, 應該是這樣找:
如果是個 perfect matching, 那就選少的那一邊的點全部當作 vertex cover,
可以看出這樣一定會蓋住所有邊.
如果至少有一個點沒有被 match 到, 從他開始把他所有鄰居都加進 vertex cover,
然後拿掉這個點以及他所有鄰居, 重複以上的步驟.
這樣每個在 matching 裡的邊一定正好只有一個端點在 vertex cover 裡, (試證明之!)
因此會是一個大小跟 maximal matching 一樣的 vertex cover.
用個圖檢查一下吧.
http://en.wikipedia.org/wiki/File:Koenigs-theorem-graph.svg
--
Chicken's Finite Playground http://finiteplayground.wordpress.com/
Algorithms, Computational Complexity, Graph Theory, and Anything... FINITE!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.15.16