Königsbergin siltaongelma
Königsbergin seitsemän siltaa on historiallisesti kuuluisa matematiikan ongelma. Leonhard Euler ratkaisi ongelman vuonna 1735. Tämä johti graafiteorian alkuun. Tämä johti sitten topologian kehittymiseen.
Preussin Königsbergin kaupunki (nykyinen Kaliningrad, Venäjä) sijaitsi Pregel-joen molemmin puolin. Siihen kuului kaksi suurta saarta, jotka oli yhdistetty toisiinsa ja mantereeseen seitsemällä sillalla.
Ongelmana oli löytää tapa kävellä kaupungin läpi ylittämällä jokainen silta vain kerran. Saarille ei päässyt muita reittejä kuin siltoja pitkin. Jokainen silta oli ylitettävä kokonaan joka kerta. Kävelyn ei tarvinnut alkaa ja päättyä samaan paikkaan. Euler todisti, että ongelmalla ei ole ratkaisua.
Eulerin aikainen Königsbergin kartta, jossa näkyy seitsemän sillan todellinen sijainti, Pregel-joki ja sillat korostettuina.
Eulerin analyysi
Euler huomautti ensinnäkin, että kunkin maamassan sisällä kulkevan reitin valinnalla ei ole merkitystä. Reitin ainoa tärkeä ominaisuus on se, missä järjestyksessä sillat ylitetään. Niinpä hän muutti ongelman abstraktiksi. Tämä loi perustan graafiteorialle. Hän poisti kaikki muut ominaisuudet paitsi luettelon maamassoista ja niitä yhdistävistä silloista. Graafiteorian kielellä hän korvasi jokaisen maamassan abstraktilla "pisteellä" tai solmulla. Sitten hän korvasi jokaisen sillan abstraktilla yhteydellä, "reunalla". Reuna (tie) kirjasi, mitkä kaksi kärkeä (maamassat) olivat yhteydessä toisiinsa. Näin hän muodosti graafin.
→
→ 
Piirretty kuvaaja on abstrakti kuva ongelmasta. Särmät voidaan siis liittää toisiinsa millä tahansa tavalla. Tärkeää on vain se, ovatko kaksi pistettä yhteydessä toisiinsa vai eivät. Kuvaajan kuvan muuttaminen ei muuta itse kuvaajaa.
Seuraavaksi Euler havaitsi, että (kävelyn päätepisteitä lukuun ottamatta) aina kun pisteeseen tullaan sillan kautta, pisteestä lähdetään sillan kautta. Millä tahansa graafin kävelyllä on sama määrä kertoja, jolloin pisteeseen tullaan, kuin kuinka monta kertaa siitä lähdetään. Jos jokainen silta on ylitetty täsmälleen kerran, seuraa siitä, että jokaisen maamassan (lukuun ottamatta alku- ja loppupisteeksi valittuja maamassoja) kohdalla kyseistä maamassaa koskettavien siltojen lukumäärän on oltava parillinen. Tämä johtuu siitä, että jos siltoja on n, se ylitetään tasan 2n kertaa. Alkuperäisen ongelman kaikkia neljää maamassoja koskettaa kuitenkin pariton määrä siltoja (yhtä koskettaa 5 siltaa, ja kolmea muuta koskettaa 3 siltaa). On enintään kaksi massaa, jotka voivat olla kävelyn päätepisteitä. Näin ollen väite, jonka mukaan kävely ylittää jokaisen sillan kerran, johtaa ristiriitaan.
Nykykielellä Euler osoittaa, että solmujen asteluvuista riippuu, voidaanko graafin läpi kulkea siten, että jokainen särmä ylitetään kerran vai ei. Solmun aste on sitä koskettavien reunojen lukumäärä. Euler osoittaa, että kävelyn välttämätön ehto on, että graafi on yhdistetty ja että siinä on täsmälleen nolla tai kaksi parittoman asteen solmua. Tämän Eulerin esittämän tuloksen todisti myöhemmin Carl Hierholzer. Tällaista kävelyä kutsutaan nykyään Eulerin poluksi tai Eulerin kävelyksi. Jos on olemassa parittoman asteen solmuja, mikä tahansa Eulerin polku alkaa yhdestä niistä ja päättyy toiseen. Koska historiallista Königsbergiä kuvaavassa graafissa on neljä parittoman asteen solmua, sillä ei voi olla Eulerin polkua.
Eulerin teos esiteltiin Pietarin akatemialle 26. elokuuta 1735. Se julkaistiin nimellä Solutio problematis ad geometriam situs pertinentis (Paikan geometriaan liittyvän ongelman ratkaisu) Commentarii academiae scientiarum Petropolitanae -lehdessä vuonna 1741. Se on saatavilla englanninkielisenä julkaisussa The World of Mathematics.
Merkitys matematiikan historiassa
Matematiikan historiassa Eulerin ratkaisua Königsbergin siltaongelmaan pidetään ensimmäisenä graafiteorian teoreemana. Graafiteoriaa pidetään nykyään yleisesti kombinatoriikan haarana.
Siltojen nykytila
Seitsemästä alkuperäisestä sillasta kaksi tuhoutui Königsbergin pommituksissa toisessa maailmansodassa. Kaksi muuta purettiin myöhemmin. Ne korvattiin nykyaikaisella valtatiellä. Kolme muuta siltaa on säilynyt, mutta vain kaksi niistä on Eulerin ajalta (yksi rakennettiin uudelleen vuonna 1935). Näin ollen Kaliningradissa oli vuonna 2000 viisi siltaa.
Graafiteorian kannalta kahdella solmulla on nyt aste 2 ja kahdella muulla solmulla aste 3. Eulerin polku on siis nyt mahdollinen, mutta koska sen on alettava toiselta saarelta ja päätyttävä toiselle saarelle, se on matkailijoille epäkäytännöllinen.
Aiheeseen liittyvät sivut
- Icosian peli
- Hamiltonin polku
- Vesi, kaasu ja sähkö
- Matkustavan myyntimiehen ongelma
Kysymyksiä ja vastauksia
Q: Mikä on Königsbergin seitsemän siltaa -ongelma?
V: Königsbergin seitsemän siltaa on kuuluisa matemaattinen ongelma, jossa on löydettävä tapa kulkea kaupungin läpi ylittämällä jokainen sen seitsemästä sillasta kerran ja vain kerran.
K: Kuka ratkaisi Königsbergin seitsemän siltaa -ongelman?
V: Leonhard Euler ratkaisi Königsbergin seitsemän siltaa -ongelman vuonna 1735.
K: Mihin Königsbergin seitsemän sillan ongelman ratkaisu johti?
V: Königsbergin seitsemän sillan ongelman ratkaisu johti graafiteorian alkamiseen, joka sitten johti topologian kehittymiseen.
K: Missä Königsberg sijaitsee?
V: Königsberg sijaitsee Preussissa, joka on nykyään osa Kaliningradia Venäjällä.
K: Mikä oli Königsbergin pohjapiirustus?
V: Königsberg sijaitsi Pregeljoen molemmin puolin, ja siihen kuului kaksi suurta saarta, jotka oli yhdistetty toisiinsa ja mantereeseen seitsemällä sillalla.
K: Mitkä olivat Königsbergin seitsemän siltaa -ongelman ratkaisemisen edellytykset?
V: Ongelmassa piti keksiä keino kulkea kaupungin läpi ylittämällä jokainen silta kerran ja vain kerran siten, että jokainen silta ylitetään kokonaan joka kerta. Saarille ei voinut päästä muuta reittiä kuin siltoja pitkin, eikä kävelyn tarvinnut alkaa ja päättyä samaan paikkaan.
Kysymys: Osoittiko Euler, että Königsbergin seitsemän siltaa -ongelmalla on ratkaisu?
V: Ei, Euler todisti, että Königsbergin seitsemän sillan ongelmalla ei ole ratkaisua.
