Алгоритам максималног упаривања

Алгоритам максималног упаривања (енгл. Blossom algorithm) је алгоритам у теорији графова и користи се за конструисање максималног поклапања на графу. Алгоритам је открио Џек Едмондс 1961. године,^[1] а објавио 1965.^[2] Посматрајући неусмерени граф graph G = (V, E), алгоритам проналази одговарајуће M такво да сваки чвор у V је заједнички са најмање једном граном у M и |M| је увећано. Упаривање је замишљено као итеративно попуњавање иницијално празног упаривања дуж повећавајућег пута у графу.

Главни разлог важности овог алгоритма је да је био први доказ да се максимално упаривање може наћи у полиномијалном времену. Други разлог је што је довео до линеарног програмирања полихедралног описа одговарајућег политопа, што је даље дало алгоритам за минималну тежину подударања.^[3] Како је образложио Александар Шријвер, даљи значај долази из чињенице да је ово први политоп чији доказ интегралности „не долази само из укупне унимодуларности и његов опис је био напредак у полиедарској комбинаторици.“^[4]

Повећавајући пут

Имајући у виду G = (V, E) и одговарајуће M из G, чвор v је издвојен, ако не постоји ни једна грана у M која садржи v. Пут у G је наизменични пут, ако његове гране наизменично нису у M и јесу у M (или јесу у M и нису у M). Повећавајући пут P је наизменичан пут који почиње и завршава се у два различита издвојена чвора. Повећавајуће упаривање дуж повећавајућег пута P је операција замене M новим подударањем $M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)$ .

Можемо да докажемо да је упаривање M максимално акко нема даљег M које увећва повећавајући пут у G. Одатле следи да, или је упаривање максимално, или може бити повећано. Дакле, почев од иницијлног упаривања, можемо израчунати максимално упаривање тако што ћемо повећавати тренутно упарено са повећавајућим путем докле год можемо да нађемо тај пут, и вратимо се кад год га не нађемо. Можемо да формаллизујемо алгоритам на следећи начин:

   УЛАЗ:  Граф G, иницијално упаривање M на G
   ИЗЛАЗ: максимално упаривање M* на G
A1 function нађи_максимално_упаривање(G, M ) : M*
A2     P ← нађи_повећавајући_пут(G, M )
A3     if P је непразно then
A4          return нађи_максимално_упаривање(G, повећај M дуж P )
A5     else
A6          return M
A7     end if
A8 end function

Још нам је остало да опишемо како ефикасно можемо пронаћи повећавајући пут. Потпрограм за то користи цветове(уклањање чворова) и контраховање (уклањање гране како би се два чвора спојила у један).

Цветови и контраховање

Имајући у виду G = (V, E) и одговарајуће M из G, цвет B је циклус у G који се састоји од 2k + 1 гране од којих тачно k грана припада M и где једно од темена v циклуса (база) је такво да постоји наизменични пут једнаке дужине (стабљика) од v до издвојеног чвора w.

Дефинишемо контраховани граф G’ као граф добијен од G помоћу контраховања сваке гране из B и дефинишемо контраховано упаривање M’ као упаривање у G’ које одговара M.

Можемо показати да G’ има повећавајући пут M’ акко G има повећавајући пут M и да било који повећавајући пут M’ P’ у G’ може бити повећан до повећавајућег пута M у G тако што ће се поништити контраховање B-ом, тако да сегмент из P’ (ако постоји) обиласка v_B је замењен било којим одговарајућим сегментом обиласка B. Или детаљније:

ако P’ обилази сегмент u → v_B → w у G’, онда се овај сегмент мења сегментом u → (u’ → ... → w’ ) → w у G, где цветни чворови u’ и w’ и страна B, (u’ → ... → w’ ), од u’ до w’ су бирани тако да би се осигурало да је нови пут и даље наизменичан (u’ је издвојено по правилу $M\cap B$ , $\{w',w\}\in E\setminus M$ ).

ако P’ има крајњу тачку v_B, онда је сегмент пута u → v_B у G’ замењен сегментом u → (u’ → ... → v’ ) у G, где цветни чворови u’ и v’ и страна B, (u’ → ... → v’ ), од u’ до v’ су бирани тако да би се осигурало да је нови пут и даље наизменичан (v’ је издвојено, $\{u',u\}\in E\setminus M$ ).

Дакле, цветови могу бити контраховани и претраживање се врши у контрахованим графовима. Ово смањење је срж Едмондсовог алгоритма.

Проналажење повећавајућег пута

Потрага за повећавајућим путем користи помоћну структуру података која се састоји од шуме F чија индивидуална стабла одговарају одређеним деловима графа G. У ствари, шума F је иста која ће се користити за проналажење макималног упаривања у бипартитном графу (без потребе за смањењем цветова). У свакој интеракцији алгоритам или (1) пронађе повећавајући пут, (2) пронађе цвет и рекурзивно позива одговарајући контраховани граф, или (3) закључи да нема повећавајућег пута. Помоћна структура је изграђена од повећавајућег процеса о коме ће се расправљати у даљем тексту.

Процедура конструкције узима у обзир чворове v и гране e у G и постепено ажурира F по потреби. Ако је v у стаблу T шуме, дозволимо да корен(v) буде означен као корен од T. Ако су оба u и v у истом стаблу T у F, дозволимо да раздаљина(u,v) будео означена као дужина јединственог пута од u до v у T.

    УЛАЗ:  Граф G, упаривање M на G
    ИЗЛАЗ: повећавајући пут P у G или празна путања ако није нађена
B01 function нађи_повећавајући_пут(G, M ) : P
B02    F ← празна шума
B03    демаркирај све чворове и гране у G, означи све гране у M
B05    for each издвојени чвор v do
B06        направи singleton дрво { v } и додај дрво у F
B07    end for
B08    while постоји демаркиран чвор v у F са раздаљина(v, корен(v ) ) do
B09        while постоји демаркирана грана e = { v, w } do
B10            if w није у F then
                   // Ажурирај F.
B11                x ← чвор упарен са w у M
B12                додај гране { v, w } и { w, x } дрвету у v
B13            else
B14            if раздаљина(w, корен(w ) ) је непарна then
B15                не ради ништа
B16            else
B17            if корен(v ) ≠ корен(w ) then
                   // Пријави повећавајући пут у F  $\cup$  { e }.
B18                P ← пут (корен(v ) → ... → v ) → (w → ... → корен(w ) )
B19                return P
B20            else
                   // Контрахуј цвет у G и потражи пут у контрахованом графу.
B21                B ← цвет формиран од e и грана у путу v → w у T
B22                G’, M’ ← контраховано G и M од B
B23                P’ ← нађи_повећавајући_пут(G’, M’ )
B24                P ← повећај P’ до G
B25                return P
B26            end if
B27            означи грану e
B28        end while
B29        означи чвор v
B30    end while
B31    return празан пут
B32 end function

Примери

Наредне четири слике илуструју извршење алгоритма. Испрекидане линије су кориштене за представљање грана које тренутно нису у шуми. Прво, алгоритам обрађује гране на спољњем делу шуме које изазива ширење тренутне шуме (линије кода B10 - B12).

Даље, алгоритам детектује цвет и контрахуе граф (линије B20 - B22).

На крају, лоцира повећавајући пут P′ у контрахованом графу (линија B23) и подиже га на оригинални граф (линија B24). Треба имати на уму да је од кључног значаја способност алгоритма да контрахује цветове; алгоритам не може да нађе P директно у оригиналном графу јер само спољне гране шуме између чворова једнаке раздаљине од корена улазе у разматрање у линији кода B17 овог алгоритма.

Анализа

Шума F конструисана функцијом нађи_повећавајући_пут() је наизменична шума.

стабло T у G је наизменично стабло према M, ако
- T садржи тачно један издвојени чвор r који се зове корен стабла
- сваки чвор на непарном растојању од корена има тачно две одговарајуће гране у T, и
- све путање из r у T имају исте дужине, његове непарне гране нису у M, а његове парне јесу у M.
шума F у G је наизменична шума према M, ако
- су њене спојене компоненте наизменична стабла, и
- сваки издвојени чвор у G је корен наизменичног стабла у F.

Свака итерација петље почевши од линије B09 или додаје стаблу T у F (линија B10) или проналази повећавајући пут (линија B17) или проналази цвет (линија B21). Сада видимо да је време извршавања $O(|V|^{4})$ . Микали и Вазирани су представили алгоритам који конструише максимално упаривање у $O(|E||V|^{1/2})$ времену.

Бипартитино упаривање

Алгоритам се своди на стандардни алгоритам упаривања у бипартитним графовима када је G бипартитно. Како нема непарних циклуса у G у том случају цветови неће бити нађени и због тога могу бити уклоњене линије B21 - B29 овог алгоритма.

Тежинско подударање

Проблем упаривања може бити генерализован додељивањем тежина гранама у G и тражећи M које ће сачињавати максимално (минимално) упаривање укупне тежине. Проблем тежинског подударања може бити решен комбинаторним алгоритмом који користи нетежински Едмондсов алгоритам као потпрограм. Колмогоров је обезбедио ефикасну C++ имплементацију.

Референце

^ Edmonds, Jack (199), „A glimpse of heaven”, Ур.: J.K. Lenstra; A.H.G. Rinnooy Kan; A. Schrijver, History of Mathematical Programming --- A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland,Amsterdam, стр. 32—54
^ Edmonds, Jack (1965). „Paths, trees, and flowers”. Canad. J. Math. 17: 449—467. doi:10.4153/CJM-1965-045-4.
^ Edmonds, Jack (1965). „Maximum matching and a polyhedron with 0,1-vertices”. Journal of Research National Bureau of Standards Section B. 69: 125—130.
^ Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. 24. Springer.

Литература

Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. 24. Springer.

[glimpse-1] Edmonds, Jack (199), „A glimpse of heaven”, Ур.: J.K. Lenstra; A.H.G. Rinnooy Kan; A. Schrijver, History of Mathematical Programming --- A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland,Amsterdam, стр. 32—54

[algorithm-2] Edmonds, Jack (1965). „Paths, trees, and flowers”. Canad. J. Math. 17: 449—467. doi:10.4153/CJM-1965-045-4.

[weighted-3] Edmonds, Jack (1965). „Maximum matching and a polyhedron with 0,1-vertices”. Journal of Research National Bureau of Standards Section B. 69: 125—130.

[schrijver-4] Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. 24. Springer.

[1]

[2]

[3]

[4]