Det königsbergske broproblem, kjent matematisk problem, et av de første problemer fra den såkalte kombinatoriske topologi. I byen Königsberg (Kaliningrad) var det på 1700-tallet sju broer som knyttet sammen de forskjellige bydeler, og broproblemet gikk ut på å legge en spasertur på en slik måte at alle broene ble passert nøyaktig én gang, og slik at man endte opp der man startet. L. Euler beviste at dette er umulig.

Euler løste i 1736 det generelle problem å 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 (dvs. at hvert knutepunkt har partallsgrad). Eulers løsning var begynnelsen på den gren av topologien som kalles grafteori. Vi ser at alle de fire knutepunktene i grafen som tilsvarer det königsbergske broproblemet, har oddetallsgrad, og problemet har følgelig ingen løsning.

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål til artikkelen? Skriv her, så får du svar fra fagansvarlig eller redaktør.

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