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

126
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
•
6 6
6
-
±°
²¯
±°
²¯
±°
²¯
¡
¡
¡
¡
¡
¡
µ
¡
¡
¡
¡
¡
¡
µ
@
@
@
@
@
@
I
@
@
@
@
@
@
I
©©
©©
©©
©©
©©
©
©
*
H
H
H
H
H
H
H
H
H
H
H
H
Y
(2, a)
(2, b)
(2, c)
(1, a)
(1, c)
(1, b)
•
•
•
•
•
•
6 6
6
-
-
±°
²¯
±°
²¯
±°
²¯
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@¡
¡
¡
¡
¡
¡
µ
@
@
@
@
@
@
R
(a, 2)
(b, 2)
(c, 2)
(a, 1)
(c, 1)
(b, 1)
Рис. 4.16
Рис. 4.17
Неформально композиция G
1
[G
2
] означает, что каждая вершина a
графа G
1
заменяется на изоморфную копию G
a
графа G
2
, а затем,
если (a
1
, a
2
) ∈ R
1
, то между любыми вершинами b
1
из G
a
1
и b
2
из G
a
2
проводится дуга (b
1
, b
2
).
§ 4.3.
Маршруты. Достижимость. Связность
Пусть G = hM; Ri — граф. Последовательность
a
1
, u
1
, a
2
, u
2
, . . . , u
n
, a
n+1
,
(4.1)
где a
1
, a
2
, . . . , a
n+1
∈ M, u
1
, u
2
, . . . , u
n
∈ R, называется маршрутом, соеди- няющим вершины a
1
и a
n+1
((a
1
, a
n+1
)-маршрутом), если u
i
= (a
i
, a
i+1
),
i = 1, 2, . . . , n (рис. 4.18).
Очевидно, что маршрут (4.1) можно задать последовательностью a
1
, . . . ,
a
n+1
его вершин, а также последовательностью
u
1
, . . . , u
n
дуг. Число n дуг в маршруте (4.1) на-
•
•
•
•
•
¡
¡
¡
µ@
@
@
R
¡
¡
¡
µ
a
1
a
3
a
n
a
2
a
n+1
u
1
u
2
u
n
· · ·
Рис. 4.18
зывается его длиной.
Пусть G — неорграф. Маршрут (4.1) называ- ется цепью, если все ребра [a
1
, a
2
], . . . , [a
n
, a
n+1
]
различны, и простой цепью, если все его вер- шины, кроме, возможно, первой и последней,
различны. Маршрут (4.1) называется цикличе-
ским, если a
1
= a
n+1
. Циклическая цепь называется циклом, а циклическая простая цепь — простым циклом. Неорграф без циклов называется ацикли-
ческим. Минимальная из длин циклов неорграфа называется его обхватом.

4.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ
127
Пример 4.3.1. Рассмотрим граф, изображенный на рис. 4.19. В нем на- боры (1, 2), (1, 2, 4, 7), (3, 4, 5, 6) являются простыми цепями; (1, 2, 4, 7, 8, 4) —
цепь, не являющаяся простой; (1, 2, 4, 7, 8, 4, 2) — маршрут, не являющийся цепью; (1, 2, 4, 7, 8, 4, 1) — цикл, не являющийся простым; (1, 2, 4, 1) — про- стой цикл. Обхват этого графа равен 3. ¤
Пусть G — граф, возможно, ориентированный. Маршрут (4.1) называется
путем, если все его дуги различны. Путь (4.1) называется контуром, если
a
1
= a
n+1
. Граф, не имеющий контуров, называется бесконтурным. Вершина
b называется достижимой из вершины a, если существует (a, b)-путь.
Пример 4.3.2. Граф, изображенный на рис. 4.20,
•
•
•
•
•
•
•
•
¢
¢
¢
¢
¢
¢
A
A
A
A
A
A
1 2
3 4
5 6
7 8
Рис. 4.19
имеет контур (1, 2, 3). Вершина 5 достижима из любой другой вершины, а из вершины 5 не достижима ни одна из вершин. ¤
Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом.
Орграф G называется связным, если связным является соответствующий ему неорграф F (G). Граф G называ- ется сильно связным, если для каждой пары различных вершин a и b суще- ствуют (a, b)-маршрут и (b, a)-маршрут. Аналогично определяются понятия связности и сильной связности для мультиграфов.
Пример 4.3.3. Граф, показанный на рис. 4.19,
•
•
•
•
•
¾
¡
¡
¡
µ @
@
@
R
-
-
2 4
5 1
3
Рис. 4.20
является связным, орграф, представленный на рис.
4.20, — связным, но не сильно связным, а граф, изоб- раженный на рис. 4.21, не является связным. ¤
Заметим, что любой связный неорграф является сильно связным.
Всякий максимальный по включению (сильно) связный подграф данного графа называется его (сильной) связной компонентой или (сильной) ком-
понентой связности.
Граф, показанный на рис. 4.21, имеет две компоненты связности с мно- жеством вершин {1, 2, 3, 4} и {5, 6, 7}. Граф, представленный на рис. 4.20,
имеет три сильные компоненты, задаваемые множествами вершин {1, 2, 3},
{4} и {5}.

