Eulervei

miniatyr|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
 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
Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th Edition (side 666-671) 

Kategori:Grafteori
Kategori:NP-komplette problemer