From Wikipedia, the free encyclopedia
Алгоритам максималног упаривања (енгл. ) је алгоритам у теорији графова и користи се за конструисање максималног поклапања на графу. Алгоритам је открио Џек Едмондс 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 максимално акко нема даљег 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’ (ако постоји) обиласка vB је замењен било којим одговарајућим сегментом обиласка B. Или детаљније:
Дакле, цветови могу бити контраховани и претраживање се врши у контрахованим графовима. Ово смањење је срж Едмондсовог алгоритма.
Потрага за повећавајућим путем користи помоћну структуру података која се састоји од шуме 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 { 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 конструисана функцијом нађи_повећавајући_пут() је наизменична шума.
Свака итерација петље почевши од линије B09 или додаје стаблу T у F (линија B10) или проналази повећавајући пут (линија B17) или проналази цвет (линија B21). Сада видимо да је време извршавања . Микали и Вазирани су представили алгоритам који конструише максимално упаривање у времену.
Алгоритам се своди на стандардни алгоритам упаривања у бипартитним графовима када је G бипартитно. Како нема непарних циклуса у G у том случају цветови неће бити нађени и због тога могу бити уклоњене линије B21 - B29 овог алгоритма.
Проблем упаривања може бити генерализован додељивањем тежина гранама у G и тражећи M које ће сачињавати максимално (минимално) упаривање укупне тежине. Проблем тежинског подударања може бити решен комбинаторним алгоритмом који користи нетежински Едмондсов алгоритам као потпрограм. Колмогоров је обезбедио ефикасну C++ имплементацију.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.