ВУЗ:
Составители:
Рубрика:
Глава 2. Плоские и планарные графы 55
рованной вершиной, либо эйлеровым графом с четными степенями
вершин и числом ребер меньшим m. В этом случае эйлеровым цик-
лом связного графа G будет объединение простого цикла С с эйле-
ровыми циклами связных компонент подграфа G
1
. ■
Утверждение 2.6. Связный граф G обладает эйлеровой цепью с
концами А и В тогда и только тогда, когда А и В единственные не-
четные его вершины.
Доказательство. Необходимость. Пусть G имеет эйлерову цепь
(А, В). Присоединим к этому графу новое ребро, соединяющее кон-
цы эйлеровой цепи. В полученном графе G
1
степени всех вершин
четные и, следовательно, существует эйлеров цикл. Тогда в графе G
все вершины, кроме А и В, являются четными.
Достаточность. Пусть G связен и А, В – единственные его не-
четные вершины. Соединив концы нечетных вершин, получим эйле-
ров граф G
1
, в котором эйлеров цикл содержит вершины А и В. Если
в этом цикле исключить дополнительное ребро, то получим эйлеро-
ву цепь. ■
Если граф G связный и имеет 2k вершин нечетной степени, то в
нем можно провести k различных цепей, содержащих все его ребра в
совокупности ровно по одному разу [2, 36].
Рассмотрим пример. Пусть автобусная сеть имеет вид графа на
рис. 2.11. Требуется найти минимальное число маршрутов, обеспе-
чивающих проезд пассажиров из
любого пункта в любой с пересад-
ками или без них. Каждый автобус
при этом должен двигаться по сво-
ему маршруту.
Решение. Граф – не эйлеров, так
как имеет 4 нечетные вершины. По-
этому в этом графе существует два маршрута (две различные цепи),
например, ADFC, DCAF. При решении прикладных задач (голово-
ломок, лабиринтов и др.) возникает проблема построения замкнуто-
го маршрута из некоторой вершины А, содержащего все ребра графа
дважды. Такие задачи приводят к необходимости рассмотрения со-
ответствующих ориентированных графов. Орграф является эйлеро-
F
А
D
С
Рис. 2.11
Страницы
- « первая
- ‹ предыдущая
- …
- 53
- 54
- 55
- 56
- 57
- …
- следующая ›
- последняя »
