AlegsaOnline.com

Königsbergin siltaongelma: Euler, graafiteoria ja topologian alku

Tutustu Königsbergin siltaongelmaan: miten Euler ratkaisi sen 1735 ja synnytti graafiteorian sekä topologian perusteet. Historiaa, selitys ja vaikutukset.

Tekijä: Leandro Alegsa Luontipäivä: 5. huhtikuuta 2022 Viimeisin päivitys: 19. helmikuuta 2026

simple.wikipedia.org · CC BY-SA 3.0

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.

Miten Euler lähestyi ongelmaa

Eulerin keskeinen idea oli yksinkertaistaa tehtävä poistamalla tarpeettomat yksityiskohdat: sillat ja saaret kuvattiin symboleilla. Hän huomasi, että ongelma ei riipu siltojen pituuksista tai kaupunkikuvasta, vaan siitä, miten alueet on yhdistetty. Tämän abstraktion myötä syntyi graafi, jossa

solmut (eli vertice) edustavat maanosia (kumpareita ja rantoja),
kaaret (eli edge) edustavat siltoja, jotka yhdistävät maanosia.

Lyhyt kuvaus todistuksesta

Euler esitti yksinkertaisen laskusäännön solmujen asteesta (degree): solmun aste on siihen liittyvien siltojen (kaarten) lukumäärä. Omatoimisen polun (trail), joka kulkee jokaisen sillan täsmälleen kerran, olemassaolon mahdollisuus riippuu siltojen ja solmujen parittomuudesta. Perusajatuksena:

jokaisella kerralla, kun polku tulee solmuun ja lähtee siitä, käytetään kahta kaarta;
sen vuoksi jos polku alkaa ja päättyy eri solmuihin, tarkasteltavissa verkon solmuissa voi olla korkeintaan kaksi solmua, joiden aste on pariton (aloitus- ja lopetussolmu);
jos polku alkaa ja päättyy samaan solmuun (suljettu lenkki eli Eulerin sykli), kaikkien solmujen asteet ovat parillisia.

Königsbergin tapauksessa kaupungissa oli neljä maanosa-aluetta, joiden yhteiset sillat muodostivat solmujen asteiksi 3, 3, 3 ja 5 (eli kaikki neljä ovat parittomia). Koska parittomia solmuja on enemmän kuin kaksi, Euler päätteli, että sellaista kävelyreittiä, joka kulkisi jokaisen sillan täsmälleen kerran, ei voi olla.

Yleistys: Eulerin polkujen ehto

Tämä havainto yleistyi muodolliseksi lauseeksi graafiteoriassa:

Yhdistetyssä graafissa on Eulerin sykli (suljettu reitti, joka kulkee jokaisen kaaren kerran) täsmälleen kun jokaisen solmun aste on parillinen.
Yhdistetyssä graafissa on Eulerin polku (avoin reitti, joka kulkee jokaisen kaaren kerran) täsmälleen kun parittomia solmuja on nolla tai kaksi.

Merkitys graafiteorialle ja topologialle

Eulerin käsittely oli merkittävä, koska se siirsi painopisteen tarkasta geometrisesta muodosta kohti rakenteellista yhteyksien tarkastelua. Tällainen lähestymistapa oli eräänlainen topologista ajattelua ennen kuin topologia oli itsenäinen matematiikan haara. Königsbergin ongelman analyysi usein mainitaan graafiteorian synnynä ja osoituksena siitä, kuinka abstraktio voi johtaa uusiin matemaattisiin aloihin.

Nykykäyttöjä ja esimerkkejä

Eulerin polkujen käsitteellä on nykyään käytännön sovelluksia muun muassa reititysongelmissa, verkkoanalyysissä, logistiikassa ja tietoliikenteessä. Esimerkiksi postinjakelussa tai katujen siivouksessa halutaan usein löytää reittejä, jotka kattavat kaikki kadut tehokkaasti; tällöin tutkitaan, voiko työ tehdä Eulerin polun tai millä muutoksilla (esimerkiksi yhdistämällä katuja) sellainen saadaan aikaan.

Yhteenveto: Königsbergin siltaongelma johti ajatukseen, että oleellista on yhteyksien rakenne, ei mittasuhteet. Eulerin ratkaisu, joka käytti solmujen asteita ja parillisuutta, muotoili ehdot Eulerin polun olemassaololle ja avasi tien graafiteorialle ja myöhemmin topologialle.

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.