Det königsbergske broproblem er et kjent matematisk problem som regnes som et av de første problemene fra kombinatorisk topologi.

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 som gjorde at alle broene ble passert nøyaktig én gang, og man endte opp der man startet. 

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

Det königsbergske broproblem. av Riojajar~commonswiki. Gjengitt med tillatelse

Den sveitsiske matematikeren Leonhard Euler beviste at det königsbergske broproblem 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

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål om eller kommentarer til artikkelen?

Kommentaren din vil bli publisert under artikkelen, og fagansvarlig eller redaktør vil svare når de har mulighet.

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