AlegsaOnline.com

Sedem königsberških mostov: Eulerjev problem in začetek teorije grafov

Eulerjev problem sedmih königsberških mostov: Eulerova rešitev (1735), rojstvo teorije grafov in začetki topologije — zgodovinski vpogled v matematični preobrat.

Avtor: Leandro Alegsa Datum ustvarjanja: 05. april 2022 Zadnja posodobitev: 18. december 2025

simple.wikipedia.org · CC BY-SA 3.0

Sedem königsberških mostov je zgodovinsko znan matematični problem. Leonhard Euler ga je rešil leta 1735. To je vodilo k začetku teorije grafov. Ta je nato privedla do razvoja topologije ter pozneje tudi številnih praktičnih aplikacij v znanosti in tehnologiji.

Mesto Königsberg v Prusiji (danes Kaliningrad v Rusiji) je bilo postavljeno na obeh straneh reke Pregel. Obsegalo je dva velika otoka, ki sta bila med seboj in s celino povezana s sedmimi mostovi.

Problem je bil najti način, kako se sprehoditi skozi mesto tako, da vsak most prečkamo enkrat in samo enkrat. Do otokov ni bilo mogoče priti drugače kot po mostovih. Vsak most je bilo treba vsakič v celoti prečkati. Sprehoda ni bilo treba začeti in končati na istem mestu. Euler je dokazal, da problem nima rešitve.

Eulerjev pristop in poenostavitev problema

Euler je problem poenostavil tako, da je dejanske oblike otokov in mostov nadomestil z abstraktno shemo: vsako prebivališče (otok ali obala) je predstavil kot vozel (to, kar danes imenujemo vozlišče ali vrh grafa), vsak most pa kot povezavo med dvema vozliščema (to je rob grafa). Tako je konkretni zemljepisni problem preoblikoval v matematični problem o grafih.

Ključni argument (poenostavljen dokaz)

Osnovno opažanje je naslednje:

Če med sprehodom prispemo v neko vozlišče in ga zapustimo (tj. vozlišče nismo izbrali kot začetek ali konec poti), potem se v tem vozlišču uporabi par robov: en rob za vstop in en rob za izstop.
To pomeni, da mora imeti vsako takšno vmesno vozlišče sodo stopnjo (število robov, ki izhajajo iz njega), ker so robovi uporabljeni v parih.
Za začetek in konec sprehoda je mogoče imeti največ dve vozlišči, ki imata neparno stopnjo — torej je dovoljeno imeti 0 ali 2 vozlišča z neparnimi stopnjami, če želimo poti, ki preidejo vsak rob natanko enkrat.

Ker je v primeru Königsberga graf s štirimi vozlišči in sedmimi robovi oblikovan tako, da so bila vsa štiri vozlišča neparne stopnje, Euler zaključi, da taka pot ne more obstajati (število neparnih vozlišč ne sme presegati 2). Torej rešitve problema ni.

Formalna definicija in posledice

Eulerjeva pot (Eulerian trail): pot v grafu, ki obišče vsak rob natanko enkrat. Obstaja natanko takrat, ko ima graf 0 ali 2 vozlišča z neparno stopnjo in je graf povezan (upoštevajoč robove z nenulnimi stopnjami).
Eulerjev cikel (Eulerian circuit): Eulerjeva pot, ki se začne in konča v istem vozlišču. Obstaja natanko takrat, ko ima graf 0 vozlišč z neparno stopnjo (torej vse stopnje so sode) in je povezan.

Pomen za matematiko in prakso

Eulerjev članek o königsberških mostovih velja za eno prvih objav v katerem se sistematično uporablja abstraktna reprezentacija problemov z vozlišči in povezavami — tako se je uradno rodila teorija grafov. Iz tega so se razvile številne veje matematike in računalništva:

Topologija in teorija omrežij
Algoritmi za iskanje Eulerjevih poti in ciklov (pomembno v računalniških aplikacijah)
Praktične naloge, kot so načrtovanje poti za pobiralce pošte, čiščenje ulic, načrtovanje električnih omrežij in optimizacija transporta
Sodobne uporabe v biologiji (npr. sestavljanje genomov iz kratkih odsekov DNA), v telekomunikacijah in pri analizi družbenih omrežij

Kaj se lahko iz tega naučimo

Primer königsberških mostov je lep uvod v razumevanje, kako abstraktne matematične ideje (grafi, stopnje vozlišč, parnost) pomagajo rešiti na videz vsakdanje probleme. Z enostavnim opazovanjem lastnosti grafov je Euler pokazal, da obstajajo vprašanja, za katera je mogoče dokončno dokazati, da rešitev ne obstaja — in hkrati odprl novo področje, ki je postalo ključno za sodobno znanost in tehnologijo.

Zemljevid Königsberga v Eulerjevem času, ki prikazuje dejansko postavitev sedmih mostov, s poudarkom na reki Pregel in mostovih

Eulerjeva analiza

Euler je najprej poudaril, da izbira poti znotraj vsake kopenske mase ni pomembna. Edina pomembna lastnost poti je vrstni red prečkanja mostov. Zato je problem spremenil v abstraktne izraze. S tem je postavil temelje teorije grafov. Odstranil je vse lastnosti razen seznama kopenskih mas in mostov, ki jih povezujejo. V jeziku teorije grafov je vsako kopno nadomestil z abstraktnim "vrhom" ali vozliščem. Nato je vsak most nadomestil z abstraktno povezavo, "robom". Rob (cesta) je zabeležil, katera dva vrhova (kopna območja) sta bila povezana. Na ta način je oblikoval graf.

