Eulerin polku
 |
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. |
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.
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.
Eulerin polun konstruointi
[muokkaa | muokkaa wikitekstiä]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.
Sovelluksia
[muokkaa | muokkaa wikitekstiä]Eulerin polkuja käytetään bioinformatiikassa dna-ketjujen rakentamisessa.
Katso myös
[muokkaa | muokkaa wikitekstiä]Kirjallisuutta
[muokkaa | muokkaa wikitekstiä]- Ruohonen, Keijo: Graafiteoria. (Opintomoniste 136) Tampere: TTKK, 1990. ISBN 951-721-530-4
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]