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

Эйлеров путь

Путь [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_0-\gt u_0[/math] в графе [math]G = (V, E)[/math]
называется Эйлеровым, если содержит все ребра [math]G[/math], причем каждое - только один раз.

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

Эйлеров граф

Определение

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

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

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

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

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

Доказательство
Достаточность:
Рассмотрим Эйлеров цикл [math]p[/math] в [math]G[/math].
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени.

Необходимость:
Докажем утверждение по индукции. База - лес из [math]N\lt math/\gt деревьев, каждое из 1 вершины. ''Переход:'' Рассмотри граф, в котором степени всех вершин четные.\lt br/\gt В нем найдется простой цикл, т.к. иначе граф является лесом \lt math\gt -\gt \lt math\gt в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.\lt br/\gt Рассмотрим цикл \lt math\gt c\lt math/\gt такой, что при удалении его ребер не образуется компонент связности размера больше 1.\lt br/\gt Такой всегда существует, т.к. граф компонент двусвязности произвольного связного графа является деревом, а т.к. все вершины \lt math\gt G\lt math/\gt Б Рассмотрим вершину \lt math\gt u\lt math/\gt со степенью больше 2. После удаления цикла \lt math\gt c\lt math/\gt из графа степени всех вершин останутся четными,\lt br/\gt при этом количество ребер в графе уменьшится. Для \lt math\gt G - c\lt math/\gt , по предположению индукции, существует эйлеров цикл \lt math\gt e\lt math/\gt .\lt br/\gt Тогда в \lt math\gt G\lt math/\gt тоже существует Эйлеров обход - сначала обойти \lt math\gt с\lt math/\gt , начиная с \lt math\gt u\lt math/\gt , затем обойти \lt math\gt e\lt math/\gt . \lt br/\gt '''Следствие'''\lt br/\gt Неориентированный связный граф \lt math\gt G = (V, E)[/math] является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.

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

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

Доказательство
Достаточность:
Необходимость:

Следствие
Ориентированный граф [math]G = (V, E)[/math] является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, входная степень которой
на единицу больше выходной, и ровно одну вершину, выходная степень которой на единицу больше входной.