Hopp til innhold

Eulervei

Fra Wikipedia, den frie encyklopedi
Dette bildet representerer problemet Broene i Königsberg, og siden alle nodene har oddetall grad er det ikke mulig å gå over hver bro kun én gang.
Hver node i denne grafen har partall grad, derfor har denne en eulerkrets.

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 i samme node som den startet. Temaet ble først diskutert av Leonhard Euler i 1736, da han viste at det kjente problemet Broene i Königsberg ikke kunne løses.

Egenskaper

[rediger | rediger kilde]
  • En sammenhengende urettet graf har en eulerkrets (eulersyklus) hvis og bare hvis alle nodene har partallsgrad. (Dvs. at antallet kanter inn til hver node er et partall.)
  • En sammenhengende urettet graf har en eulervei (men ingen eulerkrets) hvis og bare hvis eksakt to av nodene er av odde grad. (Herav kan man se at problemet Broene i Königsberg ikke kan løses.)