Az alapfeladat: Adott egy G összefüggő gráf egy l távolságfüggvénnyel az éleken. Az éleken definiált távolság természetesen kiterjeszthető a sétákra. Egy séta hossza a séta lépéseinek hosszösszege. A probléma a legrövidebb, G összes élét bejáró, zárt séta megkeresése. (Mai-ko Kwan kínai matematikus vizsgálta először 1962-ben a problémát, amely természetes interpretációja, hogy egy postás szeretné minél rövidebb út megtételével bejárni körzetének összes utcáját.)
0. észrevétel: Ha G minden fokszáma páros, akkor gráfunkban van zárt Euler-vonal, ami egy megengedett megoldás és természetesen optimális. Másrészt, ha G nem minden fokszáma páros, akkor az optimális séta bizonyos éleket többször is bejár.
Legyen M a megengedett megoldások halmaza, azaz az összes élt tartalmazó zárt séták halmaza. A továbbiakban ez a halmazt tekintjük különböző szemüvegeken keresztül.
1. észrevétel: Egy G gráfbeli S séta meghatároz egy G(S) gráfot a következőképpen. Minden e élt helyettesítünk m(e) párhuzamos éllel, ahol m(e) azt adja meg, hogy az S séta hányszor járja be az e élt (azaz minden e élre m(e) legalább 1). A párhuzamos élek hossza/költsége azonos az e élével. Ekkor egy M-beli S sétát G(S)-be vetíthetünk: Ha i-edszer haladunk át az e élen, akkor G(S)-ben aze él i-edik példányán haladunk át. Így a G-beli S zárt séta egy G(S)-beli zárt Euler-vonal lesz. Így S leírható/azonosítható azon G(S) gráfokkal, amelyek G-ből élsokszorozással kapható úgy, hogy minden csúcs foka páros legyen. Legyen M1 ezek halmaza. Egy M1-beli sokszorozott gráf hossza az élhosszainak összeges. Az M1-beli élhossz minimalizálása csak eredeti problémánk átfogalmazása.
2. észrevétel: G(S) leírható úgy is, hogy a G gráf minden e éle mellé berakunk m(e)-1 páhuzamos ``iker élt''. A mellérakott élek alkossák a G+ gráfot. Azaz G(S)``=''G+G+, ahol a a + jellel jelölt művelet a két közös ponthalmazon értelmezett gráf éldiszjunkt összege. Azaz a két gráfor egymásra helyezzük úgy, hogy a különböző gráfból eredő élek ne fedjék egymást. A diszjunkt unióból eredő gráf fokszámait úgy kapjuk meg, hogy a tag gráfok fokszámait összeadjuk. Legyen M2 a lehetséges G+ gráfok halmaza, azaz olyan gráfok, amik G-ből az élek többszörözésével kaphatok (és most a 0-szorzás is megengedett) úgy, hogy G+ páratlan fokú csúcsainka halmaz ugyanaz legyen mint G-é (ekkor és csak ekkor lesz G+G+-ban minden fok páros. Tehát M2-t úgy kaptuk, hogy `mindegyik M1-beli gráfból kivettük a közös G-t'. Az, hogy ezen gráfok közt megkeresni a legkisebb összhosszút, az ekvivalens az eredeti problémával. Legyen O a G gráf páratlan fokszámú csúcsainak halmaza.
3. észrevétel: A fenti észrevételben vizsgált G+ gráfnak tartalmazni kell O-t párosító éldiszjunkt utakat. Miért? Nyilvánvalóan, ha egy O-t párosító útrendszert éldiszjunktan uniózunk, akkor egy olyan gráfot kapunk, amely M2-beli. Így az M2 halmaz egy M3 részhalmazához jutunk. A fenti észrevétel alapján az M3-beli optimalizálás ekvivalens az eredetivel.
Ezek után már közel vagyunk az algoritmus megadásához. Az M3-n történő optimalizálás visoznylag tiszta. M3 egy elemei kettébonthatók: van O egy párosítása és egy ezt megvalósító útrendszer. Az útrendszer elemeinek az optimumnál nyilván a megfelelő csúcspár közti minimális hosszú útnak kell lenni. Ez aalpján írhatjuk fel a következő algoritmust.
1. lépés: Határozzuk meg a G gráf páratlan fokú csúcsainak halmazát, O-t.
2. lépés: O minden pontpárjára határozzuk meg a kötük vezető legrövidebb út hosszát. (Például Dijkstra-algoritmus többszörös futtatása.)
3. lépés: O elmeit (amelyek páros sokan vannak) párosítsuk úgy, hogy az egy párba került csúcsok közötti legrövidebb utak hosszösszege minimális legyen. (Minimális költségű teljes párosítás keresése. Ez egy nehéz probléma, amit nem vizsgáltunk ezen előadás keretében. Habár a páros gráfok esetére a lineáris programozási módszer elvezetett ezen kérdés megválaszolásához (ez itt nem sokat segít, mert egy teljes gráfon kell futtatni az eljárást).)
4. lépés: A 3. lépésben megtalált párok közti utakat (éldiszjunkt módon) adjuk, hozzá kiinduló G-nkhez. Így egy G' gráfot kapunk.
5. lépés: A G' gráfban keressünk zárt Euler-vonalat.
5. lépés: A kapott Euler-vonal G-ben felfogható egy zárt sétának, ez lesz eljárásunk inputja.
Észrevételeink alapján algoritmusunk helyes.
Egy kicsit bonyolultabb érveléshez jutunk, ha észrevesszük, hogy az M2 halmazt másképpen is megritkíthatjuk: Az optimális megengedett megoldás esetén G+ gráf nem tartalmaz párhuzamos éleket. Ezek megléte esetén két párhuzamos él elhagyásával egy jobb megengedett megoldáshoz jutunk. Azaz az optimális postásnak nem érdemes egyik élt sem bejárni háromszor vagy többször.
Így a megengedett megoldások halmazát véges halmazzá szükíthetjük: G+-nak a G gráf egy részgráfjának kell lennie. Legyen M2,5 G azon részgráfjainka halmaza, ahol a páratlan fokú csúcsok halmaza O. Ez hiba lenne. Ekkor ugyanis a fenti algoritmus által, a segédgráfban megtalált optimális párosítás mögött lévő útrendszerről nem látjuk, hogy a szűkített megengedett megoldások halmazához tartozik, más szóval nem látjuk éldiszjunktságukat. Ez problémát okoz: lehet, hogy az éldiszjunkt utakkal történő optimális párosításban vannak olyan utak, amik egy magukban nem optimálisak, így nincsenek benne a segédgráfban.
Ez azonban csak az első látszat. Valójában, ha O elemei közötti optimális párosítás éleinek megfelelő utakat vesszük, akkor azok automatikusan éldiszjunktak lesznek és az algoritmus a szűkített megengedett megoldások egy elemét adja. Miért
A témával kapcsolatos honlapok: