Kínai Postás feladat

A Kínai Postás probléma:

Hétköznapi megfogalmazás: Adott egy postás, aki minnél rövidebb úton kívánja bejárni körzetének összes utcáját. A problémát Mai-ko Kwan kínai matematikus vizsgáta elősször. Igen. Ezért ez az elnevezése...
Matematikaibb megfogalmazás: Adott G összefüggő, irányítatlan gráf l távolságfüggvénnyel /A programban ezt most konstans 1-nek vesszük, nem az egyszerűsítés, hanem az átláthatóság kedvéért. Az algoritmus nem nehezebb nem konstans l esetén sem./. Keressük azt a zárt sétát, aminek költsége minimális. /Megj.: páros gráfoknál ez a zárt Euler-körrel esik egybe./
A program használatához különösebb dokumentáció nem szükséges. A főbb tudnivalók a programban is meg vannak említve.
Algoritmus:
1. Páratlan fokú csúcsok meghatározása. Ilyen csúcsból páros sok van.
2. Páratlan fokú csúcsok párosítása úgy, hogy a felvett új élet költségeinek összege minimális legyen.
3. Az immáron páros gráfban zárt Euler vonal keresése diszjunkt körökre bontással.
4. Az Euler-vonalunk megfelel a feladat megoldásának /szem előtt tartva, hogy a felvett új élek helyett a nekik megfelelő utakat kell a vonalba képzelni/.
A program megírásában segítségemre volt Hajnal Péter honlapja /"http://www.math.u-szeged.hu/~hajnal/courses/grafelmelet/kinai_p.htm"/.