A Magyar Módszertan ás általánosításai

Absztrakt

A lineáris programozás dualitás tételének legkorábban előforduló speciális alakja Egerváry Jenő tétele teljes páros gráf teljes párosításainak maximális súlyáról. Az elegáns bizonyítás elvezet agy hatékony algoritmushoz, melynek a szállítási problémára kiterjesztett alakja a nemzetközi szakirodalomban a Magyar Módszer nevet viseli. A módszer alapelvét azóta több irányban is általánosították: nempáros gráfok maximális súlyú párosításainak meghatározására, a súlyozott matroid metszet problémára, folyam és szubmoduláris áram feladatokra. Jelen munkában áttekinthetjük a Magyar Módszer e kiterjesztéseit.