Eulervei

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

• 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) ISBN 9780071315012