算法合集之淺析二分圖匹配在信息學(xué)競賽中的應(yīng)用(編輯修改稿)
2024-11-12 20:32 本頁面
【文章內(nèi)容簡介】 且 為 實(shí) 點(diǎn) 且 為 實(shí) 點(diǎn) 顯然， SM即是滿足樹 T是圖 G0的一棵最小生成樹的最小代價(jià)。那么問題就轉(zhuǎn)化為求圖 G的最大權(quán)完備匹配 M，即可用 KM算法求解 。 算法分析 復(fù)雜度分析 我們來分析一下該算法的時間復(fù)雜度。 ?預(yù)處理的時間復(fù)雜度為 O(|E|) ?KM算法的時間復(fù)雜度為 O(|V||E|) 由于圖 G是二分完全圖。 |V|=2max{n – 1, m – n + 1}=O(m) |E|=|V|2=O(m2) 所以算法總時間復(fù)雜度為 O(m3) 。 用 KM算法解此題在構(gòu)圖時添加了許多虛結(jié)點(diǎn)和虛邊，但其并沒有太多實(shí)際意義。 思考 那么，算法中是否存在大量冗余呢？還有沒有優(yōu)化的余地呢？ 下面就介紹一種更優(yōu)秀的 算法！ 前面用 KM算法解此題時構(gòu)造了一個邊上帶有權(quán)值的二分圖。其實(shí)不妨換一種思路，將權(quán)值由 邊 轉(zhuǎn)移到 點(diǎn) 上，或許會有新的發(fā)現(xiàn)。 匹配算法分析 答案是肯定的，如果不添加這些虛結(jié)點(diǎn)和虛邊，可以得到更好的算法。 1 1 2 2 3 3 4 4 5 6 7 同樣建立兩個互補(bǔ)的結(jié)點(diǎn)集合 X39。， Y39。 構(gòu)造二分圖 G39。 X39。 Y39。 X39。結(jié)點(diǎn) i表示樹邊 ai(ai∈ T)， Y39。結(jié)點(diǎn) j表示任意邊aj(aj∈ V0)。 1 1 2 2 3 3 4 4 5 6 7 如果圖 G0中， aj 可替換 ai，且 Ci－ Cj0,則在 X39。結(jié)點(diǎn) i和 Y39。結(jié)點(diǎn) j之間添加邊 (i,j)。 構(gòu)造二分圖 G39。 X39。 Y39。 1 1 2 2 3 3 4 4 5 6 7 在 X39。結(jié)點(diǎn) i和 Y39。結(jié)點(diǎn) i之間添加邊 (i,i)。 構(gòu)造二分圖 G39。 X39。 Y39。 1 1 2 2 3 3 4 4 5 6 7 給每個 Y39。結(jié)點(diǎn) i一個權(quán)值 Ci。如果點(diǎn) i被匹配則得到權(quán)值 Ci， 否則得到權(quán)值 0。 C3 C2 C1 C4 C5 C6 C7 構(gòu)造二分圖 G39。 X39。 Y39。 算法分析 iiaTC??? ?設(shè)[引理 ]對于圖 G中的任何一個完備匹配 M，都可以在圖 G39。中找到一個唯一的完備匹配 M39。與其對應(yīng)，且 SM = μ－ SM39。 對于圖 G39。中的任何一個完備匹配 M39。，同樣可以在圖 G中找到一組以 M為代表的匹配與其對應(yīng)，且 SM= μ－
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1