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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эйлеров путь, Эйлеров цикл)
(эйлеровость)
Строка 21: Строка 21:
 
'''Теорема'''<br/>
 
'''Теорема'''<br/>
 
Неориентированный связный граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/>
 
Неориентированный связный граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/>
 +
<br/>
 +
 +
'''Доказательство'''<br/>
 +
 +
<br/>
 +
 +
'''Следствие'''<br/>
 +
Неориентированный связный граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
  
 
====Ориентированный граф====
 
====Ориентированный граф====
 +
'''Теорема'''<br/>
 +
Ориентированный граф <math>G = (V, E) </math> является Эйлеровым тогда и только тогда, входная степень любой вершины равна ее выходной степени.<br/>
 +
<br/>
 +
'''Доказательство'''<br/>
 +
 +
<br/>
 +
'''Следствие'''<br/>
 +
Ориентированный граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, входная степень которой<br/>
 +
на единицу больше выходной, и ровно одну вершину, выходная степень которой на единицу больше входной.<br/>

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

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

Эйлеров граф

Определение

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

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

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

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

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

Доказательство


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

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

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

Доказательство


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