128
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
©©
©©
©©
HH
HH
HH
1 3
2 4
•
•
•
¢
¢
¢
¢
¢
¢A
A
A
A
A
A
5 7
6
Рис. 4.21
Теорема 4.3.1. Любой граф представляется в виде объединения непере-
секающихся связных (сильных) компонент (с возможным добавлением дуг
с концами из разных сильных компонент). Разложение графа на связные
(сильные) компоненты определяется однозначно. ¤
Таким образом, множества вершин связных компонент, а также силь- ных компонент образуют разбиение множества вершин графа, а число c(G)
связных компонент графа G определяется однозначно.
Следующая теорема позволяет по матрице смежности A
G
исследовать маршруты данного графа G.
Теорема 4.3.2. Если A
G
— матрица смежности графа G, то (i, j)-й
элемент матрицы A
k
G
= A
G
· . . . · A
G
|
{z
}
k раз
есть число (a
i
, a
j
)-маршрутов дли-
ны k. ¤
Следствие 4.3.3. 1. В графе G мощности n тогда и только тогда
существует (a
i
, a
j
)-маршрут (a
i
6= a
j
), когда (i, j)-й элемент матрицы
A
G
+ A
2
G
+ . . . + A
n−1
G
не равен нулю.
2. В графе G мощности n тогда и только тогда существует цикл, со-
держащий вершину a
i
, когда (i, i)-й элемент матрицы A
G
+ A
2
G
+ . . . + A
n
G
не равен нулю.
Пример 4.3.4. Определим с помощью матрицы смежности существова- ние (1, 3)-маршрута в графе G, изображенном на рис. 4.22. В матрице
A
G
=



0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0




4.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ
129
(1, 3)-элемент равен 0, т. е. (1, 3)-маршрутов длины 1 нет. В матрице
A
2
G
=



0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0






0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0


 =



1 1 0 0 1 2 0 1 1 0 1 1 1 0 1 2



(1, 3)-элемент также равен 0. В матрице
A
3
G
= A
2
G
· A
G
=



1 1 0 0 1 2 0 1 1 0 1 1 1 0 1 2






0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0


 =



1 0 1 2 3 1 2 3 1 2 0 1 2 3 0 1



