Алгоритам максималног упаривања
From Wikipedia, the free encyclopedia
Алгоритам максималног упаривања (енгл. ) је алгоритам у теорији графова и користи се за конструисање максималног поклапања на графу. Алгоритам је открио Џек Едмондс 1961. године,[1] а објавио 1965.[2] Посматрајући неусмерени граф graph G = (V, E), алгоритам проналази одговарајуће M такво да сваки чвор у V је заједнички са најмање једном граном у M и |M| је увећано. Упаривање је замишљено као итеративно попуњавање иницијално празног упаривања дуж повећавајућег пута у графу.
Главни разлог важности овог алгоритма је да је био први доказ да се максимално упаривање може наћи у полиномијалном времену. Други разлог је што је довео до линеарног програмирања полихедралног описа одговарајућег политопа, што је даље дало алгоритам за минималну тежину подударања.[3] Како је образложио Александар Шријвер, даљи значај долази из чињенице да је ово први политоп чији доказ интегралности „не долази само из укупне унимодуларности и његов опис је био напредак у полиедарској комбинаторици.“[4]