Königsbergi sildade probleem

Königsbergi seitse silda on ajalooliselt kuulus matemaatikaprobleem. Leonhard Euler lahendas selle probleemi 1735. aastal. See tõi kaasa graafiteooria alguse. See viis seejärel topoloogia arenguni.

Königsbergi linn Preisimaal (praegu Kaliningrad, Venemaa) asus mõlemal pool Pregeli jõge. See hõlmas kahte suurt saart, mis olid omavahel ja mandriga ühendatud seitsme sillaga.

Probleem oli leida viis, kuidas kõndida läbi linna, ületades iga silda üks kord ja ainult üks kord. Saartele ei olnud võimalik jõuda muudel marsruutidel kui sildade kaudu. Iga sild tuli iga kord täielikult ületada. Jalutuskäik ei pidanud algama ja lõppema samas kohas. Euler tõestas, et probleemil ei ole lahendust.

Königsbergi kaart Euleri ajal, millel on kujutatud seitsme silla tegelik paigutus, esile tõstetud Pregeli jõgi ja sillad.Zoom
Königsbergi kaart Euleri ajal, millel on kujutatud seitsme silla tegelik paigutus, esile tõstetud Pregeli jõgi ja sillad.

Euleri analüüs

Esiteks märkis Euler, et marsruudi valik iga maamassi sees ei ole oluline. Marsruudi ainus oluline omadus on sildade ületamise järjekord. Seega muutis ta probleemi abstraktseks. See pani aluse graafiteooriale. Ta eemaldas kõik omadused, välja arvatud maamasside ja neid ühendavate sildade loetelu. Graafiteooria keeles asendas ta iga maamassi abstraktse "tipu" või sõlme. Seejärel asendas ta iga silla abstraktse ühendusega, "servaga". Serva (tee) abil registreeriti, millised kaks tippu (maamassiivid) olid omavahel ühendatud. Sel viisil moodustas ta graafi.

→ →

Joonistatud graafik on probleemi abstraktne pilt. Seega võib servi ühendada mis tahes viisil. Oluline on ainult see, kas kaks punkti on ühendatud või mitte. Graafi pildi muutmine ei muuda graafi ennast.

Seejärel täheldas Euler, et (välja arvatud kõndimise lõpp-punktides) alati, kui sisenetakse tippu silla kaudu, lahkutakse sellest tipust silla kaudu. Igasuguse graafi kõndimise korral on tippu sisenemise kordade arv võrdne sellest väljumise kordade arvuga. Kui iga sild on läbitud täpselt üks kord, siis järeldub, et iga maismaamassiivi puhul (välja arvatud algus- ja lõpp-punktiks valitud sildade puhul) peab seda maismaamassiivi puudutavate sildade arv olema paariline. See tuleneb sellest, et kui on n silda, siis ületatakse seda täpselt 2n korda. Siiski puudutab kõiki nelja algse probleemi maamassiivi paaritu arv sildasid (ühte puutub kokku 5 silda ja ülejäänud kolme silda 3). On maksimaalselt kaks massiivi, mis võivad olla jalutuskäigu lõpp-punktid. Seega toob väide, et jalutuskäik läbib iga silda üks kord, kaasa vastuolu.

Tänapäevases keeles näitab Euler, et see, kas iga serva üks kord ületav käik läbi graafi on võimalik või mitte, sõltub sõlmede astmetest. Sõlme aste on seda puudutavate servade arv. Euler näitab, et jalutuskäigu vajalik tingimus on, et graaf oleks seotud ja et selles oleks täpselt null või kaks paaritu astme sõlme. Selle Euleri poolt esitatud tulemuse tõestas hiljem Carl Hierholzer. Sellist käiku nimetatakse nüüd Euleri rajaks või Euleri käiguks. Kui on olemas paaritu astme sõlmed, siis algab iga Euleri rada ühes neist ja lõpeb teises. Kuna ajaloolise Königsbergi graafil on neli paaritu astme sõlme, ei saa sellel olla Euleri rada.

Euleri töö esitati Peterburi akadeemiale 26. augustil 1735. aastal. See avaldati 1741. aastal ajakirjas Commentarii academiae scientiarum Petropolitanae kui Solutio problematis ad geometriam situs pertinentis (Asukoha geomeetriaga seotud probleemi lahendus). See on inglise keeles kättesaadav ajakirjas The World of Mathematics.

Tähtsus matemaatika ajaloos

Matemaatika ajaloos peetakse Euleri Königsbergi silla probleemi lahendust esimeseks graafiteooria teoreemiks. Graafiteooria on teema, mida praegu peetakse üldiselt kombinatoorika haruks.

Sildade praegune seisukord

Seitse algset silda hävitati Königsbergi pommitamise ajal Teises maailmasõjas. Kaks ülejäänud lammutati hiljem. Need asendati kaasaegse maanteega. Ülejäänud kolm silda on säilinud, kuigi ainult kaks neist pärinevad Euleri ajast (üks ehitati ümber 1935. aastal). Seega oli 2000. aasta seisuga Kaliningradis viis silda.

Graafiteooria seisukohalt on nüüd kahel sõlmpunktil aste 2 ja kahel teisel 3. Seega on nüüd võimalik Euleri tee, kuid kuna see peab algama ühelt saarelt ja lõppema teisel saarel, on see turistide jaoks ebapraktiline.

Seotud leheküljed

Küsimused ja vastused

K: Mis on Königsbergi seitsme silla probleem?


V: Königsbergi seitse silda on kuulus matemaatiline probleem, mis seisneb selles, et tuleb leida viis, kuidas läbida linn, ületades iga seitsme silla üks kord ja ainult üks kord.

K: Kes lahendas Königsbergi seitsme silla probleemi?


V: Leonhard Euler lahendas Königsbergi seitsme silla probleemi 1735. aastal.

K: Milleks viis Königsbergi seitsme silla probleemi lahendamine?


V: Königsbergi seitsme silla probleemi lahendamine viis graafiteooria alguseni, mis omakorda viis topoloogia arenguni.

K: Kus asub Königsberg?


V: Königsberg asub Preisimaal, mis praegu on osa Kaliningradist Venemaal.

K: Milline oli Königsbergi linna plaan?


V: Königsberg paiknes mõlemal pool Pregeli jõge ja hõlmas kahte suurt saart, mis olid omavahel ja mandriga ühendatud seitsme sillaga.

K: Millised olid nõuded Königsbergi seitsme silla probleemi lahendamiseks?


V: Probleemi lahendamiseks tuli leida viis, kuidas läbida linn, ületades iga silda üks kord ja ainult üks kord, kusjuures iga sild tuli iga kord täielikult ületada. Saartele ei tohtinud jõuda muudel marsruutidel kui sildade kaudu ning jalutuskäik ei pidanud algama ja lõppema samas kohas.

Küsimus: Kas Euler tõestas, et Königsbergi seitsme silla probleemil on lahendus?


V: Ei, Euler tõestas, et Königsbergi seitsme silla probleemil ei ole lahendust.

AlegsaOnline.com - 2020 / 2023 - License CC3