Königsbergs sju broar
Under lång tid på 1700-talet försökte människorna i staden Königsberg lösa en gåta: genom staden rinner floden Pregel, som bildar två öar. Över floden går sammanlagt sju broar till öarna. Är det möjligt att under en enda söndagspromenad gå över alla broar, men varje bro exakt en gång? Titta på hur broarna över floden låg:
Är det möjligt att börja vår promenad på någon plats och gå över alla broar exakt en gång? Vi kan försöka, vi börjar längst ned till vänster och går uppåt och sedan stegvis åt höger, så här:
Vi ser att vi har gått över sex av sju broar, en av broarna missade vi. Vi kan prova en annan väg…
Återigen har vi gått över bara sex av sju broar i vårt Königsberg. Det ser nästan ut som att det inte går att gå över varje bro exakt en gång under en promenad. En dag stötte den kände matematikern Leonhard Euler på problemet. Känd är dessutom en underdrift — Euler var en riktig legend inom matematiken, och efter honom är till och med Eulers tal uppkallat. Euler bestämde sig för att knäcka gåtan. Han började med att markera de olika öarna, eller delarna av staden, som broarna ledde till och från:
Euler förde nu följande resonemang: om det leder ett jämnt antal broar till en ö kan vi gå över de broarna under en promenad, oavsett var vi börjar. Vi kommer helt enkelt till ön över en bro och lämnar den över en annan — antalet broar som återstår att gå över har minskat med två. För att kunna komma till ön över en bro och lämna den över en annan behöver vi två broar. Om det leder sex broar till en ö besöker vi ön tre gånger. Låt oss till exempel tänka oss att fyra broar ledde till ö B så här:
Då kan vi under en söndagspromenad gå över alla broar, oavsett var vi börjar. Prova själv! I figuren har jag markerat en väg. Låt oss nu tänka oss att det också ledde en bro till ö B från ö D:
Vi ser att vägen som vi valde inte låter oss gå över alla broar exakt en gång. Vi skulle behöva gå tillbaka till ö B över någon bro och sedan gå över till ö D. Men vi kan välja en annan väg. Vi kan börja vår promenad på ö B och sedan kan vi gå över alla broar exakt en gång:
Vi började vår promenad på ö B, gick uppåt till område A, sedan över en bro tillbaka till B, till område C, sedan tillbaka till ö B och till sist till ö D. Om vi alltså börjar på en ö som har ett udda antal broar kan vi gå över alla dess broar exakt en gång. Eller så kan vi gå helt tvärtom — vi kan börja på ö D och sluta på ö B.
Euler lade alltså märke till att för att det ska vara möjligt att gå över alla broar exakt en gång måste antingen alla öar ha ett jämnt antal broar, eller så får det finnas två öar som har ett udda antal broar — på den ena ön med ett udda antal broar börjar vi och på den andra slutar vi. Alla övriga öar måste ha ett jämnt antal broar. Om vi tittar på de ursprungliga sju broarna i Königsberg:
ser vi att varje ö har ett udda antal broar! Ö A har 3, B har 5, C har 3 och D har också 3. Därför har gåtan ingen lösning — det är inte möjligt att gå över alla sju broar exakt en gång under en söndagspromenad. Om vi rev vilken som helst av broarna skulle gåtan plötsligt ha en lösning. Låt oss till exempel riva en av broarna mellan ö B och C:
Vi ser att ö B plötsligt har 4 broar och ö C två broar. För öarna A och D ändrades antalet broar inte. Vi har plötsligt två öar med ett jämnt antal broar och två öar med ett udda antal broar. Om vi börjar promenaden på en av öarna som har ett udda antal broar kan vi gå över alla broar exakt en gång. I figuren började vi på ö A och slutade på ö D.
Leonhard Euler löste därmed ännu ett berömt matematiskt problem och lade mer eller mindre grunden till det vi i dag kallar grafteori, och till hans ära kallas en väg i en graf som går längs alla kanter exakt en gång, i grafteorins språk, för en eulerstig.
