Store norske leksikon
Artikkelstart
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.
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.
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
Broproblemet fremstilt som en graf. Hver node (blå prikk) er et landområde, og hver kant (linje) er en bro.
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
Fagansvarlig for Topologi
Kommentarer
Kommentaren din publiseres her. Fagansvarlig eller redaktør svarer når de kan.
Du må være logget inn for å kommentere.