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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Неориентированный граф)
Строка 20: Строка 20:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Неориентированный почти связный<ref>Граф назовем почти связным, если все его компоненты связности, кроме, быть может, одной, имеют размер 1.</ref> граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/>
+
Неориентированный почти связный
 +
<ref name = "almost">
 +
Неориентированный граф назовем почти связным, если все его компоненты связности, кроме, быть может, одной, имеют размер 1.<br/>
 +
Ориентированный граф назовем почти связным, если все его компоненты слабой связности, кроме, быть может, одной, имеют размер 1.<br/>
 +
</ref>
 +
граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/>
 
|
 
|
 
proof=
 
proof=
Строка 46: Строка 51:
 
}}
 
}}
 
'''Следствие'''<br/>
 
'''Следствие'''<br/>
Неориентированный связный граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
+
Неориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
  
 
====Ориентированный граф====
 
====Ориентированный граф====
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Ориентированный граф <math>G = (V, E) </math> является Эйлеровым тогда и только тогда, входная степень любой вершины равна ее выходной степени.<br/>
+
Ориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E) </math> является Эйлеровым тогда и только тогда, входная степень любой вершины равна ее выходной степени.<br/>
 
|proof=
 
|proof=
 
Аналогично неориентированному графу.
 
Аналогично неориентированному графу.
Строка 58: Строка 63:
 
<br/>
 
<br/>
 
'''Следствие'''<br/>
 
'''Следствие'''<br/>
Ориентированный граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, входная степень которой<br/>
+
Ориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, входная степень которой<br/>
 
на единицу больше выходной, и ровно одну вершину, выходная степень которой на единицу больше входной.<br/>
 
на единицу больше выходной, и ровно одну вершину, выходная степень которой на единицу больше входной.<br/>
  
 
== Примечания ==
 
== Примечания ==
 
<references/>
 
<references/>

Версия 05:15, 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] называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым.

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

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

Теорема:
Неориентированный почти связный

[1]

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

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

Необходимость:
Докажем утверждение по индукции.
База:
Лес из [math]N[/math] деревьев, каждое из 1 вершины.
Переход:
Рассмотри граф, в котором степени всех вершин четные.
В нем найдется простой цикл, т.к. иначе граф является лесом, и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин. Рассмотрим цикл [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]\triangleleft[/math]

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

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

Теорема:
Ориентированный почти связный[1] граф [math]G = (V, E) [/math] является Эйлеровым тогда и только тогда, входная степень любой вершины равна ее выходной степени.
Доказательство:
[math]\triangleright[/math]
Аналогично неориентированному графу.
[math]\triangleleft[/math]


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

Примечания

  1. 1,0 1,1 1,2 1,3 Неориентированный граф назовем почти связным, если все его компоненты связности, кроме, быть может, одной, имеют размер 1.
    Ориентированный граф назовем почти связным, если все его компоненты слабой связности, кроме, быть может, одной, имеют размер 1.