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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Критерий Эйлеровости)
(Критерий Эйлеровости)
Строка 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

Эйлеров путь

Путь p u0>u0u1>u1>u1u2>...>u(k1)uk>uk в графе G=(V,E)
называется Эйлеровым, если содержит все ребра G, причем каждое - только один раз.

Эйлеров цикл

Цикл p u0>u0u1>u1>u1u2>...>uku0>u0 в графе G=(V,E)
называется Эйлеровым, если содержит все ребра G, причем каждое - только один раз.

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

Эйлеров граф

Определение

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

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

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

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

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

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

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

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

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

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

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


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