算法合集之淺析二分圖匹配在信息學(xué)競(jìng)賽中的應(yīng)用-展示頁(yè)
2024-10-25 20:32本頁(yè)面
【正文】 值更小的生成樹。 初步分析 如右圖， u∈ T， t1， t2， t3∈ T，且 t1， t2， t3連接了 u的兩個(gè)端點(diǎn)，所以Pu={t1， t2， t3}。修改的代價(jià)定義為： 4 1 5 2 3 4 6 2 2 3 5 7 4 1 5 2 3 4 4 2 4 3 3 4 f=|64|+|22|+|53|+|74|+|33|+|24|+|44|=9 初步分析 ? 根據(jù)與樹 T的關(guān)系 ,我們可以把圖 G0中的邊分成樹邊與非樹邊兩類。設(shè) n= |V0|， m= |E0|， E0中前 n1條邊構(gòu)成一棵生成樹T。 [例題 ] Roads eeeEf C D????請(qǐng)求出修改的最小代價(jià)。淺析二分圖匹配 在信息學(xué)競(jìng)賽中的應(yīng)用 長(zhǎng)郡中學(xué) 王俊 引言 二分圖匹配是一類經(jīng)典的圖論算法，在近年來(lái)信息學(xué)競(jìng)賽中有廣泛的應(yīng)用。 二分圖和匹配的基礎(chǔ)知識(shí)已經(jīng)在前輩的集訓(xùn)隊(duì)論文中有過(guò)介紹，本文主要通過(guò)一道例題研究其應(yīng)用。 給定一個(gè)無(wú)向圖 G0=（ V0， E0， C）， V0為頂點(diǎn)集合 ,E0為邊集合（無(wú)重邊）， C為邊權(quán)（非負(fù)整數(shù)）。請(qǐng)將邊權(quán)進(jìn)行如下修改，即對(duì)于 e∈ E，把 Ce修改成 De（ De也為非負(fù)整數(shù)），使得樹 T成為圖 G的一棵最小生成樹。 ? 設(shè) Pe表示邊 e的兩個(gè)端點(diǎn)之間的樹的路徑中邊的集合。 / ? 那么用非樹邊 u代替樹邊 t1，t2， t3中任意一條都可以得到一棵新的生成樹。 ? 那么要使原生成樹 T是一棵最小生成樹，必須滿足條件： Dt1≤ Du ； Dt2≤ Du ； Dt3≤ Du u t1 t2 t3 初步分析 如果邊 v， u(u可替換 v)，則必須滿足 Dv≤ Du ， 否則用 u替換 v可得到一棵權(quán)值更小的生成樹 Tv+u 。 初步分析 不等式 Dv≤Du中 v總為樹邊 ， 而 u總為非樹邊。 設(shè)邊權(quán)的修改量為 Δ，即 Δe=|De－ Ce| / 當(dāng) e∈ T， Δe=De－ Ce, 即 De=Ce＋ Δe 當(dāng) e∈ T， Δe=Ce－ De，即 De=Ce－ Δe 初步分析 那問(wèn)題就是求出所有的 Δ使其滿足以上不等式且： vuDD?v v u uCC? ? ? ? ?v u v uCC? ? ? ? ?1miif????最小。 KM算法中 ， 首先給二分圖的每個(gè)頂點(diǎn)都設(shè)一個(gè)可行頂標(biāo) ， X結(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1