Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

142
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
•
•
5 2
3 1
4 6
7 8
•
•
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
2 3
1 4
3 3
3 5
1 2
Рис. 4.33
Рис. 4.34
Из следствия 4.8.2. вытекают следующие два утверждения.
Следствие 4.8.3. Неорграф G является лесом тогда и только тогда,
когда ν(G) = 0. ¤
Следствие 4.8.4. Неорграф G имеет единственный цикл тогда и толь-
ко тогда, когда ν(G) = 1. ¤
Опишем алгоритм нахождения остова минимального веса во взвешен- ном графе. Эта задача возникает при проектировании линий электропере- дач, дорог и т. п., когда требуется заданные центры (вершины) соединить некоторой системой каналов связи (ребер) так, чтобы любые два центра бы- ли связаны либо непосредственно соединяющим их каналом (ребром), либо через другие центры и каналы, т. е. цепью, у которой общая длина (или, на- пример, стоимость) каналов связи была минимальной. Искомая сеть будет остовом минимального веса полного графа.
Алгоритм, решающий задачу нахождения остова минимального веса
во взвешенном графе G = hM; Ri, заключается в следующем.
1. Строим граф T
1
, состоящий из множества вершин M и един- ственного ребра u
1
, которое имеет минимальный вес.
2. Если граф T
i
уже построен и i < n − c, где n = |M|, c = c(G), то стро- им граф T
i+1
, добавляя к множеству ребер графа T
i
ребро u
i+1
, имеющее минимальный вес среди ребер, не входящих в T
i
и не составляющих циклов с ребрами из T
i
Приведенный алгоритм, в частности, позволяет находить остов в невзве- шенном графе, положив w(u
i
) = 1 для всех ребер u
i
∈ R.
Пример 4.8.2. На рис. 4.34 показан остов минимального веса взвешен- ного графа. Вес остова равен 9. ¤

4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ
143
§ 4.9.
Обходы графа по глубине и ширине.
Решение задачи коммивояжера
При решении прикладных задач часто возникает необходимость обхода вершин графа, связанная с поиском вершин, удовлетворяющих определен- ным свойствам.
Пусть G = hM; Ri — связный неориентированный граф, T — некоторый остов графа G, a — некоторая фиксированная вершина, называемая корнем
дерева T . Разместим вершины из M по этажам
•
• • •
• • • • • •
• •
• • •
•
•
• •
¡
¡
¡
@
@
@
@
@
@
¡
¡ @
@
HH
H
¡
¡ @
@
a
1 2
3 4
5
Рис. 4.35
таким образом, чтобы корень a находился на верхнем этаже, смежные с ним верши- ны занимали этаж на единицу ниже, смежные с отмеченными вершинами — еще на единицу ниже и т. д. (рис. 4.35). Таким образом, полу- чаем e(a) + 1 этажей, где e(a) — эксцентриситет вершины a.
Опишем обход графа по глубине. При таком обходе после очередной рас- смотренной вершины выбирается смежная с ней вершина следующего этажа.
Если очередная рассмотренная вершина висячая и ее достижение не дает желаемого решения задачи, то возвращаемся до ближайшей вершины сте- пени > 3 и просматриваем вершины другого, еще не пройденного маршрута в таком же порядке и т. д.
На рис. 4.36 показана очередность обхода вершин по глубине графа, изоб- раженного на рис. 4.35.
При обходе графа по ширине просмотр вершин дерева ведется по этажам,
переход к вершинам следующего этажа производится только после просмот- ра всех вершин данного этажа. На рис. 4.37 показан порядок обхода по ши- рине графа, изображенного на рис. 4.35.
Очевидно, что при обходе всех вершин оба подхода: поиск в глубину и по- иск по ширине — эквивалентны. Если же достаточно найти одну вершину с определенным свойством, то целесообразность применения поиска решения по глубине или по ширине определяется структурой дерева. Если дерево является достаточно широким, а висячие вершины расположены на срав- нительно близких этажах, то целесообразно вести поиск по глубине. Для глубоких узких деревьев, когда висячие вершины могут встретиться на раз- личных этажах и их разброс по этажам достаточно велик, предпочтение отдается поиску по ширине.

