Eulerin polut ja kierrokset

Abstract

LuK-tutkielman aiheena on Eulerin polut ja kierrokset suunnatuissa ja suuntaamattomissa verkoissa. Suuntaamaton verkko koostuu solmuista ja näitä solmuja yhdistävistä kaarista. Verkko voidaan esittää kuvana, jossa solmut ovat pisteitä ja kaaret näitä pisteitä yhdistäviä viivoja. Verkolla on Eulerin kierros silloin, jos on mahdollista aloittaa jostain solmusta, edetä kaaria pitkin solmusta toiseen ja palata lähtösolmuun siten, että jokainen kaari käydään läpi täsmälleen kerran. Eulerin polku määritellään vastaavasti, mutta ei edellytetä palaamista lähtösolmuun.

Suunnatuissa verkoissa kaaret ovat suunnattuja, eli niitä pitkin voidaan edetä vain yhteen suuntaan. Suunnattu verkko voidaan esittää vastaavanlaisena kuvana, jossa kaaret ovat nuolia.

Tutkielman ensimmäisessä luvussa määritellään suunnattujen ja suuntaamattomien verkkojen keskeiset käsitteet. Toisessa luvussa esitellään ja todistetaan lauseet sille, millaiselle suuntaamattomalle verkolle on olemassa Eulerin kierros ja millaiselle Eulerin polku. Vastaavat lauseet esitellään ja todistetaan myös suunnatuille verkoille.