105
правок
Изменения
→Эйлеров путь, Эйлеров цикл
==Эйлеров путь, Эйлеров цикл=====Эйлеров путь===
Путь <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_(k-1)u_k -> u_k</math> в графе <math>G = (V, E)</math> <br/>
называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/>
Цикл <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_k0-> u_0</math> в графе <math>G = (V, E)</math> <br/>
называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/>
'''Эквивалентно:'''<br/>
Эйлеровым циклом является Эйлеров путь, являющийся циклом.
==Эйлеров граф==
===Определение===
Граф <math>G = (V, E)</math> называется Эйлеровым, если содержит Эйлеров цикл.<br/>
Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/>
===Критерий Эйелеровости===
====Неориентированный граф====
'''Теорема'''<br/>
Неориентированный связный граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/>
====Ориентированный граф====
