Page 95 - vol1
P. 95
Kör a gráfban, a kezdőpontjába visszavezető utat, azaz olyan
élsorozatot, amely a kezdőpontjába tér vissza és benne minden él csak egyszer
szerepel.
Az Euler-kör a gráfelmélet speciális sétáinak egyike. Ha egy gráf
MINDEN ÉLÉN pontosan egyszer haladunk át, akkor ezt az utat nyílt Euler-
vonalnak (útnak) nevezzük. Ha egy gráf MINDEN ÉLÉN pontosan egyszer
haladunk át, és visszajutunk a kezdőpontba, akkor ezt az utat Zárt Euler-
vonalnak (útnak) vagy egyszerűen Euler-kör –nek nevezzük.
Ennek kapcsán a következő típusú problémákat fogalmazhatjuk meg: Az
alábbi ábrák megrajzolhatóak-e folytonosan egy vonallal? Ha igen, akkor hol
kezdődik és hol ér véget a rajzolás?
A kérdés megválaszolásának az elméleti alapját a következő két tétel képezi:
1.Tétel:
A gráf akkor és csakis akkor rajzolható meg egy vonallal úgy, hogy bárhol
kezdhetünk, és ugyanoda érünk vissza, ha MINDEN csúcs fokszáma páros szám.
2.Tétel:
Ha egy gráfban pontosan 2 csúcs páratlan fokszámú, a többi páros, akkor a gráf
megrajzolható egy vonallal, az egyik páratlan fokszámú csúcsban kezdünk, és a
másikba érkezünk.
Euler tételeinek következményei:
95
