Königsbergske broproblem

Skisse som viser hvordan de sju broene knytter sammen bydelene. Problemet gikk ut på å krysse hver bro nøyaktig én gang, og ende opp tilbake der man startet. Euler beviste at problemet ikke har noen løsning.

Av /Store norske leksikon ※.

Det königsbergske broproblem er et kjent matematisk problem som regnes som et av de første problemene fra kombinatorisk topologi. Løsningen på problemet regnes som begynnelsen på fagområdet grafteori.

Problemet

I byen Königsberg (nåværende Kaliningrad) var det på 1700-tallet sju broer som knyttet sammen de forskjellige bydelene. Broproblemet gikk ut på å finne en spasertur slik at

  • alle broene ble passert nøyaktig én gang
  • man endte opp der man startet

Løsningen

Det königsbergske broproblem.

Broproblemet fremstilt som en graf. Hver node (blå prikk) er et landområde, og hver kant (linje) er en bro.

Av .

Den sveitsiske matematikeren Leonhard Euler beviste at det königsbergske broproblemet ikke har noen løsning. I 1736 løste Euler det generelle problemet å finne betingelsene for at en figur (graf) som består av linjer og knutepunkter, kan tegnes i et sammenhengende drag slik at hver linje gjennomløpes bare én gang og man kommer tilbake til utgangspunktet. Betingelsene er at figuren må være sammenhengende, og at det i alle knutepunkter (noder) er et like antall linjer som møtes. Den siste betingelsen kan formuleres som at hvert knutepunkt har partallsgrad.

Illustrasjonen viser at alle de fire knutepunktene i grafen som tilsvarer det königsbergske broproblemet, har oddetallsgrad, og problemet har følgelig ingen løsning.

Eulers løsning var begynnelsen på den grenen av topologien som kalles grafteori.

Les mer i Store norske leksikon

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

Du må være logget inn for å kommentere.

eller registrer deg