144
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
@
@
@
@
¡
¡
@
@
HH
HH
¡
¡
@
@
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15 16 17 18 19
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
@
@
@
@
¡
¡
@
@
HH
HH
¡
¡
@
@
1 2
5 11 16 17 6
3 7
12 13 4
8 9
14 15 18 19 10
Рис. 4.36
Рис. 4.37
Отметим, что при компьютерной реализации обходов по глубине и ши- рине целесообразно использовать задание дерева структурой смежности вер- шин.
Часто при решении задач их разбивают на несколько более простых задач, которые, в свою очередь, разбиваются на более простые подзадачи и так до тех пор, пока не появляются подзадачи, под- дающиеся непосредственному решению. Такое разбиение задач можно представить в виде дерева следующим образом. Если задача A разбивается на подзадачи A(1, 1), A(1, 2), . . . , A(1, n
1
), подзадача A(1, i) — на подза- дачи A(2, i, 1), . . . , A(2, i, n
2,i
) и т. д., то получается дерево, изображенное на рис. 4.38.
Для решения задач используются обходы таких деревьев с поиском по глубине или ширине. Опишем данный подход на примере решения задачи коммивояжера методом ветвей и границ.
Пусть W = (w
ij
) — матрица весов графа G = hM; Ri, не имеющего пе- тель, где M = {1, 2, . . . , n}. Для простоты будем считать, что все веса w
ij
неотрицательны. Найдем нижнюю оценку весов гамильтоновых циклов. Для этого в матрице весов найдем минимальные числа каждой строки: w
1k
1
, w
2k
2
,
. . ., w
nk
n
. Очевидно, что вес произвольного гамильтонова цикла не мень- ше w
1k
1
+ w
2k
2
+ . . . + w
nk
n
. Преобразуем матрицу весов, вычитая из каж- дой строки соответствующее число w
ik
i
. Получаем матрицу W
∨
= (w
∨
ij
),
где w
∨
ij
= w
ij
− w
ik
i
. В ней найдем минимальные числа каждого столбца:
w
∨
l
1 1
, w
∨
l
2 2
, . . ., w
∨
l
n
n
, и преобразуем ее, вычитая из каждого столбца соответ- ствующее число w
∨
l
j
j
: W
∗
= (w
∗
ij
), где w
∗
ij
= w
∨
ij
− w
∨
l
j
j
. Для любого гамиль- тонова цикла X справедлива оценка веса w(X) цикла X: w(X) > h, где
h = w
1k
1
+ w
2k
2
+ . . . + w
nk
n
+ w
∨
l
1 1
+ w
∨
l
2 2
+ . . . + w
∨
l
n
n

4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ
145
•
A
A(1, 1)
A(1, 2)
A(1, n
1
)
· · ·
A(2, 1, 1) · · · A(2, 1, n
21
)
A(2, n
1
, 1) · · · A(2, n
1
, n
2n
1
)
¡
¡
¡
¡
¡
@
@
@
@
@
´
´
´
´
´
Q
Q
Q
Q
Q
¤
¤
¤
¤¤
C
C
C
CC
· · ·
¤
¤
¤
¤¤
C
C
C
CC
· · ·
¤
¤
¤
¤¤
C
C
C
CC
· · ·
¤
¤
¤
¤¤
C
C
C
CC
· · ·
¤
¤
¤
¤¤
C
C
C
CC
· · ·
Рис. 4.38
Обозначим через (a
1
, a
2
, . . . , a
k
){b
1
, b
2
, . . . , b
t
} множество гамильтоновых циклов, в которых первые k вершин a
1
, a
2
, . . ., a
k
, а (k + 1)-я вершина a
k+1
не принадлежит множеству {b
1
, b
2
, . . . , b
t
}. Используя введенные обозначе- ния, можем разбить нашу задачу на две подзадачи, поделив множество га- мильтоновых циклов на множества (1, k
1
)∅ и (1){k
1
} (рис. 4.39).
При рассмотрении множества (1, k
1
)∅ отождествим в графе G вершины 1
и k
1
(обозначим новую вершину через x) и получим граф G
0
с множеством вершин {x, 2, . . . , k
1
− 1, k
1
+ 1, . . . , n} и матрицей весов
W
0
=











∞
w
∗
k
1 2
w
∗
k
1 3
· · ·
w
∗
k
1
,k
1
−1
w
∗
k
1
,k
1
+1
· · ·
w
∗
k
1
n
w
∗
21
∞
w
∗
23
· · ·
w
∗
2,k
1
−1
w
∗
2,k
1
+1
· · ·
w
∗
2n
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
w
∗
k
1
−1,1
w
∗
k
1
−1,2
w
∗
k
1
−1,3
· · ·
∞
w
∗
k
1
−1,k
1
+1
· · · w
∗
k
1
−1,n
w
∗
k
1
+1,1
w
∗
k
1
+1,2
w
∗
k
1
+1,3
· · · w
∗
k
1
+1,k
1
−1
∞
· · · w
∗
k
1
+1,n
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
w
∗
n1
w
∗
n2
w
∗
n3
· · ·
w
∗
n,k
1
−1
w
∗
n,k
1
+1
· · ·
∞











