Euleri graaf

Euleri tee (ehk Euleri ahel) graafis on tee, mis kulgeb graafi kõiki servi pidi, läbides igat serva üks kord (võrdle Hamiltoni graafiga). Pildil oleva Königsbergi sildade probleemi lahendamine Leonhard Euleri poolt 1736. aastal pani aluse graafiteooria tekkele.

Königsbergi sildade graaf. See ei ole Euleri graaf, sest iseloomulik tulemus puudub

Euleri graafi iga tipp on paarisarv valentne (astmeline). Liikumine mööda servi alfabeetilises järjestuses annab Euleri tsükli

Euleri tsükkel – Euleri tee, mis suletult moodustab tsükli.

Euleri graaf – graaf, mis sisaldab Euleri tsüklit.

Pooleuleri graaf – graaf, mis sisaldab Euleri teed (ahelat).

Euleri tsükli ja Euleri tee olemasolu

Euleri tsükkel/tee esineb ainult sidusas graafis või graafis, mis peale kõikide seostamata tippude eraldamist muutub sidusaks.

Lihtgraafis

Vastavalt Euleri teoreemile esineb Euleri tsükkel parajasti siis kui graaf on sidus ja selles ei ole paarituarvulise valentsiga (astmega) tippe.

Euleri tee graafis esineb parajasti siis kui graaf on sidus ja ei sisalda rohkem kui kaht paarituarvulise valentsiga (astmega) tippu. Vastavalt Handshakingi „kätlemise“ lemmale peab paarituarvulise valentsusega (astmega) tippude arv olema paarisarvuline. Seega, Euleri tee esineb vaid siis, kui see arv on null või kaks. Samas muutub see tee nulli puhul Euleri tsükliks.

Suunatud graafis

Suunatud graaf sisaldab Euleri tsüklit parajasti siis kui see on tugevalt sidus ja graafi iga tipu sisendi poolaste võrdub tema väljundi poolastmega.

Euleri tee leidmine

Alati on võimalik taandada Euleri tee leidmise ülesanne Euleri tsükli leidmise ülesandele. Tõepoolest, oletagem et need mõlemad on graafis olemas. Siis on selles täpselt 2 paarituarvulise valentsiga tippu. Ühendame need tipud servaga, ja saame graafi mille kõik tipud on paarisarv valentsed ning Euleri tsükkel eksisteerib. Leiame selles graafis Euleri tsükli ja eraldame saadust selle olematu serva.

Euleri tsükli leidmine

Vaadelgem kõige üldisemat – suunatud, multigraafi ja sõlmede juhtu. Samas eeldame, et Euleri tsükkel graafis esineb (ja koosneb vähemalt ühest tipust). Leidmiseks lähtume asjaolust, et Euleri tsükkel kujutab endast graafi kõikide lihttsüklite ühendit. Seega seisneb ülesanne nende efektiivses leidmises ja üheks ühendamises. See on teostatav, näiteks rekursiivselt või süvaotsingu teel.

Kirjandust

• A. Buldas, P. Laud, J. Villemson. 2003. Graafid. Tartu, ISBN 9789949118182
• F. Harary. 1972. Graph Theory. Addison-Wesley.
• A. Dharwadker, S. Pirzada. 2011. Graph Theory. Amazon Books, ISBN 9781466254992.