De syv broer i Königsberg
I 1700-tallet brugte folk i byen Königsberg lang tid på at løse en gåde: floden Pregel løber gennem byen og danner to øer. Over floden fører i alt syv broer til øerne. Er det muligt på en enkelt søndagstur at gå over alle broerne, men hver bro præcis én gang? Lad os se på, hvordan broerne lå over floden:
Er det muligt at starte vores tur et sted og gå over alle broerne præcis én gang? Vi kan prøve, vi starter nederst til venstre og går opad og så efterhånden mod højre, sådan her:
Vi ser, at vi har gået over seks af de syv broer, og at vi har sprunget én bro over. Vi kan prøve en anden rute …
Igen har vi kun gået over seks af de syv broer i vores Königsberg. Det ser næsten ud til, at det ikke er muligt at gå over hver bro præcis én gang på en enkelt tur. En dag stødte den kendte matematiker Leonhard Euler på dette problem. Kendt er næsten for lidt sagt — Euler var en regulær legende i matematikken, og efter ham er der endda opkaldt Eulers tal. Euler besluttede sig for at knække denne gåde. Han begyndte med at betegne de enkelte øer eller dele af byen, som broerne førte til og fra:
Euler gjorde nu følgende overvejelse: hvis der fører et lige antal broer til en ø, kan vi gå over disse broer på en enkelt tur, uanset hvor vi starter. Kort sagt, over den ene bro kommer vi til øen, over den anden forlader vi den — antallet af broer, der endnu mangler at blive gået over, er faldet med to. For at kunne komme til øen over den ene bro og forlade den over den anden skal vi bruge to broer. Hvis der fører seks broer til en ø, besøger vi øen tre gange. Forestil dig for eksempel, at der førte fire broer til ø B sådan her:
Så kan vi på en enkelt søndagstur gå over alle broerne, uanset hvor vi starter. Prøv det selv! På figuren har jeg markeret én rute. Forestil dig nu, at der også førte en bro til ø B fra ø D:
Vi ser, at den rute, vi valgte, ikke lader os gå over alle broerne præcis én gang. Vi ville være nødt til at vende tilbage til ø B over en af broerne og så gå videre til ø D. Men vi kan vælge en anden rute. Vi kan starte vores tur på ø B, og så kan vi gå over alle broerne præcis én gang:
Vi startede vores tur på ø B, gik op til område A, så over broen tilbage til B, til område C, så igen tilbage til ø B og til sidst til ø D. Hvis vi altså starter på en ø med et ulige antal broer, kan vi gå over alle dens broer præcis én gang. Eller vi kan gå helt omvendt — vi kan starte på ø D og slutte på ø B.
Euler lagde således mærke til, at for at det er muligt at gå over alle broerne præcis én gang, skal enten alle øer have et lige antal broer, eller også kan der være to øer, som har et ulige antal broer — på den ene ø med et ulige antal broer starter vi, og på den anden slutter vi. Alle de øvrige øer skal have et lige antal broer. Hvis vi ser på de oprindelige syv broer i Königsberg:
så ser vi, at hver ø har et ulige antal broer! Ø A har 3, B har 5, C har 3, og D har også 3. Derfor har gåden ingen løsning — det er ikke muligt at gå over alle syv broer præcis én gang på en enkelt søndagstur. Hvis vi nedrev en vilkårlig af broerne, ville gåden pludselig have en løsning. Lad os for eksempel nedrive en af broerne mellem ø B og C:
Vi ser, at ø B nu med ét har 4 broer og ø C to broer. For øerne A og D er antallet af broer uændret. Vi har pludselig to øer med et lige antal broer og to øer med et ulige antal broer. Hvis vi starter vores tur på en af de øer, der har et ulige antal broer, kan vi gå over alle broerne præcis én gang. På figuren startede vi på ø A og sluttede på ø D.
Leonhard Euler løste således endnu et berømt matematisk problem og lagde mere eller mindre grunden til det, vi i dag kalder grafteori, og til ære for ham kaldes en graf, hvor man kan gå gennem alle kanter præcis én gang, i grafteoriens sprog for en Eulergraf.
