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
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
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.
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.