Eulervei
Utseende
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/96/K%C3%B6nigsberg_graph.svg/250px-K%C3%B6nigsberg_graph.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Labelled_Eulergraph.svg/250px-Labelled_Eulergraph.svg.png)
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.)
Kilder[rediger | rediger kilde]
- Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th Edition (side 666-671) ISBN 9780071315012