[離散] 有關maximum matching 與edge cover

看板Math作者 (4浩)時間15年前 (2011/01/01 22:40), 編輯推噓1(1推 0噓 2→)
留言3則, 2人參與, 最新討論串1/2 (看更多)
最近在學離散的網路流量這部份 想請問找出了最大配對maximum matching後 要怎麼選取minimum edge cover呢 課本說它是等價的 可是不知道怎麼選取它，煩請大大舉個例子說明一下，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.172.219.37
推
01/02 02:32, , 1F
我猜你說的是在 bipartite graph 上的 vertex cover?
01/02 02:32, 1F
→
01/02 02:32, , 2F
如果是這樣的話, 這是 Konig 定理.
01/02 02:32, 2F
→
01/02 13:11, , 3F
是的 可以煩請舉個例嗎
01/02 13:11, 3F
‣ 更多 leo790124 的文章
文章代碼(AID): #1D7ppwy8 (Math)
‣ 更多 leo790124 的文章
文章代碼(AID): #1D7ppwy8 (Math)