Эйлеровость графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Критерий Эйлеровости)
(Критерий Эйлеровости)
Строка 19: Строка 19:
 
===Критерий Эйлеровости===
 
===Критерий Эйлеровости===
 
====Неориентированный граф====
 
====Неориентированный граф====
'''Теорема'''<br/>
+
 
 +
{{Теорема|theorem
 +
{{statement
 
Неориентированный связный граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/>
 
Неориентированный связный граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/>
<br/>
+
}}
 
+
{{proof
'''Доказательство'''<br/>
 
 
Достаточность:
 
Достаточность:
 
<br/>
 
<br/>
Строка 43: Строка 44:
 
при этом количество ребер в графе уменьшится. Для <math>G - c</math>, по предположению индукции, существует эйлеров цикл <math>e</math>.<br/>
 
при этом количество ребер в графе уменьшится. Для <math>G - c</math>, по предположению индукции, существует эйлеров цикл <math>e</math>.<br/>
 
Тогда в <math>G</math> тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины <math>u</math>, затем обойти <math>e</math>.<br/>
 
Тогда в <math>G</math> тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины <math>u</math>, затем обойти <math>e</math>.<br/>
Теорема доказана.
+
}}
<br/>
 
  
 
'''Следствие'''<br/>
 
'''Следствие'''<br/>

Версия 04:46, 9 октября 2010

Эйлеров путь

Путь [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] называется Эйлеровым, если содержит Эйлеров цикл.

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

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

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

{{Теорема|theorem {{statement Неориентированный связный граф [math]G = (V, E)[/math] является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.
}} {{proof Достаточность:
Рассмотрим Эйлеров цикл [math]p[/math] в [math]G[/math].
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени.

Необходимость:
Докажем утверждение по индукции.
База - лес из [math]N[/math] деревьев, каждое из 1 вершины.
Переход:
Рассмотри граф, в котором степени всех вершин четные.
В нем найдется простой цикл, т.к. иначе граф является лесом [math]-\gt [/math] в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.
Рассмотрим цикл [math]c[/math] такой, что при удалении его ребер не образуется компонент связности размера больше 1.
Такой всегда существует, т.к. граф компонент двусвязности произвольного связного графа является деревом, а т.к. все вершины [math]G[/math]

Рассмотрим вершину [math]u[/math] со степенью больше 2. После удаления цикла [math]c[/math] из графа степени всех вершин останутся четными,
при этом количество ребер в графе уменьшится. Для [math]G - c[/math], по предположению индукции, существует эйлеров цикл [math]e[/math].
Тогда в [math]G[/math] тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины [math]u[/math], затем обойти [math]e[/math].
}}

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

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

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

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


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