Königsbergin siltaongelma
Wikipedia
Königsbergin siltaongelma on klassinen matemaattinen ongelma graafiteorian ja topologian alalta. Königsbergin eli nykyisen Kaliningradin läpi virtaa Pregolja-joki, jonka keskellä on kaksi saarta. Saaret oli 1700-luvulla yhdistetty toisiinsa ja mantereeseen seitsemällä sillalla (kuva oikealla). Ongelmana oli sellaisen reitin keksiminen mitä kävelemällä voitaisiin ylittää jokainen silta täsmälleen yhden kerran ja päätyä takaisin lähtöpisteeseen. Leonhard Euler todisti vuonna 1736, ettei tällaista reittiä ole olemassa.
Sisällysluettelo |
[muokkaa] Ongelman ratkaisu
Sveitsiläinen matemaatikko Leonhard Euler oli kuultuaan Königsbergin siltaongelmasta päättänyt ratkaista sen. Hän aloitti abstrahoimalla Königsbergin kartan poistaen ensin ylimääräiset piirteet siten, 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 termillä kutsutaan graafiksi. Pisteitä taas kutsutaan solmuiksi ja viivoja kaariksi.
→ 
→ 
Graafin muotoa voidaan muokata vapaasti ilman, että graafi itse muuttuu, kunhan solmujen väliset yhteydet pysyvät samoina. Ei ole merkitystä, ovatko kaaret suoria vai käyriä, taikka millä puolella toista solmua jokin solmu sijaitsee. Solmun asteluku on siihen ulottuvien 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ä asteeltaan paritonta solmua, joten polkua ei Königsbergin tapauksessa ole mahdollista piirtää.
Ongelma voidaan muuntaa sellaiseksi, että etsitään polkua, joka ylittää jokaisen sillan kerran, mutta jonka alku- ja loppupiste ei välttämättä ole sama. Tällaista polkua kutsutaan Eulerin poluksi; se on olemassa, jos ja vain jos graafissa on täsmälleen kaksi (tai ei yhtään) solmua, joiden asteluku on pariton siten, että nämä kaksi solmua ovat polun alku- ja loppusolmu. Königsbergin siltojen kohdalla tämäkään ehto ei toteudu.
[muokkaa] Historiallinen merkitys
Eulerin ratkaisua Königsbergin siltaongelmaan pidetään matematiikan historian ensimmäisenä teoreemana, joka koskee nykyisin graafiteoriana tunnettua matematiikan alaa. Tätä puolestaan pidetään nykyään yleisesti kombinatoriikan haarana (kombinatorisia ongelmia oli toki tutkittu jo paljon aikaisemmin).
Lisäksi Eulerin huomio siitä, että ongelman ratkaisemisen avain olivat siltojen määrä ja loppupisteet (eikä niiden täsmällinen sijainti), enteili topologian kehittymistä. Königsbergin kartan ja siitä johdetun kaavakuvan välinen ero havainnollistaa, että esineiden jäykkä muoto ei sinänsä ole merkityksellinen topologiassa.
[muokkaa] Siltojen nykytila
Eulerin aikaisista Königsbergin silloista vain kaksi on enää jäljellä. Kaksi tuhoutui toisen maailmansodan ilmapommituksista. Yksi oli jo vuonna 1935 purettu uuden sillan tieltä. Kaksi muuta on myöhemmin purettu ja tilalle rakennettu moderni päätie.[1] Köningsbergin eli nykyisen Kaliningradin vanhan kaupungin aluella on näin ollen nykyisin vain viisi siltaa.
Näin ollen graafiteorian kannalta nykyisin kahdella solmupisteellä on asteluku 2, kahdella muulla asteluku 3. On siis mahdollista kulkea kaikkien siltojen yli kerran, mutta tällöin reitin on alettava toiselta ja päätyttävä toiselle saarelle. Toisin sanoen Eulerin polku on olemassa, mutta Eulerin kehää ei.[2] Näiden lisäksi hieman keskikaupungin länsipuolella on kuitenkin myös kuudes silta, joka johtaa suoraan joen toiselta rannalta toiselle, ei siis saareen.[3] Jos se luetaan mukaan, on kaikkien solmupisteiden asteluku pariton eikä Eulerin polkuakaan ole olemassa.
[muokkaa] Viitteet
- ↑ Taylor, Peter (December 2000). What Ever Happened to Those Bridges?. Australian Mathematics Trust. Luettu 2006-11-11.
- ↑ Matthias Stallman: The 7/5 Bridges of Koenigsberg/Kaliningrad, 11.11.2006
- ↑ Teo Paoletti: Leonard Euler's Solution to the Konigsberg Bridge Problem, sisältää nyky-Kaliningradin kartan
[muokkaa] Aiheesta muualla
