ВУЗ:
Составители:
Рубрика:
ляемым рекой участкам суши
A,B,C,D, а ребра – мостам.
46
Рис.12.1. Рис.12.2.
Таким образом, задачу о кенигсбергских мостах можно на язы-
ке теории графов сформулировать следующим образом: есть ли в
графе
на рис. 12.2 цикл, содержащий все ребра графа? Эйлер дока-
зал неразрешимость этой задачи.
Определение
. Цикл в графе называется эйлеровым, если он со-
держит все ребра графа.
Определение.
Связный граф, в котором есть эйлеров цикл, на-
зывается эйлеровым графом.
Примеры
эйлеровых графов.
(1,2,3,4,2,6,4,5,6,1) Сабли Магомета
Теорема.
Связный граф является эйлеровым тогда и только то-
гда, когда степени всех его вершин четны.
Доказательство.
Необходимость. Пусть G - эйлеров граф. Эйлеров цикл этого
графа, проходя через каждую вершину графа, входит в нее по од-
ному ребру, а выходит по другому. Это означает, что каждая вер-
шина инцидентна четному числу ребер эйлерового цикла, а по-
скольку такой цикл содержит все ребра графа G, то отсюда следует
четность степеней всех его вершин.
Достаточность. Предположим теперь, что степени всех вершин
графа G четны. Начнем цепь P
1
из произвольной вершины v
1
и бу-
A
B
C
D
A
B
C
D
1
2
3
4
5
6
Страницы
- « первая
- ‹ предыдущая
- …
- 44
- 45
- 46
- 47
- 48
- …
- следующая ›
- последняя »