.
Для графа G
0
найдем нижнюю оценку h
0
весов гамильтоновых циклов аналогично тому, как найдены оценки h. Тогда нижняя оценка h
1
весов га- мильтоновых циклов множества (1, k
1
)∅ равна h + h
0

146
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
H
µ´
¶³
(1, k
1
)∅
h
1
±°
²¯
(1){k
1
}
h
2
±°
²¯
(1, k
1
, k
k
1
)∅
h
11
±°
²¯
(1, k
1
){k
k
1
}
h
12
±°
²¯
(1, m
1
)∅
h
21
±°
²¯
(1){k
1
, m
1
}
h
22
±°
²¯
(1, k
1
, k
k
1
, k
k
k1
)∅
h
111
µ´
¶³
¡
¡
¡
@
@
@
¡
¡
¡
@
@
@
¡
¡
¡
@
@
@
· · · · · · · · ·
¤
¤
¤
C
C
C
C
C
C
¤
¤
¤
@
@
@
¢
¢
¢
· · ·
· · · · · · · · ·
Рис. 4.39
При рассмотрении множества (1){k
1
} в матрице весов W
∗
элемент w
∗
1k
1
заменяется на ∞ и по полученной матрице W находится нижняя оценка h
00
весов гамильтоновых циклов графа с матрицей весов W
00
. Тогда нижняя оценка h
2
весов гамильтоновых циклов множества (1){k
1
} равна h + h
00
Каждая из подзадач разбивается на свои подзадачи, и этот процесс с оце- ниванием весов гамильтоновых циклов продолжается до тех пор, пока не оты- щется самая низкая из оценок, являющаяся весом некоторого гамильтонова цикла, который и будет иметь минимальный вес.
При рассмотрении подзадач целесообразно вести поиск в глубину, при котором на каждом следующем этаже выбирается та подзадача, которая имеет меньшую нижнюю оценку.
Пример 4.9.1. Рассмотрим граф с матрицей весов
W =
1 2
3 4
5 6








∞ 13 7
5 2
9 8
∞
4 7
5
∞
8 4
∞
3 6
2 5
8 1
∞
0 1
∞
6 1
4
∞
9 10 0
8 3
7
∞








.
Найдем минимальные числа строк:
Ã
2 4
2 0
1 0
!
, где 2 = w
15
, 4 = w
23
, 2 = w
36
,
0 = w
45
, 1 = w
53
, 0 = w
62

4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ
147
Вычитая соответствующие числа w
ik
i
из каждой строки, получим матрицу
W
∨
=








∞ 11 5
3 0
7 4
∞
0 3
1
∞
6 2
∞
1 4
0 5
8 1
∞
0 1
∞
5 0
3
∞
8 10 0
∞
3 7
∞








.
После нахождения наименьших значений по столбцам (4, 0, 0, 1, 0, 0) и вы- читания из каждого столбца матрицы W
∨
соответствующего числа w
l
i
j
об- разуется матрица
W
∗
=








∞ 11 5
2 0
7 0
∞
0 2
1
∞
2 2
∞
0 4
0 1
8 1
∞
0 1
∞
5 0
2
∞
8 6
0
∞
2 7
∞








.
Суммируя элементы w
ik
i
и w
i
j
j
, получаем нижнюю оценку h = 14. Так как
w
15
= min{w
1i
| i = 1, . . . , n}, то множество гамильтоновых циклов разобьем на два множества (1, 5)∅ и (1){5} (рис. 4.40).
При рассмотрении множества (1, 5)∅ получаем матрицу весов
W
0
=
x
2 3
4 6
x
2 3
4 6






∞
5 0
2 8
0
∞
0 2
∞
2 2
∞
0 0
1 8
1
∞
1 6
0 8
2
∞






графа G
0
, образованного отождествлением вершин 1 и 5 графа G. Мини- мальные элементы строк матрицы W
0
образуют столбец






0 0
0 1
0






, поэтому (W
0
)
∨
=






∞
5 0
2
∞
0
∞
0 2
∞
2 2
∞
0 0
0 7
0
∞
0 6
0 8
2
∞






,

