Königsbergi seitse silda: Euleri lahendus ja graafiteooria algus

Avasta Königsbergi seitse silda: Euleri 1735 tõestus, klassikaline matemaatikaprobleem, mis sünnitas graafiteooria ja mõjutas topoloogiat — selge ja kaasahaarav ülevaade.

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.

Probleemi lihtsustamine ja modelleerimine

Euleri olulisim samm oli näha, et konkreetset kaartkujutist pole vaja — tähtis on ainult see, kuidas maalapid (saared ja kaldad) on omavahel ühendatud. Ta asendas iga maaaluse piirkonna tippu (vertex) ja iga silda servaks (edge). Selline abstraktne mudel on tänapäeval tuntud kui graaf.

Tähelepanuväärne on, et probleem muutus geomeetrilisest korduvate käimiste loendamisest lihtsaks pariteedi- ehk paarisarvuküsimuseks: iga kord, kui jalutaja silda ületab, ta siseneb ühte tippu ja väljub teisest — seega enamikul tippudel tuleb tulla ja minna paarisarv kordi.

Euleri argumendi tuum (lühiülevaade)

Euler näitas, et selline jalutuskäik (mida nüüd nimetatakse Euleri trajektooriks või Euleri teeks) on võimalik ainult siis, kui graafil on kas:

kõik tipud on paarilise astmega (siis saab algusest lõppu tagasi jõuda; see nimetatakse Euleri tsükliks), või
täpselt kaks tippu on paaritu astmega (siis algab tee ühes paaritu astmega tipust ja lõpeb teises; see annab Euleri trajektoori, mis ei pea kokku tulema).

Selle põhjendus on lihtne: kui tipp pole tee algus ega lõpp, siis iga sisenemine sinna tuleb tasakaalustada väljumisega — sisenemiste ja väljumiste arv on paaris. Seega tippudel, mis ei ole algus ega lõpp, peab olema paarisarv servasid. Kui aga rohkem kui kaks tippu on paaritud, ei ole võimalik sellist paari-sobitamist teha ja Euleri trajektoori ei leidu.

Kõige tähtsam: Königsbergi graafis oli rohkem kui kaks paaritu astmega tippu, seega võis Euler kohe järeldada, et nõutud jalutuskäiku ei eksisteeri.

Miks see on tähtis

Kuigi probleem ise oli lihtne ja konkreetne, oli Euleri lähenemine revolutsiooniline — ta näitas, et mõnikord ei ole vaja uurida joonise detaile, vaid piisab struktuurilisest analüüsist. See idee kujundas aluse graafiteooriale, mis on nüüd hulga teoreetiliste ja praktiliste rakendustega (võrgud, transpordiprobleemid, keemia, arvutiteadus jpm), ning mõjutas ka topoloogia arengut, kus uuritakse ruumi omadusi, mis püsivad läbi pidevate teisenduste.

Edasine areng ja terminoloogia

Pärast Euleri tööd sai selliseid teid hakata nimetama Euleri trajektoorideks ja Euleri tsükliteks. Tingimused tipu astmete (degree) paarisuse kohta on tänaseni graafiteooria põhiteoreemide hulgas ja moodustavad standardse tööriista paljude võrgupõhiste probleemide lahendamisel.

Lõpuks tasub märkida, et kuigi algsetes kaartides olevad sillad on ajalooliselt muutunud, jääb Königsbergi näide oluliseks õppetunniks: lihtsate näidete kaudu võivad sündida uued matemaatika harud.

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

Icosian mäng
Hamiltoni tee
Vesi, gaas ja elekter
Reisijate müügimehe probleem

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.