Hopp til hovedinnholdet
www.matematikk.org

Broene i Königsberg

Det viser seg at det kan finnes mye matematikk i det å kunne krysse broer på en bestemt måte! Problemet 'Broene i Kønigsberg' var opptakten til mye ny matematikk.

Byen Königsberg ble grunnlagt på 1200-tallet av Den tyske orden og ligger ved Østersjøen mellom dagens Litauen og Polen. De prøyssiske kongene ble kronet her, og byen var hovedstad i øst-Preussen. Königsberg ble russisk i 1945 og heter i dag Kaliningrad etter Sovjetunionens statssjef under Den andre verdenskrig.

Elven Pregel (dagens Pregolja) rant gjennom Kønigsberg og forgrenet seg slik at den lagde ei øy i byen. Syv broer gikk over elven som vist på dette bildet:

 

Figur : De 7 broene i Königsberg.

Innbyggerne i Königsberg gikk mange turer over broene, og det berømte problemet var om det var mulig å gå Turen med stor t, nemlig en tur gjennom byen der man krysset hver av de syv broene nøyaktig en gang. Det var matematikeren Leonard Euler som løste dette i 1736, og som samtidig startet det som i dag kalles grafteori.

Vi kan tegne broene i Königsberg litt mer skjematisk:

 

 

Figur 3: Eulers forenkling av broene og øyene.

Vi ser at elven deler byen i fire adskilte landområder. Euler så på disse områdene som punkter som skal besøkes, og broene som veier mellom punktene:

Her har vi altså strukket broene og presset sammen landområdene. Dette er operasjoner som hører hjemme i topologien, og Eulers arbeid på broene i Königsberg regnes også som starten på topologien, som er et stort felt innenfor matematikken i dag. Topologene studerer egenskaper ved ulike figurer (eller former) som ikke forandres selv om vi presser sammen eller strekker figurene (slik som vi nettopp har gjort med Königsberg).

Går vi et skritt videre med tegningen vår, blir broene i Kønigsberg et eksempel på en graf (en annen bruk av ordet graf, som også brukes om tegningen av en funksjon):

 

Figur 4: Nok en forenkling gjør at vi kan se på broene i Königsberg som et eksempel på en graf.

En graf (et nettverk) er en figur som består av punkter (kalles grafens topper) og linjer eller kurver (kalles grafens kanter) mellom punktene. Toppene i grafen vår har vi kalt A, B, C og D. Problemet om vi kan gå Turen kan nå reformuleres: Kan vi følge grafen i tegningen slik at hver av kantene følges nøyaktig en gang? Vi forkorter dette til å spørre om grafen vår har en "eulervei". Ved å bruke grafteori viste Euler at grafen ikke har noen eulervei, det vil si at vi ikke kan følge grafen slik at hver av kantene følges nøyaktig en gang, og dermed er Turen umulig.

Euler observerte at hvis vi prøver å finne en eulervei og besøker en topp, må vi følge en kant når vi kommer inn til toppen og en annen kant ut. Det vil si at hvis vi skal ha en eulervei der vi starter og slutter på samme topp, må vi ha et like antall kanter som kommer inn til hver topp. Vi sier at alle toppene må ha et like antall kanter. Hvis vi skal ha en eulervei der vi starter og slutter på forskjellige topper, kan imidlertid start- og slutt-toppen ha et odde antall kanter. I denne situasjonen må grafen altså ha topper der høyst to av dem har et odde antall kanter og resten har et like antall.

I grafen vår har toppene A, C og D tre kanter hver mens topp B har fem. Altså har alle toppene et odde antall kanter, og ved Eulers observasjoner har den ingen eulervei.

Hva hvis vi tegner noen andre grafer? Har for eksempel grafene nedenfor en eulervei?

 

Figur 5: Har disse grafene en Euler-vei?

Her kommer litt mer grafteori:

En graf er et matematisk objekt på lik linje med at et tall er et matematisk objekt. Matematikere studerer slike objekter ved å se på egenskapene til de ulike objektene. Egenskaper ved et tall er om det er positivt, et oddetall, delelig med tallet 3 osv. La oss se litt på noen av egenskapene til en graf:

  • Sammenhengende graf: Alle par av topper har en kant som forbinder dem. De fleste mener "sammenhengende graf" når de sier "graf". Det gjør vi også.
  • Størrelsen på en graf: Antall topper på grafen.
  • Graden til en topp: Antall kanter toppen har.
  • Avstanden mellom to topper: Det minste antall kanter du må følge for å komme fra den ene toppen til den andre.
  • Diameteren til en graf: Avstanden mellom de to toppene på grafen som ligger lengst fra hverandre.

En graf kalles n-regulær hvis alle toppene har grad n. Hva er den minste størrelsen en 4-regulær graf med diameter 2 kan ha?

Grafteori er et stort felt med mange dype resultater. Og det kan anvendes: Grafer kan for eksempel modellere elektriske kretser på en mikrobrikke eller hvordan datamaskiner er forbundet via telefonlinjer og satelitter. Da blir slike spørsmål som vi nettopp har stilt viktige.

Grafteori er et typisk eksempel der vi starter med et reelt problem og utvikler en teori som viser seg å ha mange anvendelser. Mange samarbeidsprosjekter som involverer matematikere fungerer på denne måten: Folk har et problem og spør en matematiker om han/hun kan løse det. Eller matematikeren har utviklet en teori og prøver å finne et problem som teorien kan anvendes på. Et eksempel på det sistnevnte er tallteori. Tallteori ble utviklet fra problemer man støtte på innenfor matematikken, og ikke i dagliglivet. Men resultater herfra har vist seg å ha store anvendelser, for eksempel innenfor kryptologi (koding og dekoding). De såkalte "samarbeidsprosjektene" kan imidlertid ofte gå over flere århundrer...

Del på Facebook

Del på Facebook

Skrevet av

Inger Christin Borge
Inger Christin Borge

Institusjon

Universitetet i Oslo

Begrep

  • Topologi

    Topologi

    Et felt i matematikk som studerer egenskaper ved figurer og flater som er uavhengig av kontinuerlige forandringer av størrelse og form.

    Illustrasjonen er fra Wikimedia commons.

Omtalt person

Hopp over bunnteksten