148
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
H
(1, 5)∅
(1, 5, 3)∅
(1, 5, 3, 4)∅
(1, 5, 3, 4, 6)∅
(1){5}
(1, 5){3}
(1, 5, 3){4}
(1, 5, 3, 4){6}
¡
¡
¡
@
@
@
¡
¡
¡
HH
HH
HH
¡
¡
¡
PPP
PPP
PPPP
¡
¡
¡
XXXX
XXXX
XXXX
X
14
±°
²¯
15
±°
²¯
15
±°
²¯
15
±°
²¯
15
±°
²¯
16
±°
²¯
17
±°
²¯
17
±°
²¯
∞
±°
²¯
Рис. 4.40
а минимальные элементы столбцов матрицы (W
0
)
∨
образуют нулевую стро- ку, и значит, (W
0
)
∗
= (W
0
)
∨
. Таким образом, оценка h
1
будет равна h + h
0
=
= 14 + 1 = 15.
Рассматривая множество (1){5}, мы должны в матрице W
∗
заменить эле- мент w
∗
15
= 0 на ∞. Тогда оценка h
2
будет h + h
0
= 14 + 2 = 16.
Поскольку h
1
< h
2
, выбираем множество (1, 5)∅ и соответствующую мат- рицу весов (W
0
)
∗
. Теперь в силу того, что (w
∗
)
x3
= 0, разобьем множе- ство гамильтоновых циклов из множества (1, 5)∅ на множества (1, 5, 3)∅
и (1, 5){3} (рис. 4.40). Рассматривая случай (1, 5, 3)∅, получаем матрицу ве- сов
W
00
=
x
2 4
6
x
2 4
6




∞
2 0
0 0
∞
2
∞
0 7
∞
0 6
0 2
∞




графа G
00
, образованного отождествлением вершин x и 3 графа G
0
. Оценка
h
11
равна 15, а (W
00
)
∗
= W
00
. При рассмотрении множества (1, 5){3} в матрице
(W
0
)
∗
заменяем элемент (w
0
)
∗
23
= 0 на ∞ и получаем оценку h
12
= h
1
+2 = 17.

4.10. УПОРЯДОЧЕННЫЕ И БИНАРНЫЕ ДЕРЕВЬЯ
149
Так как h
11
< h
12
, выберем множество (1, 5, 3)∅ с матрицей ве- сов (W
00
)
∗
= W
00
. Поскольку (W
00
)
∗
x4
= 0, рассмотрим множества циклов
(1, 5, 3, 4)∅ и (1, 5, 3){4}. Для оценивания весов в множестве (1, 5, 3, 4)∅ отож- дествим вершины x и 4 в графе G
00
и получим граф G
000
с матрицей весов
W
000
=
x
2 6
x
2 6


∞
7 0
0
∞ ∞
6 0
∞

 .
Очевидно, что h
111
= h
11
= 15, а (W
000
)
∗
= W
000
. Рассматривая случай
(1, 5, 3){4}, заменяем в матрице (W
00
)
∗
элемент (w
00
)
∗
x4
= 0 на ∞ и получаем оценку h
112
= h
11
+ 2 = 17.
Так как h
111
< h
112
, то переходим к рассмотрению множества (1, 5, 3, 4)∅,
состоящего из двух гамильтоновых циклов (1, 5, 3, 4, 2, 6, 1) и (1, 5, 3, 4, 6, 2, 1).
Первый из этих циклов будет иметь вес ∞, поскольку (W
000
)
26
= ∞, а вес второго цикла 15, что соответствует оценке h
111
= 15. Поскольку оценки
h
2
, h
12
и h
112
больше h
111
, соответствующие множества не содержат гамиль- тонова цикла веса, меньшего 15, и поэтому цикл (1, 5, 3, 4, 6, 2, 1) является гамильтоновым циклом минимального веса.
§ 4.10.
Упорядоченные и бинарные деревья
Определим по индукции понятие упорядоченного дерева:
1) пустое множество и список (a), где a — некоторый элемент, является упорядоченным деревом;
2) если T
1
, T
2
, . . . , T
n
— непустые упорядоченные деревья, a — некоторый новый элемент, то список T = (a, T
1
, T
2
, . . . , T
n
) есть упорядоченное дерево.
При этом элемент a называется корнем упорядоченного дерева T ;
3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2.
Если T
1
, T
2
, . . . , T
n
— упорядоченные деревья, то список (T
1
, T
2
, . . . , T
n
)
называется упорядоченным лесом.
Для заданного упорядоченного дерева T определим множество S(T ) его
упорядоченных поддеревьев:
• если T = ∅, то S(T ) = ∅;
• если T = (a), то S(T ) = {(a)};
• если T = (a, T
1
, T
2
, . . . , T
n
), то S(T ) = S(T
1
) ∪ . . . ∪ S(T
n
) ∪ {T }.