Königsbergin seitsemän siltaa

1700-luvulla Königsbergin kaupungissa asuneet ihmiset pohtivat pitkään yhtä arvoitusta: kaupungin läpi virtaa Pregolja-joki, joka muodostaa kaksi saarta. Joen yli johtaa saarille yhteensä seitsemän siltaa. Onko mahdollista kävellä yhdellä sunnuntaikävelyllä kaikkien siltojen yli, mutta kunkin yli vain kerran? Katsotaan, miten sillat joen yli sijaitsivat:

Onko mahdollista aloittaa kävely jostain paikasta ja kulkea kaikkien siltojen yli tasan kerran? Voidaan yrittää: aloitetaan vasemmalta alhaalta ja edetään ylös ja sitten vähitellen oikealle, näin:

Nähdään, että seitsemästä sillasta kuljettiin kuuden yli, yksi silta jäi väliin. Voidaan yrittää toista reittiä…

Jälleen kuljettiin vain kuuden Königsbergin seitsemästä sillasta. Melkein vaikuttaa siltä, ettei ole mahdollista ylittää yhdellä kävelyllä jokaista siltaa tasan kerran. Eräänä päivänä tähän ongelmaan törmäsi tunnettu matemaatikko Leonhard Euler. Mikä tunnettu – Euler oli matematiikan todellinen legenda, jonka mukaan on nimetty jopa Eulerin luku. Euler päätti ratkaista tämän arvoituksen. Hän aloitti merkitsemällä erikseen saaret eli kaupungin osat, joihin ja joista sillat johtivat:

Euler teki nyt seuraavan päättelyn: jos jollekin saarelle johtaa parillinen määrä siltoja, nämä sillat voi kulkea yhden kävelyn aikana riippumatta siitä, mistä aloittaa. Eli yhtä siltaa pitkin saarelle tullaan ja toista pitkin lähdetään – jäljellä olevien kuljettavien siltojen määrä väheni kahdella. Jotta voi tulla yhtä siltaa pitkin saarelle ja lähteä toista pitkin, tarvitaan kaksi siltaa. Jos saarelle johtaa kuusi siltaa, saarella vieraillaan kolme kertaa. Kuvitellaan esimerkiksi, että saarelle B johtaisi neljä siltaa näin:

Silloin yhdellä sunnuntaikävelyllä voi kulkea kaikkien siltojen yli, vaikka aloittaisi mistä tahansa. Kokeile itse! Kuvaan on merkitty yksi reitti. Kuvitellaan sitten, että saarelle B johtaisi vielä yksi silta saarelta D:

Nähdään, että valittu reitti ei salli kulkea kaikkien siltojen yli tasan kerran. Jonkin sillan yli täytyisi palata saarelle B ja vasta sitten mennä saarelle D. Voidaan kuitenkin valita toinen reitti. Kävely voidaan aloittaa saarelta B, ja sitten voidaan kulkea kaikkien siltojen yli tasan kerran:

Kävely aloitettiin saarelta B, mentiin ylös alueelle A, sitten sillan kautta takaisin saarelle B, alueelle C, sitten takaisin saarelle B ja lopuksi saarelle D. Jos siis aloitetaan saarelta, jolle johtaa pariton määrä siltoja, kaikkien sen siltojen yli voi kulkea tasan kerran. Tai voidaan toimia aivan päinvastoin – aloittaa saarelta D ja lopettaa saarella B.

Euler huomasi siis, että jotta kaikkien siltojen yli voi kulkea tasan kerran, täytyy päteä joko se, että kaikille saarille johtaa parillinen määrä siltoja, tai se, että saaria voi olla kaksi, joille johtaa pariton määrä siltoja – toiselta parittoman siltamäärän saarelta aloitetaan ja toisella lopetetaan. Kaikille muille saarille täytyy johtaa parillinen määrä siltoja. Kun katsotaan Königsbergin alkuperäistä seitsemää siltaa:

nähdään, että jokaiselle saarelle johtaa pariton määrä siltoja! Saarelle A johtaa 3, B:lle 5, C:lle 3 ja D:lle myös 3. Siksi arvoitukselle ei ole ratkaisua – ei ole mahdollista kulkea kaikkien seitsemän sillan yli tasan kerran yhdellä sunnuntaikävelyllä. Jos mikä tahansa silta purettaisiin, arvoituksella olisi yhtäkkiä ratkaisu. Puretaan esimerkiksi yksi saarten B ja C välisistä silloista:

Nähdään, että saarelle B johtaa nyt äkkiä 4 siltaa ja saarelle C kaksi siltaa. Saarten A ja D siltojen määrä ei muuttunut. Nyt on kaksi saarta, joille johtaa parillinen määrä siltoja, ja kaksi saarta, joille johtaa pariton määrä siltoja. Jos kävely aloitetaan joltakin saarelta, jolle johtaa pariton määrä siltoja, kaikkien siltojen yli voi kulkea tasan kerran. Kuvassa aloitettiin saarelta A ja lopetettiin saarella D.

Leonhard Euler ratkaisi siis jälleen yhden kuuluisan matemaattisen ongelman ja loi enemmän tai vähemmän perustan sille, mitä nykyisin kutsutaan graafiteoriaksi, ja hänen kunniakseen graafia, jossa kaikki kaaret voi kulkea tasan kerran, kutsutaan graafiteorian kielellä Eulerin graafiksi.