Königsbergin siltaongelma

Eulerin aikaisen Königsbergin kartta, jossa sillat ja Pregel-joki on korostettu

Königsbergin siltaongelma on klassinen matemaattinen ongelma graafiteorian ja topologian alalta. Königsbergin eli nykyisen Kaliningradin läpi virtaa Pregel-joki, jonka keskellä on kaksi saarta. Saaret oli 1700-luvulla yhdistetty toisiinsa ja mantereeseen seitsemällä sillalla (katso kuva oikealla). Ongelmana oli keksiä reitti, jota kävelemällä voisi ylittää jokaisen sillan täsmälleen yhden kerran ja päätyä takaisin lähtöpisteeseen. Leonhard Euler todisti vuonna 1736, ettei kyseistä reittiä ole olemassa.

Ongelman ratkaisu

Sveitsiläinen matemaatikko Leonhard Euler oli kuullut Königsbergin siltaongelmasta ja päätti ratkaista sen. Hän aloitti abstrahoimalla Königbergin kartan, poistaen ensin ylimääräiset piirteet, niin että jäljelle jäävään kuvaan oli merkitty vain maamassat, niitä erottava vesi ja niiden väliset sillat. Seuraavaksi hän korvasi maamassat pisteillä ja niitä yhdistävät sillat viivoilla saaden tulokseksi alla kuvatun verkon, jota graafiteorian termeillä kutsutaan graafiksi. Pisteitä taas kutsutaan solmuiksi ja viivoja kaariksi.

→ →

Graafin muotoa voi muokata vapaasti ilman että graafi itse muuttuu kunhan solmujen väliset yhteydet pysyvät samana. Sillä ei ole väliä ovatko kaaret suoria vai käyriä, tai millä puolella toista solmua jokin solmu sijaitsee. Solmun asteluku on siihen tulevien kaarien lukumäärä.

Euler todisti että graafiin on mahdollista piirtää polku, Eulerin kehä, joka kulkee graafin jokaisen kaaren kautta täsmälleen kerran palaten alkusolmuun, jos ja vain jos graafissa ei ole yhtään solmua, jonka asteluku on pariton. Königsbergin silloista muodostuvassa graafissa on kolme solmua joiden asteluku on kolme ja yksi solmu jonka asteluku on viisi, yhteensä siis neljä paritonasteista solmua, joten polkua ei Königsbergin tapauksessa ole mahdollista piirtää.

Ongelmaa voi muokata niin että etsitään polkua, joka ylittää jokaisen sillan kerran, mutta jonka alku- ja loppupisteet eivät välttämättä ole samat. Tällaista polkua kutsutaan Eulerin poluksi ja se on olemassa jos ja vain jos graafissa on täsmälleen kaksi (tai ei yhtään) solmua, jonka asteluku on pariton, niin että nämä kaksi solmua ovat polun alku- ja loppusolmut. Königsbergin silloille ei löydy tätäkään.