ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 6759
Скачиваний: 28
51
Таблица 2.4 – Матрица смежности с весами для графа на рис. 2.38
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
1
10
3
6
12
x
2
10
18
2
13
x
3
18
25
20
7
x
4
25
5
16
4
x
5
5
10
x
6
20
10
14
15
9
x
7
2
4
14
24
x
8
6
23
15
5
x
9
12
13
9
24
5
Уточняем пометки в соответствии с формулой (2).
l(x
2
) = min(
∞, 0
+
+10) = 10, аналогично l(x
7
) = 3, l(x
8
) = 6, l(x
9
) = 12.
Шаг 3. min(10, 3, 6, 12,
∞
) = 3,
x
2
x
7
x
8
x
9
x
3
, x
4
, x
5
, x
6
соответственно x
7
получает постоянную пометку l(x
7
) = 3
+
, p = x
7
.
Шаг 4. Не все вершины имеют постоянные пометки, поэтому
переходим к шагу 2. Значения пометок вершин графа приведены на
рис. 2.39. Обведены вершины с постоянными пометками.
x
3
x
2
x
1
x
5
x
8
x
9
x
7
x
6
x
4
Рис.2.38
− Пример графа к алгоритму Дейкстры
x
1
x
7
x
3
x
4
Рис. 2.39 – Пометки в начале второй итерации
0
+
3
+
∞
∞
∞
∞
6
12
10
x
2
x
9
x
8
x
6
x
5
52
Вторая итерация.
Шаг 2. G(p) = G(x
7
) = {x
2
, x
4
, x
6
, x
9
}.Пометки всех этих вершин
временные. Из (2) получим l(x
2
) = 5, l(x
4
) =7, l(x
6
) = 17, l(x
9
) = 12.
Шаг 3. min(5, 7, 17, 6, 12,
∞ ) = 5,
x
2
x
4
x
6
x
8
x
9
x
3
, x
5
соответственно x
2
получает постоянную пометку. l(x
2
) = 5
+
, p = x
2
.
Шаг 4. Перейти к шагу 2. Значения пометок приведены на
рис. 2.40.
Третья итерация.
Шаг 2. G(p) = G(x
2
) = {x
1
, x
3
, x
7
, x
9
}. Только вершины x
3
и x
9
имеют временные пометки. Из (2) получаем: l(x
3
) = min(
∞, 5
+
+18) =
=23, аналогично l(x
9
) = 12.
Шаг 3. min(23, 7, 17, 6, 12,
∞) = 6,
x
3
x
4
x
6
x
8
x
9
x
5
соответственно x
8
получает постоянную пометку l(x
8
) = 6
+
, p = x
8
.
Шаг 4. Перейти к шагу 2 (рис. 2.41).
x
1
x
8
x
2
x
7
x
9
x
5
x
6
x
3
x
4
Рис. 2.41 – Пометки в начале четвертой итерации
0
+
3
+
∞
17
7
23
6
+
12
5
+
x
1
x
8
x
2
x
7
x
9
x
5
x
6
x
3
x
4
Рис. 2.40 – Пометки в начале третьей итерации
0
+
3
+
∞
17
7
∞
6
12
5
+
53
Продолжая итерационный процесс, получим в итоге постоян-
ные пометки для всех вершин графа (рис.2.42) и кратчайшие пути от
вершины x
1
ко всем остальным вершинам. Эти пути выделены на
рис. 2.42 жирными линиями.
Для нахождения кратчайшего пути между вершиной x
2
и на-
чальной вершиной x
1
, последовательно используем соотношение
l(x
i
′) + C(x
i
′
,
x
i
) = l(x
i
). Полагая i = 2 находим вершину x
2
′, непосред-
ственно предшествующей x
2
в кратчайшем пути от x
1
к x
2
:
l(x
2
′) + C(x
2
′
,
x
2
) = l(x
2
) = 5. Этому соотношению удовлетворяет
вершина x
7
. Следовательно, x
2
′ = x
7
. Полагая i = 7 и применяя соот-
ношение еще раз, получим x
7
′ = x
1
. Поэтому кратчайший путь со-
стоит из вершин x
1
, x
7
, x
2
. Аналогичным образом находим все крат-
чайшие пути от x
1
к остальным вершинам.
2.8
Обход
графа
В теории графов есть понятие обход графа. Это маршрут, со-
держащий все ребра или вершины графа и обладающий определен-
ными свойствами. Наиболее известными обходами графа являются
эйлеровы и гамильтоновы цепи и циклы.
2.8.1
Эйлеровы
цепи
,
циклы
,
пути
,
контуры
Эти понятия возникли в статье Эйлера в 1736 г., в которой он
рассуждает о Кенигсбергских мостах. Известно, что Кенигсберг
(ныне Калининград) расположен на берегах реки Преголи и остро-
x
5
12
+
17
+
7
+
x
1
x
8
6
+
x
9
11
+
23
+
5
+
0
+
x
7
3
+
x
3
x
2
x
6
x
4
Рис.2.42 – Пометки и кратчайшие пути в графе
54
вах на ней. Все части города соединены мостами. На рис. 2.43,а
приведен план расположения семи мостов в Кенигсберге. Задача
состоит в том, чтобы пройти каждый мост по одному разу и вер-
нуться в исходную точку C.
Так как существенны только переходы через мосты, то план
города можно свести к изображению графа, в котором ребра соот-
ветствуют мостам, а вершины – различным разделенным частям
города (рис. 2.43,б).
Поскольку в конце обхода нужно вернуться в исходную часть
города, и на каждом мосту нужно побывать по одному разу, этот
маршрут является простым циклом, содержащим все ребра графа. В
дальнейшем такие циклы стали называть эйлеровыми, а графы,
имеющие эйлеров цикл, – эйлеровыми графами.
Эйлеров цикл можно считать следом пера, вычерчивающего
этот граф, не отрываясь от бумаги. Таким образом, эйлеровы графы
– это графы, которые можно изобразить одним росчерком пера,
причем процесс такого изображения начинается и заканчивается в
одной и той же точке.
Обнаружив, что в данном графе не существует циклических
обходов, проходящих по всем ребрам по одному разу, Эйлер обра-
тился к общей задаче: при каких условиях в графе можно найти та-
кой цикл? Ответ на этот вопрос дает следующая теорема.
A
C
B
D
g
e
f
b
a
c
d
а)
C
a
b
B
g
D
f
d
c
A e
б)
Рис. 2.43 – Схема Кенигсбергских мостов и соответствующий граф
55
Теорема 1 (Эйлера). Конечный связный неориентированный
мультиграф является эйлеровым графом тогда и только тогда, когда
в нем отсутствуют вершины нечетной степени.
Доказательство. Каждый раз, когда эйлеров цикл проходит
через какую-либо вершину, он должен войти в нее по одному ребру,
а выйти по другому. Поэтому условие отсутствия вершин нечетной
степени в эйлеровом графе является необходимым.
Для доказательства достаточности предположим, что все
вершины графа имеют четные степени. Начнем цепь P в произволь-
ной вершине x
i
графа G (рис. 2.44,а), и будем продолжать ее, на-
сколько возможно, все время через новые ребра. Так как в каждой
вершине число ребер четно, этот процесс может закончиться только
в x
i
. Если цикл P содержит не все ребра графа G, то удалим из G
часть, соответствующую циклу P.
Графы P и G имеют четные степени всех вершин. То же долж-
но быть справедливо и для оставшегося графа
P
.
Так как граф G связен, в цикле P должна найтись вершина x
j
,
инцидентная также ребрам
P
. Из x
j
можно построить новую цепь
P
′, содержащую только ребра из
P
. И снова такая цепь может за-
кончиться только при возвращении в x
j
. Но тогда из P и P
′ можно
составить новый цикл
x
i
x
j
P
P
x
1
x
2
x
3
x
7
x
8
x
4
x
5
x
6
Рис. 2.44 – Иллюстрация доказательства теоремы Эйлера (а)
и пример построения Эйлерова цикла (б)
а)
б)