Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 519
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
134
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
показанного на рис. 4.25. В качестве источника выберем верши- ну 1. Тогда D
(1)
= (0, 1, ∞, ∞, 3), D
(2)
= (0, 1, 4, 4, 3), D
(3)
= (0, 1, 4, 4, −1),
D
(4)
= (0, 1, 4, 3, −1). Таким образом, ρ
w
(1, 1) = 0, ρ
w
(1, 2) = 1, ρ
w
(1, 3) = 4,
ρ
w
(1, 4) = 3, ρ
w
(1, 5) = −1. ¤
Отметим, что, зная расстояние от источника a
i
•
•
•
•
•
¡
¡
¡
µ
@
@
@
R
-
-
@
@
@
@
@
@
R
¡
¡
¡
¡
¡
¡
ª
?
6
®
1 2
3 5
4
(1)
(2)
(8)
(4)
(3)
(1)
(3)
(3)
(-5)
Рис. 4.25
до всех остальных вершин графа, можно найти и са- ми кратчайшие (a
i
, a
j
)-маршруты. Действительно,
пусть a
i
, b
1
, b
2
, . . ., b
r
, a
j
— кратчайший (a
i
, a
j
)-марш- рут. Тогда по строке D
(n−1)
вершина b
r
= a
k
1
нахо- дится из соотношения ρ
w
(a
i
, a
j
) = ρ
w
(a
i
, a
k
1
) + w
k
1
j
,
вершина b
r−1
= a
k
2
— из соотношения ρ
w
(a
i
, a
k
1
) =
= ρ
w
(a
i
, a
k
2
) + w
k
2
k
1
и т. д.
Пример 4.5.2. В примере 4.5.1 кратчайший (1, 4)-маршрут определяется следующим образом: ρ
w
(1, 4) = 3 = −1 + 4 = ρ
w
(1, 5) + w
54
, тогда b
r
= 5;
ρ
w
(1, 5) = −1 = 4 − 5 = ρ
w
(1, 3) + w
35
, откуда b
r−1
= 3; ρ
w
(1, 3) = 4 =
= 1 + 3 = w
12
+ w
23
, следовательно, b
r−2
= b
2
= 3, b
r−3
= b
1
= 2. Таким образом, кратчайший (1, 4)-маршрут задается последовательностью вершин
(1, 2, 3, 5, 4). ¤
Следующий алгоритм, алгоритм Дейкстры, более эффективен, чем ал- горитм Форда—Беллмана, но используется только для взвешенных графов,
в которых веса всех дуг неотрицательны.
Итак, пусть G = hM; Ri — взвешенный граф, W = (w
ij
) — матрица весов графа G, где w
ij
> 0; a
i
— выделенный источник. Зададим стро- ку D
(1)
= (d
(1)
1
, d
(1)
2
, . . . , d
(1)
n
), полагая, как и в алгоритме Форда—Беллмана,
d
(1)
i
= 0, d
(1)
j
= w
ij
, i 6= j. Обозначим через T
1
множество вершин M \ {a
i
}.
Предположим, что на шаге s уже определены строка D
(s)
= (d
(s)
1
, . . . , d
(s)
n
)
и множество вершин T
s
. Выберем теперь вершину a
j
∈ T
s
так, что d
(s)
j
=
= min{d
(s)
k
| a
k
∈ T
s
}. Положим T
s+1
T
s
\ {a
j
}, D
(s+1)
(d
(s+1)
1
, . . . , d
(s+1)
n
),
где d
(s+1)
k
= min{d
(s)
k
, d
(s)
j
+ w
jk
}, если a
k
∈ T
s+1
, и d
(s+1)
k
= d
(s)
k
, если a
k
/
∈ T
s+1
На шаге s = n − 1 образуется строка D
(n−1)
w-расстояний между верши- ной a
i
и остальными вершинами графа: d
(n−1)
j
= ρ
w
(a
i
, a
j
).
Отметим, что для реализации алгоритма Форда—Беллмана требуется по- рядка n
3
операций, тогда как в алгоритме Дейкстры необходимо выполнить порядка n
2
операций.
4.5. НАХОЖДЕНИЕ КРАТЧАЙШИХ МАРШРУТОВ
135
Пример 4.5.3. Рассмотрим взвешенный граф G с матрицей весов
W =
0 1
∞ ∞ ∞ ∞
∞
0 5
2
∞
7
∞ ∞
0
∞ ∞
1 2
∞
1 0
4
∞
∞ ∞ ∞
3 0
∞
∞ ∞ ∞ ∞
1 0
и источником 1 (рис. 4.26). Тогда по алгоритму Дейкстры T
1
= {2, 3, 4, 5, 6},
D
(1)
= (0, 1, ∞, ∞, ∞, ∞),
T
2
= {3, 4, 5, 6},
D
(2)
= (0, 1, 6, 3, ∞, ∞),
T
3
= {3, 5, 6},
D
(3)
= (0, 1, 4, 3, 7, 7),
T
4
= {5, 6},
D
(4)
= (0, 1, 4, 3, 7, 5),
T
5
= {5}, D
(5)
= (0, 1, 4, 3, 6, 5) (в D
(s)
подчеркнута величина d
(s)
j
, для которой T
s+1
= T
s
\{a
j
}). Таким образом, ρ
w
(1, 1) = 0, ρ
w
(1, 2) = 1, ρ
w
(1, 3) =
= 4, ρ
w
(1, 4) = 3, ρ
w
(1, 5) = 6, ρ
w
(1, 6) = 5. ¤
Опишем теперь алгоритм нахождения крат-
•
•
•
•
•
•
6 6
?
-
-
@
@
@
@
@
@
R
¾
R
j
Y
1 4
5 2
6 3
(1)
(1)
(1)
(2)
(5)
(1)
(7)
(4)
(3)
(2)
Рис. 4.26
чайших маршрутов в бесконтурном графе. Так же, как и в алгоритме Дейкстры, для выпол- нения этого алгоритма необходимо порядка n
2
операций.
Прежде всего заметим, что в конечном бес- контурном графе G = hM; Ri вершины можно перенумеровать так, что каждая дуга будет иметь вид (a
i
, a
j
), где i < j. Действительно,
в конечном бесконтурном графе всегда суще- ствует вершина a, в которую не заходит ни одна дуга. Обозначим эту верши- ну через a
1
и рассмотрим граф G
1
, полученный из G удалением вершины a
1
Граф G
1
также является бесконтурным и, следовательно, содержит верши- ну a
0
, в которую не заходит ни одна дуга графа G
1
. Вершину a
0
обозначим через a
2
, а граф, полученный из G
1
удалением вершины a
2
, — через G
2
Продолжая процесс, получим в результате искомую нумерацию a
1
, a
2
, . . .,
a
n
вершин графа G.
Пример 4.5.4. На рис. 4.27 приведен пример нумерации вершин бес- контурного взвешенного графа, при которой из (a
i
, a
j
) ∈ R следует i < j
(в скобках указаны веса взвешенных дуг). ¤
136
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Предположим, что в бесконтурном графе G = h{a
1
, a
2
, . . . , a
n
}; Ri для произвольной дуги (a
i
, a
j
) выполняется условие i < j. Заметим, что при такой нумерации все элементы матрицы весов, стоящие под главной диа- гональю, равны ∞. Найдем расстояние от a
1
до всех вершин графа.
Рассмотрим строку D
(1)
= (d
(1)
1
, d
(1)
2
, . . . , d
(1)
n
), где d
(1)
1
= 0; d
(1)
j
= w
1j
; j > 2.
Если на шаге s строка D
(s)
= (d
(s)
1
, d
(s)
2
, . . . , d
(s)
n
) определена,
положим
D
(s+1)
(d
(s+1)
1
, d
(s+1)
2
, . . . , d
(s+1)
n
),
где d
(s+1)
j
min{d
(s)
j
, d
(s)
k
+ w
kj
}, для
k < j и (a
k
, a
j
) ∈ R, j = 1, . . . , n. Данный алгоритм является аналогом ал- горитма Форда—Беллмана, учитывающим бесконтурность графа G, и при
s = n − 1 получаем d
(n−1)
j
= ρ
w
(a
1
, a
j
).
Пример 4.5.5. Для графа G, изображенного
•
•
•
•
•
•
•
•
¡
¡
¡
¡
µ
-
@
@
@
@
R
-
-
-
¡
¡
¡
¡
µ
¡
¡
¡
¡
µ
6
-
1 2
3 4
5 6
7 8
(−2)
(2)
(−5)
(6)
(3)
(1)
(1)
(7)
(10)
(1)
Рис. 4.27
на рис. 4.27, имеем
W =
0 1
∞
2
∞
∞
1
∞
∞
0
−2 ∞
7
∞ ∞ ∞
∞ ∞
0
∞
∞
10 ∞ ∞
∞ ∞
∞
0
−5 ∞ ∞ ∞
∞ ∞
∞
∞
0 6
∞
1
∞ ∞
∞
∞
∞
0
∞ ∞
∞ ∞
∞
∞
∞
∞
0 3
∞ ∞
∞
∞
∞
∞ ∞
0
,
D
(1)
= (0, 1, ∞, 2, ∞, ∞, 1, ∞), D
(2)
= (0, 1, −1, 2,
−3, ∞, 1, 4), D
(3)
= (0, 1, −1, 2, −3, 3, 1, −2) = D
(4)
= D
(5)
= D
(6)
= D
(7)
. ¤
Отметим, что если в приведенных алгоритмах ∞ заменить на −∞, min —
на max, то получим алгоритмы, которые позволяют в графах, не имеющих контуров положительных весов, находить маршруты наибольшей длины.
§ 4.6.
Степени вершин
Степенью или валентностью вершины a неорграфа G называется число ребер, инцидентных вершине a, т. е. число ребер, концом которых является вершина a (при этом петли считаются дважды). Если G — орграф, то степени его вершин определяются как степени вершин в соответствующем неоргра- фе F (G). Аналогично вводится понятие степени вершины в мультиграфах.
Степень вершины a будем обозначать через deg
G
a или просто deg a. Вер- шина степени 0 называется изолированной, вершина степени 1 — концевой
или висячей.
4.7. ОБХОДЫ ГРАФОВ
137
Пример 4.6.1. Вершины графа G, изображенного на рис. 4.28, имеют следующие валентности: deg 1 = deg 2 = deg 3 = 1 (т. е. 1, 2, 3 — висячие вершины), deg 4 = 5, deg 5 = 0 (т. е. 5 — изолированная вершина). ¤
Рассмотрим сумму степеней всех вершин графа. По-
•
•
•
•
•
¡
¡
¡
¡
µ@
@
@
@
R
g
2 3
5 1
4
Рис. 4.28
скольку каждое ребро входит в эту сумму дважды, спра- ведливо
Утверждение 4.6.1 (лемма о рукопожатиях). Сум-
ма степеней всех вершин графа является четным числом
и равна удвоенному числу ребер.
Пусть G — бесконтурный орграф. Полустепенью ис-
хода deg
+
a вершины a называется число дуг, исходящих из a. Полустепенью
захода deg
−
a вершины a называется число дуг, которые заходят в верши- ну a. Справедливо соотношение deg a = deg
+
a + deg
−
a.
В примере 4.5.4 имеем deg 2 = 3, deg
+
2 = 2, deg
−
2 = 1.
§ 4.7.
Обходы графов
Опишем одну из задач, положивших начало теории графов, — задачу
о кенигсбергских мостах . На рис. 4.29 схематично изображена карта г. Кенигсберга в XVIII в. Город был расположен на берегах и двух островах реки Преголи. Острова между собой и с берегами были связаны семью мо- стами. Возник вопрос: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз?
Неориентированный мультиграф G, представляющий задачу, показан на рис. 4.30. Вершины x
1
, x
4
соответствуют берегам реки, x
2
, x
3
— остро- вам, ребра мультиграфа — мостам. Следовательно, на языке теории графов
•
•
•
•
¡
¡
¡
@
@
@
x
1
x
2
x
4
x
3
Рис. 4.29
Рис. 4.30
138
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
1 ... 12 13 14 15 16 17 18 19 ... 29
задача формулируется следующим образом: существует ли в мультиграфе цикл, содержащий все ребра данного мультиграфа?
Выдающимся математиком и механиком Л. Эйлером сформулирован и до- казан критерий того, что связный неориентированный мультиграф имеет цикл, содержащий все ребра данного мультиграфа. Цикл, содержащий все ребра мультиграфа, называется эйлеровым, и мультиграф, в котором име- ется эйлеров цикл, также называется эйлеровым.
Теорема 4.7.1. Связный неориентированный мультиграф является
эйлеровым тогда и только тогда, когда степень каждой из его вершин —
четное число. ¤
Мультиграф, изображенный на рис. 4.30, не содержит эйлеров цикл,
поскольку в нем есть вершины, имеющие нечетную степень. Более того, все его вершины имеют нечетную степень.
Опишем алгоритм построения эйлерова цикла в эйлеровом мультиграфе.
Этот алгоритм задается следующими правилами.
1. Выбрать произвольно некоторую вершину a.
2. Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным).
3. Каждое пройденное ребро вычеркнуть и присвоить ему номер, на еди- ницу больший номера предыдущего вычеркнутого ребра.
4. Находясь в вершине x, не выбирать ребро, соединяющее x с a, если имеется возможность иного выбора.
5. Находясь в вершине x, не выбирать ребро, ко-
•
•
•
•
•
•
•a
1 2
3 4
5 6
7 8
Рис. 4.31
торое является перешейком (т. е. ребром, при удале- нии которого граф, образованный невычеркнутыми ребрами, распадается на две компоненты связности,
каждая из которых имеет хотя бы по одному ребру).
6. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл, причем порядок нумерации соответствует последовательности обхода ребер.
Пример 4.7.1. Найдем эйлеров цикл в эйлеровом графе, изображенном на рис. 4.31. После выбора вершины a и прохождения ребер 1 и 2 имеют- ся три возможности выбора: ребра 3, 6 или 7. Так как ребро 7 является перешейком, выбираем следующее ребро из оставшихся, например 3. Далее обходим оставшиеся ребра и получаем эйлеров цикл 1, 2, 3, 4, 5, 6, 7, 8. ¤
4.7. ОБХОДЫ ГРАФОВ
139
Будем говорить, что набор реберно непересекающихся цепей покрывает
граф G, если каждое ребро графа G входит в одну из этих цепей. Пусть связный граф G содержит k вершин нечетной степени. По лемме о рукопо- жатиях число k четно. Рассмотрим граф G
0
, полученный добавлением к G
новой вершины a и ребер, соединяющих a со всеми вершинами графа G
нечетной степени. Поскольку степени всех вершин графа G
0
четны, G
0
со- держит эйлеров цикл. Если удалить из этого цикла все ребра, инцидентные вершине a, то получится не более k/2 цепей, содержащих все ребра графа G,
т. е. покрывающих G. С другой стороны, граф, являющийся объединением
r реберно непересекающихся цепей, имеет не более 2r вершин нечетной сте- пени. Поэтому граф G нельзя покрыть цепями, число которых меньше k/2.
Тем самым доказана
Теорема 4.7.2. Если связный граф содержит k вершин нечетной сте-
пени, то минимальное число покрывающих его реберно непересекающихся
цепей равно k/2. ¤
В частности, при k = 2 граф имеет цепь, которая соединяет вершины нечетной степени и содержит все ребра графа. Цепь, содержащая все ребра графа, называется эйлеровой.
Мы рассмотрели обходы ребер графа. Следующей нашей целью является изучение обходов вершин графа.
Граф называется гамильтоновым, если в нем имеется простой цикл, со- держащий каждую вершину этого графа. Сам такой цикл также называется
гамильтоновым. Гамильтоновой называется и простая цепь, содержащая все вершины графа. Очевидно, что любой граф, ребра которого образуют простой цикл, является гамильтоновым, а граф, показанный на рис. 4.31, —
негамильтоновым.
Несмотря на схожесть задач о нахождении эйлеровых и гамильтоновых циклов, решение последней значительно сложнее. Известны следующие до- статочные условия существования гамильтоновых циклов в связном неор- графе G без петель, имеющем n > 3 вершин:
Теорема 4.7.3. Если для любых двух различных несмежных вершин a
и b графа G выполняется условие deg a + deg b > n, то существует гамиль-
тонов цикл. ¤
Следствие 4.7.4. Если для любой вершины a графа G выполнено усло-
вие deg a > n/2, то существует гамильтонов цикл. ¤
140
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
С задачей нахождения гамильтонова цикла связана следующая задача
коммивояжера. Район, который должен посетить бродячий торговец,
содержит некоторое количество городов, расстояния между которыми из- вестны. Требуется найти маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный город. Если таких маршрутов много,
требуется найти кратчайший из них.
Математическая постановка задачи выглядит так: найти гамильтонов цикл минимального веса. Решение этой проблемы мы рассмотрим в § 4.9,
а здесь отметим некоторые практические задачи, сводящиеся к задаче ком- мивояжера.
1. Пусть граф задает сеть коммуникаций между фиксированными цен- трами. Необходимо построить маршрут, обеспечивающий посещение всех центров ровно по одному разу.
2. Имеется станок с числовым программным управлением, который вы- сверливает отверстия в печатных платах по заданной программе. Составляя граф, в котором вершины соответствуют требуемым отверстиям, получаем задачу нахождения обхода вершин, такого, что суммарное время, затрачен- ное на него, было бы минимальным.
§ 4.8.
Остовы графов
Деревом называется связный неорграф, не содержащий циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом, компонентами связности любого леса являются деревья.
На рис. 4.32 изображен лес, состоящий из двух деревьев.
Теорема 4.8.1. Для неорграфа G без петель, содержащего n вершин,
следующие условия эквивалентны:
1) G — дерево;
2) G — связный граф, содержащий n − 1 ребро;
3) G — ациклический граф, содержащий n − 1 ребро;
•
•
•
•
A
A
A
A
A
¢
¢
¢
¢
¢
•
•
•
¢
¢
¢
¢
¢
•
•
•
•
•
A
A
A
A
A
¡
¡
¡
¡
¡
•
•
•
•
©©
©©
©
¢
¢
¢
¢
¢
Рис. 4.32
4.8. ОСТОВЫ ГРАФОВ
141 4) любые две несовпадающие вершины графа G соединяет единственная
простая цепь;
5) G — ациклический граф, такой, что если какую-либо пару его несмеж-
ных вершин соединить ребром, то полученный граф будет содержать ровно
один цикл. ¤
Пусть G = hM; Ri — неорграф. Часть G
0
= hM
0
; R
0
i графа G называется
остовом или каркасом графа G, если M = M
0
и G
0
— лес, который на любой связной компоненте графа G образует дерево. Таким образом, если G — связ- ный граф, то остов G
0
является деревом, которое будем называть остовным
деревом графа G.
Понятие остова для орграфа G определяется как часть G
0
графа G, для которой F (G
0
) является остовом графа F (G). Аналогично вводится понятие остовного дерева для связного орграфа G.
Очевидно, что в каждом графе существует остов: разрушая в каждой связной компоненте циклы, т. е. удаляя лишние ребра, получаем остов.
Пример 4.8.1. В качестве остова графа G, изображенного на рис. 4.33,
можно взять лес с ребрами 2, 3, 4, 6, 7 (вообще говоря, остов определяется неоднозначно). ¤
Из теоремы 4.8.1. вытекает
Следствие 4.8.2. Число ребер произвольного неорграфа G, которые
необходимо удалить для получения остова, не зависит от последователь-
ности их удаления и равно m−n+c, где m — число ребер, n — число вершин,
c — число компонент связности графа G.
Доказательство. Действительно, если i-я компонента связности C
i
графа G содержит n
i
вершин, то по теореме 4.8.1 соответствующее дерево K
i
остова содержит n
i
−1 ребро. Следовательно, для получения K
i
из компонен- ты C
i
нужно удалить m
i
−(n
i
−1) ребер, где m
i
— число ребер в C
i
. Суммируя удаляемые ребра по всем компонентам связности и замечая, что
c
P
i=1
m
i
= m,
c
P
i=1
n
i
= n, получаем, что необходимо удалить
c
P
i=1
(m
i
− n
i
+ 1) = m − n + c
ребер. ¤
Число ν(G) m − n + c называется цикломатическим числом или цик-
лическим рангом графа G. Число ν
∗
(G) n − c называется коциклическим
рангом или корангом. Таким образом, ν
∗
(G) есть число ребер, входящих в любой остов графа G, и ν(G) + ν
∗
(G) = m.