Эйлеровость графов

Эйлеров путь

Путь [math]p[/math] [math]u_0 -\gt u_0u_1 -\gt u_1 -\gt u_1u_2 -\gt ...-\gt u_(k-1)u_k -\gt u_k[/math] в графе [math]G = (V, E)[/math]
называется Эйлеровым, если содержит все ребра [math]G[/math], причем каждое - только один раз.

Эйлеров цикл

Цикл [math]p[/math] [math]u_0 -\gt u_0u_1 -\gt u_1 -\gt u_1u_2 -\gt ...-\gt u_ku_k0-\gt u_0[/math] в графе [math]G = (V, E)[/math]
называется Эйлеровым, если содержит все ребра [math]G[/math], причем каждое - только один раз.

Эквивалентно: Эйлеровым циклом является Эйлеров путь, являющийся циклом.

Эйлеров граф

Определение

Граф [math]G = (V, E)[/math] называется Эйлеровым, если содержит Эйлеров цикл.

Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым.

Критерий Эйелеровости

Неориентированный граф

Теорема
Неориентированный связный граф [math]G = (V, E)[/math] является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.

Ориентированный граф