Ero sivun ”Königsbergin siltaongelma” versioiden välillä

[[KuvaTiedosto:Konigsberg bridges.png|frame|rightthumb|[[Leonhard Euler|Eulerin]] aikaisen [[Königsberg]]in kartta, jossa sillat ja Pregolja-joki on korostettu.]]

'''Königsbergin siltaongelma''' on klassinen [[matematiikka|matemaattinen]] ongelma [[graafiteoria]]n ja [[topologia]]n alalta. Königsbergin eli nykyisen [[Kaliningrad]]in läpi virtaa [[Pregolja]]-joki, jonka keskellä on kaksi [[saari|saarta]]. Saaret oli [[1700-luku|1700-luvulla]] saaret oli yhdistetty toisiinsa ja mantereeseen seitsemällä sillalla (kuva oikealla). Ongelmana oli sellaisenkeksiä reitinsellainen keksiminenreitti, mitäjota kävelemälläkulkemalla 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.

Kuultuaan Königsbergin siltaongelmasta [[Sveitsisveitsi]]läinen [[matemaatikko]] [[Leonhard Euler]] oli kuultuaan Königsbergin siltaongelmasta päättänytpäätti 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 [[termi]]lläkäsitteillä kutsutaan [[graafi]]ksi. 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ä, taikkatai millä puolella toista solmua jokin solmu sijaitsee. Solmun asteluku on siihen ulottuvien kaarien lukumäärä.

Eulerin aikaisista Königsbergin silloista vainon kaksi onjäljellä enää jäljelläkaksi. Kaksi tuhoutui [[toinen maailmansota|toisen maailmansodan]] ilmapommituksissa. Yksi olipurettiin jo vuonna [[1935]] purettu uuden sillan tieltä., Kaksija kaksi muuta on myöhemmin purettu ja tilalle rakennettu moderni päätie.<ref>{{cite webVerkkoviite |urlOsoite=http://www.amt.canberra.edu.au/koenigs.html |title Nimeke=What ''Ever'' Happened to Those Bridges? |accessdate=2006-11-11 |lastTekijä=Taylor, |first=Peter |year Ajankohta=Joulukuu 2000 |month=December |publisherJulkaisija=Australian Mathematics Trust | Viitattu= | Kieli={{en}} }}</ref> Königsbergin eli nykyisen Kaliningradin vanhanVanhan kaupungin aluellaalueella on näin ollensiis 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.<ref>[http://www.csc.ncsu.edu/faculty/stallmann/SevenBridges/ Matthias Stallman: The 7/5 Bridges of Koenigsberg/Kaliningrad, 11.11.2006]</ref> Näiden lisäksi hiemanHieman keskikaupungin länsipuolella on kuitenkin myös kuudes silta, joka johtaa suoraan joen toiselta rannalta toiselle, ei siis saareen.<ref>[http://mathdl.maa.org/mathDL/1/?pa=content&sa=viewDocument&nodeId=1310&bodyId=1460 Teo Paoletti: Leonard Euler's Solution to the Konigsberg Bridge Problem, sisältää nyky-Kaliningradin kartan]</ref> Jos se luetaanotetaan mukaanhuomioon, on kaikkien solmupisteiden asteluku on pariton eikä Eulerin polkuakaan ole olemassa.

== ViitteetLähteet ==