Grafteori: Eulervei og Hamiltonsti

Hva er Königsbergs broer?

De syv broene i Königsberg er et klassisk problem i grafteori.

Königsberg (dagens Kalingrad) hadde syv broer over elven Pregel som delte og samlet seg flere ganger. Spørsmålet er om det er mulig å gå en tur der man krysser alle broene nøyaktig en gang.

Problemet kan modelleres med en graf der landområdene er noder og broene er kanter:

Finnes det en Eulervei i grafen?

I 1736 publiserte Leonhard Euler en artikkel der han beviste at dette var umulig.