Sedem königsberških mostov
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.
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.
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.
