Eulerin polku

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.

Königsbergin siltojen graafi

Ratkaisu "avatulle kirjekuoren tapaukselle".

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

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

Eulerin polkuja käytetään bioinformatiikassa dna-ketjujen rakentamisessa.

Katso myös

• Hamiltonin polku

Kirjallisuutta

• Ruohonen, Keijo: Graafiteoria. Opintomoniste 136. Tampere: TTKK, 1990. ISBN 951-721-530-4.

Aiheesta muualla

• Eulerin arkiston sivu sisältäen hiukan tietoa ja Eulerin papereiden vedoksen alla mainittuun viitteeseen (englanniksi)
• Keskustelua Fleuryn menetelmästä (englanniksi)