(1, 3)-элемент равен 1, т. е. существует один (1, 3)-маршрут длины 3. Из ри- сунка видно, что этот маршрут определяется набором вершин (1, 4, 2, 3).
Эту последовательность можно найти на основе пере-
•
•
•
•
S
S
S¶
¶
¶
¾
1 2
3 4
Рис. 4.22
множения матрицы смежности: элемент (1, 3) мат- рицы A
3
G
получается при перемножении элемента (1, 2)
матрицы A
2
G
и элемента (2, 3) матрицы A
G
; в свою оче- редь элемент (1, 2) матрицы A
2
G
образуется при пере- множении элемента (1, 4) матрицы A
G
на элемент (4, 2)
матрицы A
G
; следовательно, двигаясь от 1 к 3 за три шага, получаем маршрут (1, 4, 2, 3).
В матрице A
3
G
элемент (4, 2) равен 3, т. е. существует 3 (4, 2)-маршрута длины 3: (4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2). ¤
Образуем из матрицы (b
ij
) = E + A
G
+ A
2
G
+ . . . + A
n−1
G
матрицу C = (c
ij
)
порядка n по следующему правилу:
c
ij
­
(
1, если b
ij
6= 0,
0, если b
ij
= 0.
Матрица C называется матрицей связности, если G — неорграф, и мат-
рицей достижимости, если G — орграф. В графе G тогда и только тогда существует (a
i
, a
j
)-маршрут (i 6= j), когда c
ij
= 1. Таким образом, в матри- це C содержится информация о существовании связей между различными элементами графа посредством маршрутов. Если G — связный неорграф,
то все элементы матрицы связности C равны единице. В общем случае мат- рица связности неорграфа является матрицей отношения эквивалентности,

130
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
соответствующего разбиению множества вершин графа на компоненты связ- ности.
Определим следующим образом
матрицу
контрдостижимости
Q = (q
ij
):
q
ij
­
(
1, если вершина a
i
достижима из вершины a
j
или i = j;
0
в противном случае.
Нетрудно заметить, что если C — матрица достижимости, то Q = C
T
Матрицы достижимости и контрдостижимости C = (c
ij
) и Q = (q
ij
) мож- но использовать для нахождения сильных компонент графа. Рассмотрим матрицу S = C ∗ Q, где операция ∗ означает поэлементное произведение матриц C и Q: s
ij
= c
ij
· q
ij
(см. § 1.5). Элемент s
ij
матрицы S равен 1 то- гда и только тогда, когда i = j или вершины a
i
и a
j
взаимно достижимы,
т. е. a
i
достижима из a
j
и a
j
достижима из a
i
. Таким образом, матрица S
является матрицей следующего отношения эквивалентности E:
a
i
E a
j
⇔ a
i
и a
j
находятся в одной сильной компоненте.
Следовательно, сильная компонента, содержащая вершину a
i
, состоит из эле- ментов a
j
, для которых s
ij
= 1.
Пример 4.3.5. Матрицы достижимости C и контрдостижимости Q гра- фа, изображенного на рис. 4.20, имеют вид
C =






1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1






, Q = C
T
=






1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1






,
S = C ∗ Q =






1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1






.
По 2-й строке матрицы S находим, что сильная компонента, содержащая вершину 2, состоит из вершин {1, 2, 3}. ¤

4.4. РАССТОЯНИЯ В ГРАФАХ
131
§ 4.4.
Расстояния в графах
Пусть G = hM; Ri — связный неорграф, a, b — две его несовпадаю- щие вершины. Длина кратчайшего (a, b)-маршрута называется расстоянием
между вершинами a и b и обозначается через ρ(a, b). Положим ρ(a, a) ­ 0.
Очевидно, что введенное таким образом расстояние удовлетворяет сле- дующим аксиомам метрики:
• ρ(a, b) > 0;
• ρ(a, b) = 0 ⇔ a = b;
• ρ(b, a) = ρ(a, b) (симметричность);
• ρ(a, b) 6 ρ(a, c) + ρ(c, b) (неравенство треугольника).
Если M = {a
1
, a
2
, . . . , a
n
}, то матрица P = (p
ij
), в которой p
ij
= ρ(a
i
, a
j
),
называется матрицей расстояний. Заметим, что P
T
= P , т. е. матрица P
симметрична.
Для фиксированной вершины a величина
e(a) ­ max{ρ(a, b) | b ∈ M}
называется эксцентриситетом вершины a. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее. Если P — матрица расстояний, то эксцентриситет e(a
i
) равен наиболь- шему из чисел, стоящих в i-й строке.
Максимальный среди всех эксцентриситетов вершин называется диамет-
ром графа G и обозначается через d(G):
d(G) ­ max{e(a) | a ∈ M}.
Вершина a называется периферийной, если e(a) = d(G).
Пример 4.4.1. Найдем диаметр графа G, изображенного на рис. 4.23.
Матрица расстояний P имеет вид






0 1 3 1 2 1 0 2 1 1 3 2 0 2 1 1 1 2 0 1 2 1 1 1 0






,
отсюда e(1) = 3, e(2) = 2, e(3) = 3, e(4) = 2, e(5) = 2 и, следовательно,
d(G) = 3. Вершины 1 и 3 являются периферийными. ¤

132
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Минимальный из эксцентриситетов графа G называется его радиусом
и обозначается через r(G):
r(G) ­ min{e(a) | a ∈ M}.
Вершина a называется центральной, если e(a) = r(G). Множество всех центральных вершин графа называется его центром.
Пример 4.4.2. 1. Радиус графа, показанного на рис. 4.23, равен 2, а его центром является множество {2, 4, 5}.
2. В полном графе K
n
все различные вершины смежны, и поэтому
d(K
n
) = r(K
n
) = 1. ¤
Задача нахождения центральных вершин возника-
•
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
1 3
2 4
5
Рис. 4.23
ет в практической деятельности людей. Пусть, например,
граф представляет собой сеть дорог, т. е. вершины соот- ветствуют населенным пунктам, а ребра — дорогам между ними. Требуется оптимально разместить больницы, пунк- ты обслуживания и т. п. В подобных ситуациях оптимиза- ция заключается в минимизации расстояния от места об- служивания до наиболее удаленного населенного пункта.
Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной тем, что приходит- ся учитывать и другие обстоятельства — расстояния между населенными пунктами, стоимость, время проезда и т. д. Для учета этих параметров ис- пользуются взвешенные графы.
Пусть G = hM; Ri — взвешенный граф, в котором вес каждой ду- ги (a, b) есть некоторое вещественное число µ(a, b). Весом маршрута
a
1
, a
2
, . . . , a
n
, a
n+1
называется число µ =
n
P
i=1
µ(a
i
, a
i+1
). Взвешенным рассто-
янием (w-расстоянием) ρ
w
(a, b) между вершинами a и b называется ми- нимальный из весов (a, b)-маршрутов. (a, b)-Маршрут, вес которого равен расстоянию ρ
w
(a, b), называется кратчайшим (a, b)-маршрутом во взвешен- ном графе G. Взвешенным эксцентриситетом e
w
(a) вершины a называется число max{ρ
w
(a, b) | b ∈ M}. Взвешенной центральной вершиной графа G
называется вершина a, для которой e
w
(a) = min{e
w
(b) | b ∈ M}. Взвешен- ный эксцентриситет центральной вершины называется взвешенным радиу-
сом графа G и обозначается через r
w
(G).
Пример 4.4.3. Во взвешенном графе G, показанном на рис. 4.8, цен- тральной вершиной является вершина “Новосибирск”, а r
w
(G) = 681. ¤

4.5. НАХОЖДЕНИЕ КРАТЧАЙШИХ МАРШРУТОВ
133
§ 4.5.
Нахождение кратчайших маршрутов
Пусть G = hM; Ri — взвешенный граф, имеющий n вершин и матрицу весов W = (w
ij
), w
ij
∈ R ∪ {∞}. Опишем некоторые методы нахождения взвешенного расстояния от фиксированной вершины a
i
∈ M (называемой
источником) до всех вершин графа G.
Мы будем предполагать, что в G отсутствуют контуры с отрицательным весом, поскольку, двигаясь по такому контуру достаточное количество раз,
можно получить маршрут, имеющий вес, меньший любого заведомо взятого числа, и тем самым задача нахождения расстояния становится бес- смысленной.
Определим алгоритм Форда—Беллмана. Зададим строку D
(1)
=
= (d
(1)
1
, d
(1)
2
, . . . , d
(1)
n
), полагая d
(1)
i
= 0, d
(1)
j
= w
ij
, i 6= j. В этой строке d
(1)
j
(j 6= i) есть вес w
ij
дуги (a
i
, a
j
), если дуга (a
i
, a
j
) су-
•
•
•
HH
HH
HH
j
©©
©©
©©
*
6
a
i
a
k
a
j
w
kj
d
(1)
k
d
(1)
j
Рис. 4.24
ществует, и d
(1)
j
­ ∞, если (a
i
, a
j
) /
∈ R. Теперь опреде- лим строку D
(2)
= (d
(2)
1
, d
(2)
2
, . . . , d
(2)
n
), полагая d
(2)
j
­
­ min{d
(1)
j
, d
(1)
k
+ w
kj
}
k=1,...,n
. Нетрудно заметить, что
d
(2)
j
— минимальный из весов (a
i
, a
j
)-маршрутов, со- стоящих не более чем из двух дуг (рис. 4.24).
Продолжая процесс, на шаге s определим строку
D
(s)
= (d
(s)
1
, d
(s)
2
, . . . , d
(s)
n
),
полагая
d
(s)
j
­ min{d
(s−1)
j
, d
(s−1)
k
+ w
kj
}
k=1,...,n
Искомая строка w-расстояний получается при s = n−1: d
(n−1)
j
= ρ
w
(a
i
, a
j
).
Действительно, на этом шаге из весов всех (a
i
, a
j
)-маршрутов, содержащих не более n − 1 дуг, выбирается наименьший, а каждый маршрут более чем с n− 1 дугами содержит контур, добавление которого к маршруту не умень- шает w-расстояния, так как мы предположили отсутствие контуров отрица- тельного веса. Работу алгоритма можно завершить на шаге k, если
D
(k)
= D
(k+1)
Пример 4.5.1. Продемонстрируем работу алгоритма Форда—Беллмана на примере взвешенного графа с матрицей весов
W =






0 1
∞ ∞
3
∞
0 3
3 8
∞ ∞
0 1
−5
∞ ∞
2 0
∞
∞ ∞ ∞
4 0






,