算法合集之淺析二分圖匹配在信息學(xué)競(jìng)賽中的應(yīng)用-在線瀏覽
2024-12-03 20:32本頁面
【正文】 點(diǎn) i為 li， Y結(jié)點(diǎn) j為 rj。 1 2 3 4 5 6 7 我們來構(gòu)造二分圖 G 建立兩個(gè)互補(bǔ)的結(jié)點(diǎn)集合 X， Y。 X結(jié)點(diǎn) i表示圖 G0中 樹邊 ai(ai∈ T)。 構(gòu)造二分圖 G 如果圖 G0中， aj 可替換 ai，且 Ci－ Cj0,則在 X結(jié)點(diǎn) i和Y結(jié)點(diǎn) j之間添加邊 (i,j), 邊權(quán) Wi,j=Ci－ Cj。 1 2 3 4 5 6 7 在結(jié)點(diǎn)數(shù)少的一側(cè)添加虛結(jié)點(diǎn)，使得 X結(jié)點(diǎn)和 Y結(jié)點(diǎn)的數(shù)目相等。 1 2 3 4 5 6 7 8 構(gòu)造二分圖 G X Y 算法分析 ? ?, ( , )i j i jl r W i j X? ? ?? ?, ( , )i j i jl r W i j M? ? ?,( , )M i j i ji j M i X j YS W l r? ? ?? ? ?? ? ?設(shè)完備匹配 X的所有匹配邊的權(quán)值和為 SX， 則 對(duì)于圖 G的任意一個(gè)完備匹配 X，都有 設(shè) M為圖 G的最大權(quán)匹配，顯然 M也是完備匹配，則滿足 顯然，此時(shí)的可行頂標(biāo)之和取到最小值。同理對(duì)于虛結(jié)點(diǎn) Yj， rj = 0。那么問題就轉(zhuǎn)化為求圖 G的最大權(quán)完備匹配 M，即可用 KM算法求解 。 ?預(yù)處理的時(shí)間復(fù)雜度為 O(|E|) ?KM算法的時(shí)間復(fù)雜度為 O(|V||E|) 由于圖 G是二分完全圖。 用 KM算法解此題在構(gòu)圖時(shí)添加了許多虛結(jié)點(diǎn)和虛邊，但其并沒有太多實(shí)際意義。其實(shí)不妨換一種思路，將權(quán)值由 邊 轉(zhuǎn)移到 點(diǎn) 上，或許會(huì)有新的發(fā)現(xiàn)。 1 1 2 2 3 3 4 4 5 6 7 同樣建立兩個(gè)互補(bǔ)的結(jié)點(diǎn)集合 X39。 構(gòu)造二分圖 G39。 Y39。結(jié)點(diǎn) i表示樹邊 ai(ai∈ T)， Y39。 1 1 2 2 3 3 4 4 5 6 7 如果圖 G0中， aj 可替換 ai，且 Ci－ Cj0,則在 X39。結(jié)點(diǎn) j之間添加邊 (i,j)。 X39。 1 1 2 2 3 3 4 4 5 6 7 在 X39。結(jié)點(diǎn) i之間添加邊 (i,i)。 X39。 1 1 2 2 3 3 4 4 5 6 7 給每個(gè) Y39。如果點(diǎn) i被匹配則得到權(quán)值 Ci， 否則得到權(quán)值 0。 X39。 算法分析 iiaTC??? ?設(shè)[引理 ]對(duì)于圖 G中的任何一個(gè)完備匹配 M，都可以在圖 G39。與其對(duì)應(yīng)，且 SM = μ－ SM39。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1