Problem Koenigsberških mostov

Iz MaFiRaWiki

V 18. stoletju je bilo v srednjeveškem mestu Königsberg v Vzhodni Prusiji sedem mostov, ki so povezovali štiri dele mesta. Na reki Pregel je bil otok, imenoven Kneiphof. Reka se je, kot kaže slika, razcepila v dva rokava. Pravijo, da so se meščani zabavali s poskušanjem, ali bo komu uspelo sprehoditi se po mestu tako, da bo prečkal vsakega od mostov natanko enkrat in se vrnil na začetno točko.

image:euler1.jpg

Meščani so zaman znova in znova poskušali najti obhod mesta, ki bi prečkal vsakega od mostov natanko enkrat in se vrnil v izhodišče, in so začeli verjeti, da naloga nima rešitve. Dokazati tega ni znal nihče, vse dokler se problema ni lotil Leonard Euler. Eulerjev dokaz je bil objavljen leta 1736 v članku z naslovom Solutio problematis ad geometriam situs pertinensis.

Na problem königberških mostov lahko pogledamo kot na problem iz teorije grafov, pri čemer so vozlišča štirje deli mesta, povezave grafa pa sedem mostov na reki. Problem iskanja obhoda grafa , pri katerem "prehodimo" vsako povezavo natanko enkrat imenujemo iskanje Eulerjevega obhoda v tem grafu.

Euler v članku ni obravnaval samo problem königsberških mostov, ampak se je lotil tudi bolj splošnih porazdelitev delov mesta in mostov. Ideje, ki jih je uporabil so zelo blizu idejam teorije grafov, zato Eulerjev članek (čeprav ni napisan v takem jeziku) štejemo za prvi članek teorije grafov.

Glej tudi

Osebna orodja