From Wikipedia, the free encyclopedia
Eulerin polku on suunnatussa tai suuntaamattomassa graafissa oleva polku, joka kulkee graafin jokaisen kaaren kautta täsmälleen kerran. Jos Eulerin polku palaa lopuksi takaisin lähtösolmuun, se on Eulerin kierros. Käsitteet on tehnyt tunnetuksi sveitsiläinen matemaatikko Leonhard Euler, joka ratkaisi vuonna 1736 kuuluisan Königsbergin siltaongelman.
Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan. |
Välttämätön ehto Eulerin kierrokselle on jokaisen solmun asteen parillisuus. Graafissa on Eulerin polku, jos siinä on Eulerin kierros, tai jos täsmälleen kahden solmun aste on pariton. Lisäksi graafin tulee olla yhtenäinen. Königsbergin siltojen graafissa on neljä paritonasteista solmua, joten siitä ei löydy Eulerin polkua.
Oletetaan, että meillä on yhtenäinen graafi, jossa on korkeintaan kaksi paritonasteista solmua. Voimme löytää "Fleuryn algoritmilla" graafista Eulerin polun. Aloitamme polun paritonasteisesta solmusta, tai mielivaltaisesta solmusta mikäli graafissa ei ole paritonasteisia solmuja. Jokaisella askeleella liikumme solmusta toiseen siten, että valitun kaaren poistaminen ei tee graafin jäljellä olevista kaarien joukosta epäyhtenäistä. Sen jälkeen poistamme kyseisen kaaren graafista. Lopussa olemme käyneet läpi kaikki kaaret, ja niiden poistamisjärjestys antaa Eulerin polun.
Eulerin polkuja käytetään bioinformatiikassa dna-ketjujen rakentamisessa.
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.