→ →

Narisani graf je abstraktna slika problema. Zato lahko robove poljubno povežemo. Pomembno je le, ali sta dve točki povezani ali ne. Sprememba slike grafa ne spremeni grafa samega.

Nato je Euler opazil, da (razen na končnih točkah sprehoda), kadar koli vstopimo v vrh z mostom, ga tudi zapustimo z mostom. Pri vsakem sprehodu po grafu je število vstopov v vrh enako številu izstopov iz njega. Če je bil vsak most prečkan natanko enkrat, iz tega sledi, da mora biti število mostov, ki se dotikajo vsake zemeljske mase (razen tistih, izbranih za začetek in cilj), parno. Če je namreč mostov n, je zemljišče prečkano natanko 2n-krat. Vendar se vseh štirih kopenskih mas v prvotni nalogi dotika liho število mostov (ene se dotika 5 mostov, vsake od preostalih treh pa po 3 mostovi). Obstajata največ dve masi, ki sta lahko končni točki sprehoda. Zato predlog, da sprehod vsak most prečka enkrat, vodi v protislovje.

V sodobnem jeziku Euler pokaže, da je to, ali je sprehod po grafu, ki vsak rob prečka enkrat, mogoč ali ne, odvisno od stopenj vozlišč. Stopnja vozlišča je število robov, ki se ga dotikajo. Euler pokaže, da je nujni pogoj za sprehod, da je graf povezan in ima natanko nič ali dve vozlišči lihe stopnje. Ta Eulerjev rezultat je pozneje dokazal Carl Hierholzer. Takšna hoja se zdaj imenuje Eulerjeva pot ali Eulerjeva hoja. Če obstajajo vozlišča lihe stopnje, se bo vsaka Eulerjeva pot začela pri enem od njih in končala pri drugem. Ker ima graf, ki predstavlja zgodovinski Königsberg, štiri vozlišča lihe stopnje, ne more imeti Eulerjeve poti.

Eulerjevo delo je bilo 26. avgusta 1735 predstavljeno Akademiji v Sankt Peterburgu. Objavljeno je bilo kot Solutio problematis ad geometriam situs pertinentis (Rešitev problema, ki se nanaša na geometrijo položaja) v reviji Commentarii academiae scientiarum Petropolitanae leta 1741. V angleščini je na voljo v zbirki The World of Mathematics.

Pomen v zgodovini matematike

V zgodovini matematike velja Eulerjeva rešitev problema königsberškega mostu za prvi izrek teorije grafov. Teorija grafov je predmet, ki se zdaj na splošno obravnava kot veja kombinatorike.

Sedanje stanje mostov

Dva od sedmih prvotnih mostov sta bila uničena med bombardiranjem Königsberga v drugi svetovni vojni. Dva mostova sta bila pozneje porušena. Nadomestila ju je sodobna avtocesta. Ostali trije mostovi so ostali, čeprav sta le dva iz Eulerjevega časa (eden je bil obnovljen leta 1935). Tako je bilo leta 2000 v Kaliningradu pet mostov.

Po teoriji grafov imata zdaj dve vozlišči stopnjo 2, drugi dve pa stopnjo 3. Eulerjeva pot je zdaj mogoča, vendar je za turiste nepraktična, saj se mora začeti na enem otoku in končati na drugem.

Sorodne strani

Ikozijska igra
Hamiltonova pot
Voda, plin in elektrika
Problem potujočega prodajalca

Vprašanja in odgovori

V: Kaj je problem sedmih mostov v Königsbergu?

O: Sedem königsberških mostov je znan matematični problem, ki vključuje iskanje načina, kako se sprehoditi skozi mesto tako, da vsakega od sedmih mostov prečkamo enkrat in samo enkrat.

V: Kdo je rešil problem sedmih mostov v Königsbergu?

O: Leonhard Euler je leta 1735 rešil problem sedmih mostov v Königsbergu.

V: Do česa je pripeljala rešitev problema sedmih mostov v Königsbergu?

O: Rešitev problema sedmih mostov v Königsbergu je pripeljala do začetka teorije grafov, ki je nato pripeljala do razvoja topologije.

V: Kje se nahaja Königsberg?

O: Königsberg leži v Prusiji, ki je zdaj del Kaliningrada v Rusiji.

V: Kakšna je bila razporeditev Königsberga?

O: Königsberg je bil postavljen na obeh straneh reke Pregel in je vključeval dva velika otoka, ki sta bila med seboj in s celino povezana s sedmimi mostovi.

V: Kakšne so bile zahteve za rešitev problema sedmih mostov v Königsbergu?

O: Problem je zahteval najti način, kako se sprehoditi skozi mesto tako, da vsak most prečkamo enkrat in samo enkrat, pri čemer je treba vsakič v celoti prečkati vsak most. Do otokov ni bilo mogoče priti po nobeni drugi poti kot po mostovih, sprehoda pa ni bilo treba začeti in končati na istem mestu.

V: Ali je Euler dokazal, da ima problem sedmih mostov v Königsbergu rešitev?

O: Ne, Euler je dokazal, da problem sedmih mostov v Königsbergu nima rešitve.