Eulerin polku

Wikipedia
Loikkaa: valikkoon, hakuun
Königsbergin siltojen graafi

Eulerin polku on suunnatussa tai suuntaamattomassa graafissa oleva polku, joka kulkee graafin jokaisen kaaren kautta täsmälleen kerran. Eulerin polun erikoistapaus on Eulerin kierros, joka on suunnatussa tai suuntaamattomassa graafissa oleva polku, joka kulkee graafin jokaisen kaaren kautta täsmälleen kerran ja palaa lopuksi lähtösolmuun. 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ä]

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]

Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.