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

[[Kuva:Konigsberg bridges.png|frame|right|[[Leonhard Euler|Eulerin]] aikaisen [[Königsberg]]in kartta, jossa sillat ja Pregel-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 [[Pregel]]-joki, jonka keskellä on kaksi [[saari|saarta]]. Saaret oli [[1700-luku|1700-luvulla]] yhdistetty toisiinsa ja mantereeseen seitsemällä sillalla (katso kuva oikealla). Ongelmana oli keksiäsellaisen reitti,reitin keksiminen jotamitä kävelemällä voisivoitaisiin ylittää jokaisenjokainen sillansilta täsmälleen yhden kerran ja päätyä takaisin lähtöpisteeseen. [[Leonhard Euler]] todisti vuonna [[1736]], ettei kyseistätällaista reittiä ole olemassa.

[[Sveitsi]]läinen [[matemaatikko]] [[Leonhard Euler]] oli kuullutkuultuaan Königsbergin siltaongelmasta ja päättipäättänyt ratkaista sen. Hän aloitti abstrahoimalla KönigberginKönigsbergin kartan poistaen ensin ylimääräiset piirteet, niinsiten, 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ä[[termi]]llä kutsutaan [[graafi]]ksi. Pisteitä taas kutsutaan solmuiksi ja viivoja kaariksi.

Graafin muotoa voivoidaan muokata vapaasti ilman, että graafi itse muuttuu, kunhan solmujen väliset yhteydet pysyvät samanasamoina. Sillä eiEi ole väliämerkitystä, ovatko kaaret suoria vai käyriä, taitaikka millä puolella toista solmua jokin solmu sijaitsee. Solmun asteluku on siihen tulevienulottuvien 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 luku|pariton]]. Königsbergin silloista muodostuvassa graafissa on kolme solmua, joiden asteluku on kolme, ja yksi solmu, jonka asteluku on viisi, yhteensä siis neljä paritonasteistaasteeltaan paritonta solmua, joten polkua ei Königsbergin tapauksessa ole mahdollista piirtää.

OngelmaaOngelma voivoidaan muokatamuuntaa niinsellaiseksi, että etsitään polkua, joka ylittää jokaisen sillan kerran, mutta jonka alku- ja loppupisteetloppupiste eivätei välttämättä ole samatsama. Tällaista polkua kutsutaan ''[[Eulerin polku|Eulerin poluksi]]'', ja; se on olemassa, jos ja vain jos graafissa on täsmälleen kaksi (tai ei yhtään) solmua, jonkajoiden asteluku on pariton siten, niin että nämä kaksi solmua ovat polun alku- ja loppusolmutloppusolmu. Königsbergin silloillesiltojen eikohdalla löydytämäkään ehto ei tätäkääntoteudu.

Eulerin ratkaisua Königsbergin siltaongelmaan pidetään matematiikan historian ensimmäisenä teoreemana, joka koskee nykyisin graafiteoriana tunnettua matematiikan alaa,. jotaTätä puolestaan pidetään nykyään yleisesti pidetään [[kombinatoriikka|kombinatoriikan]] haarana (kombinatorisia ongelmia oli toki tutkittu jo paljon aikaisemmin).

Lisäksi Eulerin huomio siitä, että ongelman ratkaisemisen avain oliolivat siltojen määrä ja niiden loppupisteet (eikä niiden täsmällinen sijainti), enteili [[topologia]]n kehittymistä. Königsbergin kartan ja siitä johdetun kaavakuvan välinen ero havainnollistaa, että esineiden jäykkä muoto ei kosketasinänsä ole merkityksellinen topologiaatopologiassa.

*[http://www.amt.canberra.edu.au/koenigs.html Australian Mathematics Trust -– The Bridges of Königsberg]{{en}}