From Wikipedia, the free encyclopedia
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.
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ükkel/tee esineb ainult sidusas graafis või graafis, mis peale kõikide seostamata tippude eraldamist muutub sidusaks.
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 graaf sisaldab Euleri tsüklit parajasti siis kui see on tugevalt sidus ja graafi iga tipu sisendi poolaste võrdub tema väljundi poolastmega.
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.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
