Dei sju bruene i Königsberg

Dei sju bruene i Königsberg er eit matematisk problem innan grafteori og topologi. Den sveitsiske matematikaren Leonhard Euler viste i artikkelen Solutio problematis ad geometriam situs pertinentis i 1736 at problemet ikkje lèt seg løyse. Artikkelen hans vert ofte rekna som byrjinga på den matematiske greina grafteori.

På 1700-talet var byen Königsberg (i dag Kaliningrad) i dåverande Aust-Preussen delt inn i fire delar: den nordlege og sørlege sida av elva Pregel, som rann gjennom byen, samt to øyar midt i elva – ei mindre øy i vest og ei større øy i aust. Den minste av øyane, Kneiphof, var sentrum i byen, der mellom anna katedralen låg. Frå denne øya gjekk det to bruer til den nordlege breidda og to bruer til den sørlege breidda, samt ei bru til den største øya. Frå denne gjekk det i sin tur ei bru til den nordlege breidda og ei bru til den sørlege breidda. Totalt var dermed øyane og fastlandet knytt saman til kvarandre via sju bruer. Det vart sagt at innbyggjarane i byen på søndagsturane sine prøvde å finne ein måte å gå gjennom byen på ein slik måte at ein berre passerte kvar bru éin gong og at ein var tilbake til utgangspunktet når turen var over. Ingen hadde derfor lukkast med dette. Enkelte hevda at det var umogeleg, men ingen visste dette sikkert.

Den sveitsiske matematikaren Leonhard Euler fekk høyre om problemet med dei sju bruene i Königsberg og ønskte å løyse det. Problemet var å finne ein veg der ein passerer alle bruene nøyaktig éin gong. I 1736 viste han at det ikkje fanst noka løysing på problemet; ein slik tur er ikkje mogeleg. For å løyse problemet, formulerte Euler problemet om til ein abstrakt graf med følgjande utsjånad:

→ →

I denne grafen tilsvarar prikkane (nodane) posisjonar på nokre av øyane eller fastlandet og linjene (kantane) bruer. Euler viste at:

• om det finst fleire enn to nodar som har eit oddetal på samband, så finst det inga løysing.

Beviset er trivielt og er nok for å løyse problemet med bruene i Königsberg, anten det vert kravd at start- og sluttpunktet fell saman eller ikkje: Om eit punkt har eit oddetal på sambindingar må det vere anten start- eller sluttpunkt; elles vert ein tvungen til å gå over ei bru ein alt har gått over ein gong før for å kome derifrå siste gongen punktet vert vitja. Ein tur kan berre ha eit start- og eit sluttpunkt.

I tilfellet Königsberg har alle fire punkta eit oddetal sambindingar og det er derfor ikkje mogeleg med ei løysing her.

Utan å vise det konstaterte Euler at:

• om det finst nøyaktig to nodar med eit oddetal sambindingar, så finst dei ei løysing der turen byrjar i eitt av desse punkta og sluttar i det andre.
• om ingen node har eitt odde tal sambindingar, så går det an å finne ein tur som passerer kvar bru eksakt ein gong uansett kva punkt som er startpunkt.

Den andre påstanden vart bevist i 1873 av den tyske matematikaren Carl Hierholzer. Han viste at det finst ei løysing uansett i kva punkt ein startar og turen byrjar og sluttar i same punkt.

Til minne om Euler vert ein slik tur som passerer alle bruer eksakt ein gong kalla ein eulerveg. Om turen byrjar og sluttar i same punkt vert det kalla ein eulersirkel.

Dei sju bruene hadde under den tyske tida eigne namn. Bruene til den nordlege sida heitte Krämerbrücke, Schmiedbrücke og Holzbrücke, bruene til sørsida heitte Grünbrücke Köttelbrücke og Höhebrücke («Høgbrua»), medan brua mellom dei to øyane heitte Honigbrücke («Honningbrua»). I dag finst berre fem bruer att, og av desse to er berre Holzbrücke og Höhebrücke igjen frå Euler si tid. Honigbrücke vart erstatta i 1935 av ei ny bru, medan Schmiedbrücke og Köttelbrücke vart øydelagde under den andre verdskrigen. Dei to opphavlege vestlege bruene, Krämerbrücke og Grünbrücke, vart rivne av russarane etter krigen og erstatta av ei ny bru, noko som dermed gjorde den ønskte turen mogeleg.

• Königsbergbruene
• A visit at the bridges of Königsberg Arkivert 2012-03-19 ved Wayback Machine.