Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
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 132 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ (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 равны единице. В общем случае мат- рица связности неорграфа является матрицей отношения эквивалентности, 4.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ 133 соответствующего разбиению множества вершин графа на компоненты связ- ности. Определим следующим образом матрицу контрдостижимости 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}. ¤ 134 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ § 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 являются периферийными. ¤ 4.4. РАССТОЯНИЯ В ГРАФАХ 135 Минимальный из эксцентриситетов графа 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. ¤ 136 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ § 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 , 4.5. НАХОЖДЕНИЕ КРАТЧАЙШИХ МАРШРУТОВ 137 показанного на рис. 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 |