Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
b i , i = 1, . . . , n, то матрицы смежности A G 1 и A G 2 совпадают. В общем случае справедлива Теорема 4.1.1. Графы изоморфны тогда и только тогда, когда их мат- рицы смежности получаются друг из друга одновременными перестанов- ками строк и столбцов (т. е. одновременно с перестановкой i-й и j-й строк переставляются i-й и j-й столбцы). ¤ Согласно этой теореме граф восстанавливается однозначно, с точностью до изоморфизма, по своей матрице смежности. В мультиграфе G = hM, U, P i дуга u ∈ U называется инцидентной вер- шине a ∈ M, если (a, u, b) ∈ P или (b, u, a) ∈ P для некоторого b ∈ M . Если M = {a 1 , . . . , a m }, U = {u 1 , . . . , u n }, то матрицей инцидентности B G = (B ij ) мультиграфа G называется матрица размера m×n, определяемая по следующему правилу: B ij 1, если дуга u j исходит из вершины a i ; −1, если дуга u j заходит в вершину a i и u j не является петлей; 0 — в противном случае. Пример 4.1.5. Мультиграф G, изображенный на рис. 4.7, имеет матрицу инцидентности • • • ¾ l ® U µ R * a 1 a 3 a 2 1 2 3 4 5 6 Рис. 4.7 B G = −1 −1 0 0 0 0 1 1 1 1 −1 1 0 0 0 −1 1 −1 . ¤ Мультиграфы G = hM, U, P i и G 0 = hM 0 , U 0 , P 0 i называются изоморфными, если существуют биекции ϕ: M ↔ M 0 и ψ: U ↔ U 0 такие, что (a, u, b) ∈ P то- гда и только тогда, когда (ϕ(a), ψ(u), ϕ(b)) ∈ P 0 Аналогично теореме 4.1.1. справедлива Теорема 4.1.2. Мультиграфы G и G 0 изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга неко- торыми перестановками строк и столбцов. ¤ 120 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • • • • Q Q Q Q Q Q¡ ¡ ¡ ¡ Q Q Q Q Q Q 681 a 4 Павлодар a 3 Кемерово a 2 Новосибирск Омск a 1 413 274 589 Рис. 4.8 Во многих задачах требуется дополнительная информация о верши- нах и ребрах, например, о расстоянии между населенными пунктами в слу- чае, когда граф представляет собой сеть дорог, или о времени прохождения сигнала от одного узла связи к другому и т. д. В таких задачах используются взвешенные графы. Пусть S M , S R — множества меток. Пометкой или распределением меток графа G = hM; Ri называется пара функций f : M → S M (распределение меток вершин), g: R → S R (распределение меток дуг). Четверка hM, R, f, gi называется взвешенным или помеченным графом. Для вершины a ∈ M элемент f (a) называется весом вершины a, а для дуги u ∈ R элемент g(u) — весом дуги u. Часто бывают помеченными только вершины (в этом случае g = const) или дуги (в этом случае f = const). Пример 4.1.6. Пусть M = {a 1 , a 2 , a 3 , a 4 }, R = [a 1 , a 2 ] ∪ [a 2 , a 3 ] ∪ [a 1 , a 4 ]∪ ∪[a 2 , a 4 ], f : M → C, где C — множество городов, g: R → ω, f (a 1 ) = Омск, f (a 2 ) = Новосибирск, f (a 3 ) = Кемерово, f (a 4 ) = Павлодар, g([a 1 , a 2 ]) = 681, g([a 2 , a 3 ]) = 274, g([a 1 , a 4 ]) = 413, g([a 2 , a 4 ]) = 589. Помеченный граф hM, R, f, gi изображен на рис. 4.8 и представляет собой схему автомобильных дорог с указанием их протяженности. ¤ Информацию о весах дуг во взвешенном графе можно представлять в ви- де матрицы весов W = (w ij ), где w ij — вес дуги (a i , a j ), если дуга (a i , a j ) существует, а для несуществующих дуг веса обычно помечают нулем или знаком ∞ в зависимости от приложений. В примере 4.1.6 матрица весов имеет вид W = 0 681 ∞ 413 681 0 274 589 ∞ 274 0 ∞ 413 589 ∞ 0 . 4.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ 121 Если граф G = hM ; Ri является разреженным, т. е. число дуг |R| до- статочно мало по сравнению с числом вершин |M|, то более эффектив- ным, чем с помощью матрицы смежности, является представление дуг гра- фа посредством списка дуг. Этот список задается двумя наборами m = (m 1 , m 2 , . . . , m |R| ) и n = (n 1 , n 2 , . . . , n |R| ), где (a m i , a n i ) — i-я дуга графа G. Пример 4.1.7. Орграф, изображенный на рис. 4.6, представляется сле- дующим списком дуг: m = (1, 1, 2, 3, 4, 4), n = (1, 2, 3, 4, 3, 4). Для пред- ставления рассматриваемого графа матрицей смежности требуется 5 2 = 25 элементов, а списком дуг — только 6 · 2 = 12 элементов. ¤ Другим представлением графа, удобным при работе с графами, в кото- рых удаляются или добавляются вершины, является структура смежно- сти, получаемая составлением для каждой вершины a списка номеров ее последователей, т. е. номеров вершин b, для которых имеется дуга (a, b). Пример 4.1.8. Орграф, изображенный на рис. 4.6, представляется сле- дующей структурой смежности: Вершины Списки последователей 1: 1, 2 2: 3 3: 4 4: 3, 4 5: § 4.2. Подграфы и части графа. Операции над графами Граф G 0 = hM 0 ; R 0 i называется подграфом графа G = hM; Ri, если M 0 ⊆ M и R 0 = R ∩ (M 0 ) 2 . Граф G 0 называется частью графа G, если M 0 ⊆ M и R 0 ⊆ R ∩ (M 0 ) 2 Пример 4.2.1. Граф G 0 = h{1, 2, 3}; [1, 2] ∪ [2, 3] ∪ {(1, 3)}i (рис. 4.9б ) является подграфом графа G = h{1, 2, 3, 4}; [1, 2]∪[1, 4]∪[2, 3]∪[3, 4]∪{(1, 3)}i (рис. 4.9а), а граф G 00 = h{1, 2, 3}; [1, 2] ∪ {(3, 2)}i (рис. 4.9в) — частью графа G. ¤ 122 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • • • • - ¡ ¡ ¡ @ @ @ ¡ ¡ ¡ @ @ @ 1 1 1 3 3 3 2 2 2 4 • • • - ¡ ¡ ¡ @ @ @ • • • ¡ ¡ ¡ @ @ @ I а б в Рис. 4.9 Рассмотрим некоторые основные операции, производимые над графами. Операцией добавления к графу G = hM; Ri вершины a образуется граф hM ∪ {a}; Ri. Операция добавления дуги (a, b) к графу G состоит в образо- вании графа hM ∪ {a, b}; R ∪ {(a, b)}i. Под операцией удаления дуги (a, b) из графа G понимается операция, заключающаяся в удалении пары (a, b) из множества дуг R, в результате получается граф hM; R \ {(a, b)}i. Опера- ция удаления вершины a из графа G заключается в удалении вершины a вместе с инцидентными ей дугами: hM \ {a}; R \ {(b, c) | b = a или c = a}i. Операция отождествления вершин a и b графа G = hM; Ri состоит в удале- нии из графа G вершин a и b и присоединении новой вершины a 0 , дуг (a 0 , c), если (a, c) ∈ R или (b, c) ∈ R, и дуг (c, a 0 ), если (c, a) ∈ R или (c, b) ∈ R: h(M \ {a, b}) ∪ {a 0 }; (R \ {(c, d) | c = a, или d = a, или c = b, или d = b})∪ ∪{(a 0 , c) | (a, c) ∈ R или (b, c) ∈ R, c / ∈ {a, b}} ∪ {(c, a 0 ) | (c, a) ∈ R или (c, b) ∈ R, c / ∈ {a, b}} ∪ {(a 0 , a 0 ) | найдутся c, d ∈ {a, b}, где (c, d) ∈ R}i. Говорят, что построенный граф получается из графа G отождествлением вершин a и b. В случае, когда a и b соединены дугой, операцию отождеств- ления вершин a и b называют стягиванием дуги (a, b). Пример 4.2.2. Из графа G, показанного на рис. 4.10, добавлением вер- шины 5 образуется граф G 1 , добавлением дуги (3, 1) — граф G 2 , удалением дуги (3, 2) — граф G 3 , удалением вершины 2 — граф G 4 , отождествлением вершин 1 и 4 — граф G 5 , стягиванием дуги (2, 3) — граф G 6 . ¤ 4.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ 123 • • • • • • • • • • • • • • • • • • • • • • ? ? ? ? ? • • • • C C C C CC ¤ ¤ ¤ ¤ ¤¤ ±° ²¯ ¢ ¢ ¢ ¢ ¢ ¢® - ¢ ¢ ¢ ¢ ¢ ¢® 1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 1 0 2 1 4 2 0 G G 1 G 2 G 3 G 4 G 5 G 6 Рис. 4.10 Дополнением графа без петель G = hM; Ri называется граф G hM; M 2 \ (R ∪ id M )i. Пример 4.2.3. Дополнением графа G, изображенного на рис. 4.10, яв- ляется граф G, показанный на рис. 4.11. ¤ Пусть G 1 = hM 1 ; R 1 i, G 2 = hM 2 ; R 2 i — графы. Объедине- • • • • ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ 6 1 4 2 3 Рис. 4.11 нием G 1 ∪ G 2 графов G 1 и G 2 называется граф hM 1 ∪ M 2 ; R 1 ∪ R 2 i. Если M 1 ∩ M 2 6= ∅, то пересечением G 1 ∩ G 2 графов G 1 и G 2 называется граф hM 1 ∩M 2 ; R 1 ∩R 2 i. Кольцевой суммой G 1 ⊕ G 2 графов G 1 и G 2 называется граф hM 1 ∪ M 2 ; R 1 ⊕ R 2 i, где R 1 ⊕ R 2 = (R 1 \ R 2 ) ∪ (R 2 \ R 1 ). Пример 4.2.4. Для графов G 1 = h{a 1 , a 2 , a 3 }; [a 1 , a 2 ]∪ ∪{(a 2 , a 3 )}i и G 2 = h{a 1 , a 2 , a 4 }; {(a 1 , a 2 ), (a 4 , a 1 )}i (рис. 4.12) найдем G 1 ∪G 2 , G 1 ∩G 2 , G 1 ⊕G 2 . По определению имеем G 1 ∪G 2 = h{a 1 , a 2 , a 3 , a 4 }; [a 1 , a 2 ]∪ ∪{(a 2 , a 3 ), (a 4 , a 1 )}i, G 1 ∩ G 2 = h{a 1 , a 2 }; {(a 1 , a 2 )}i, G 1 ⊕ G 2 = h{a 1 , a 2 , a 3 , a 4 }; {(a 2 , a 1 ), (a 2 , a 3 ), (a 4 , a 1 )}i. ¤ Соединением G 1 + G 2 графов G 1 и G 2 называется граф hM 1 ∪ M 2 ; R 1 ∪ ∪R 2 ∪ ∪{[a, b] | a ∈ M 1 , b ∈ M 2 , a 6= b}i. Пример 4.2.5. Для графов G 1 и G 2 , показанных на рис. 4.13а, соедине- нием G 1 + G 2 является граф, представленный на рис. 4.13б. ¤ Часто при рассмотрении операции соединения графов предполагается, что M 1 ∩ M 2 = ∅. Произведением G 1 × G 2 графов G 1 и G 2 называется граф hM 1 × M 2 ; Ri, в котором ((a 1 , b 1 ), (a 2 , b 2 )) ∈ R тогда и только тогда, когда a 1 = a 2 и (b 1 , b 2 ) ∈ R 2 , или b 1 = b 2 и (a 1 , a 2 ) ∈ R 1 Пример 4.2.6. На рис. 4.14 изображено произведение G 1 × G 2 графов G 1 = h{1, 2}; {(1, 1), (2, 1)}i и G 2 = h{a, b, c}; [a, b] ∪ {(b, c)}i. ¤ 124 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • • • ¡ ¡ ¡@ @@ R a 1 a 2 a 3 G 1 • • • X X X X X X y »»» »» » : a 1 a 4 a 2 G 2 • • • • @ @ @ I ¡ ¡ ¡@ @@ R a 1 a 2 a 3 a 4 G 1 ∪ G 2 • • 6 a 1 a 2 G 1 ∩ G 2 • • • • @ @ @ I ¡ ¡ ¡ ª @ @@ R a 1 a 2 a 3 a 4 G 1 ⊕ G 2 Рис. 4.12 • • • ¢ ¢ ¢ ¢ ¢¢AA A A AAU ¾ a 1 a 3 a 2 • • • ¢ ¢ ¢ ¢ ¢ ¢ A A A A A AK a 2 a 4 a 5 а • • • • • ´ ´ ´ ´ ´ ´ ´ ´ ´ Q Q Q Q Q Q Q Q Q ¾ a 1 a 3 a 4 a 5 a 2 б Рис. 4.13 • • 6 j 2 1 G 1 × • • • - a b c G 2 = • • • • • • 6 6 6 n n n - - (2, a) (2, b) (2, c) (1, a) (1, b) (1, c) G 1 × G 2 Рис. 4.14 4.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ 125 • • • • (0, 0) (1, 0) (0, 1) (1, 1) • • • • • • • • ©© ©© © ©© ©© © HH HHH HH HHH (0, 0, 0) (0, 1, 0) (0, 0, 1) (0, 1, 1) (1, 0, 0) (1, 1, 0) (1, 0, 1) (1, 1, 1) Рис. 4.15 Неорграф без петель называется полным, если его любые две различ- ные вершины смежны. Полный граф, имеющий n вершин, обозначается че- рез K n С помощью операции произведения определим по индукции важ- ный класс графов, называемых n-мерными кубами (n-кубами). Рассмотрим граф K 2 , вершины которого обозначим 0 и 1. n-Мерный куб, или n-куб Q n , определяется по следующим правилам: Q 0 — граф без петель, состоящий из одной вершины, Q 1 K 2 , Q n K 2 × Q n−1 , n > 1. Вершинами n-мерного куба Q n являются всевозможные n-ки, состоящие из нулей и единиц (все- го таких наборов 2 n ), а ребра задаются по следующему правилу: вершины смежны тогда и только тогда, когда соответствующие кортежи различаются ровно одной координатой. На рис. 4.15 показаны двумерный Q 2 и трехмер- ный Q 3 кубы. Композицией G 1 [G 2 ] графов G 1 и G 2 называется граф hM 1 ×M 2 ; Ri, в ко- тором ((a 1 , b 1 ), (a 2 , b 2 )) ∈ R тогда и только тогда, когда выполняется одно из следующих условий: 1) (a 1 , a 2 ) ∈ R 1 ; 2) a 1 = a 2 и (b 1 , b 2 ) ∈ R 2 Пример 4.2.7. Композицией G 1 [G 2 ] графов G 1 и G 2 , рассмотренных в примере 4.2.6, является граф, изображенный на рис. 4.16, а композицией G 2 [G 1 ] — граф, представленный на рис. 4.17. ¤ 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 , 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 |