Eulervei

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk
Dette bilde representerer problemet Broene i Königsberg, og siden tre av nodene har oddetall grad er det ikke mulig å gå over hver bro kun en gang
Hver node i denne grafen har partall grad, derfor har denne en eulersyklus.

En eulervei i matematisk grafteori er en vei som går gjennom hver kant (strek) nøyaktig én gang. En eulerkrets er en eulervei som ender opp i samme node som den startet. Temaet ble først diskutert av Leonhard Euler i 1736, da han løste det kjente problemet Broene i Königsberg.

Egenskaper[rediger | rediger kilde]

  • En urettet graf har en eulerkrets dersom alle nodene har partall grad. (Dvs det går partall kanter inn til hver node)
  • Dersom en urettet graf har noe annet enn to noder med oddetall grad, kan den ikke ha en eulervei (herav kan vi se at problemet Königsberg syv broer ikke er gjennomførbart).

Kilder[rediger | rediger kilde]