Königsbergin siltaongelma

Teksti: Milja Niemi, Venla Väli-Torola & Miia Liimatainen Kuvat: Saara Lehto

Königsbergin siltaongelma

Königsbergin eli nykyisen Kaliningradin läpi virtaa Pregolja-joki, jonka keskellä on kaksi saarta. Saaria yhdisti 1700-luvulla 7 siltaa. Sveitsiläinen matemaatikko Leonhard Euler keksi noihin aikoihin Königsbergin siltaongelman.

Kartta1: Könisbergin siltaongelma

Ongelmana on keksiä sellainen reitti, jota kulkemalla voitaisiin ylittää jokainen silta täsmälleen yhden kerran. Reitin voi aloittaa mistä kohtaa vain maalta ja lopettaa myös mihin kohtaan vain. Ei tarvitse siis päätyä aloituspisteeseen. Löytyykö tällaista reittiä?

Alla on esitetty Königsbergin lisäksi kolme muutakin karttaa. Millä kartoilla reittiongelmaan löytyy ratkaisu? Millä kartoilla reittiä ei tunnu löytyvän?

Kartta2
Kartta3
Kartta4

Löydätkö yhtäläisyyksiä niiden karttojen välillä joilta reitti löytyy tai niiden karttojen välillä joilta reittiä ei löydy?

Tarkastele karttoja joissa reittiä ei löydy. Auttaisiko jos joen yli rakennettaisiin johonkin kohtaan uusi silta?

Verkkoja, solmuja ja polkuja

Kun olet etsinyt reittejä eri kartoilta riittämiin, katsotaan, miten saadaan selville mitkä kartoista ovat ratkaistavissa. Tehdään kartoista uudet piirrokset, joissa maaosuudet on merkitty solmuilla (eli piirroksissa ympyröinä) ja niitä yhdistävät sillat on merkitty poluilla (eli piirroksessa ympyröiden välisinä viivoina). Tällaista karttaa kutsutaan verkoksi. Alla on esimerkki kartasta 1 laaditusta verkosta.

Verkko1

Ota verkosta 1 mallia ja piirrä vastaavat verkot muistakin kartoista.

Laske seuraavaksi, kuinka monta polkua (eli piirroksen viivaa) menee yhteen solmuun (eli ympyrään) ja kirjoita vastaus kunkin ympyrän sisälle. Verkossa 1 luvut näyttävät siis tältä:

 

Laske polkujen määriä kuvaavat numerot myös muihin piirtämiisi verkkoihin.

Mitkä verkoista olivat mielestäsi ratkaistavissa? Löydätkö jotain erityistä solmujen numeroista niissä verkoissa, joista ratkaisu löytyi? Onko väliä mistä solmusta aloitat ja mihin lopetat? Mitä yhteistä on verkoilla, joita et saanut ratkaistua? Millaisen säännön voisimme keksiä sille, milloin verkko voidaan ratkaista? Jos reittiä ei löydy, millaisia solmuja on paljon?

Vinkki: Voit googlata apua hakusanoilla ”Eulerin polku”.

Ratkaisut voit tarkistaa täältä!

Tällaista matematiikkaa kutsutaan verkkoteoriaksi. Jos kiinostuit, voit käydä tutkimassa lisää ongelmia Mathigonin sivuilla (englanniksi): https://mathigon.org/course/graph-theory/bridges

Voit myös katsoa suomenkielisiä verkkotehtäviä Summamutikan materiaalipankista:

https://blogs.helsinki.fi/summamutikka/tag/verkot/

Vastaa

Sähköpostiosoitettasi ei julkaista.