Euler-tur

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

En tur i en graf kaldes en Euler-tur hvis den omfatter samtlige kanter i grafen. (Kanterne i en tur er indbyrdes forskellige.)

En graf hvori der findes en lukket Euler-tur kaldes en Euler-graf.

Begrebet Euler-tur er knyttet til Leonhard Euler, som efter sigende overvejede, om det var muligt at tilrettelægge en spadsererundtur i Königsberg/Kaliningrad, der passerede byens broer præcis én gang hver. Dette problem kaldes Königsbergs broproblem

Se også[redigér | redigér wikikode]