Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
Рис. 4.1 ражать сеть улиц в городе: вершины графа — пере- крестки, а дуги — улицы с разрешенным направлением движения (улицы могут быть с односторонним и дву- сторонним движением). В виде графов можно предста- вить блок-схемы программ (вершины — блоки, а ду- ги — разрешенные переходы от одного блока к друго- му), электрические цепи, географические карты и мо- лекулы химических соединений, связи между людьми и группами людей. Перейдем к точным определениям. Графом называется алгебраическая система G = hM; Ri, где R — двух- местный предикатный символ. Элементы носителя M называются вершина- ми графа G, а элементы бинарного отношения R ⊆ M 2 — дугами. Таким образом, дугами являются пары вершин (a, b) ∈ R. При этом дуга (a, b) на- зывается исходящей из вершины a и заходящей в вершину b. Изображение графа G = hM; Ri получается путем расположения различ- ных точек на плоскости для каждой вершины a ∈ M, причем если (a, b) ∈ R, то проводится стрелка (дуга) из вершины a к вершине b. 4.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ 119 Пример 4.1.1. Изображение графа G с множеством вершин M = {1, 2, 3, 4} и множеством дуг R = {(1, 1), (1, 2), (2, 3), (3, 4), (4, 3), (4, 1)} представлено на рис. 4.1. ¤ При задании графа для нас не имеет значения природа a b • • ¡ ¡ ¡ ¡ ¡ µº : Рис. 4.2 связи между вершинами a и b, важно только то, что связь существует и информация о связях содержится во множестве дуг R. Однако часто возникают ситуации, при которых та- кой информации оказывается недостаточно, например, в слу- чаях, когда имеется несколько дуг, исходящих из вершины a и заходящих в вершину b. Такие дуги называются кратными (рис. 4.2). Тогда используется понятие мультиграфа. Мультиграфом G называется тройка hM, U, P i, в которой M — множе- ство вершин, U — множество дуг, а P ⊆ M × U × M — трехместный пре- дикат, называемый инцидентором и представляемый следующим образом: (a, u, b) ∈ P тогда и только тогда, когда дуга u исходит из вершины a и за- ходит в вершину b. Отметим, что любой граф можно представить в виде мультиграфа. Граф G = hM; Ri называется ориентированным (орграфом), если най- дется дуга (a, b) ∈ R такая, что (b, a) / ∈ R. Если же отношение R симметрич- но, т. е. из (a, b) ∈ R следует (b, a) ∈ R, то граф G называется неориентиро- ванным (неорграфом). Если одновременно пары (a, b) и (b, a) принадлежат R (рис. 4.3а), то информацию об этих дугах можно представить множеством [a, b] {(a, b), (b, a)}, называемым ребром, которое соединяет вершины a и b. При этом вершины a и b называются концами ребра [a, b]. Ребра изобража- ются линиями (без стрелок), соединяющими вершины (рис. 4.3б ). • • ¼ * a b • • ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ a b а б Рис. 4.3 120 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Если в мультиграфе вместо дуг рассматриваются ребра, то мультиграф также называется неориентированным. Отметим, что если в орграфе G = hM; Ri к каждой дуге (a, b) ∈ R добавить пару (b, a), то в результате образуется неорграф , который будем называть соответствующим данному орграфу G и обозначать через F (G). Пример 4.1.2. Орграфу G, изображенному на рис. 4.1, соответствует неорграф F (G), изображенный на рис. 4.4. ¤ Введенные в § 2.2 понятия морфизмов алгебраиче- • • • • ¡ ¡ ¡ ¡ ¡ H H H H H @ @ @ m ¢ ¢ ¢ ¢ ¢ 1 2 4 3 Рис. 4.4 ских систем для графов представляются следующим об- разом. Пусть G = hM; Ri, G 0 = hM 0 ; R 0 i — графы. Тогда отображение ϕ: M → M 0 является гомоморфизмом, ес- ли для любых вершин a, b ∈ M из (a, b) ∈ R следует (ϕ(a), ϕ(b)) ∈ R 0 . Биекция ϕ: M ↔ M 0 является изо- морфизмом графов, если (a, b) ∈ R ⇔ (ϕ(a), ϕ(b)) ∈ R 0 . Пример 4.1.3. Рассмотрим граф G, состоящий из множества вершин {1, 2, 3, 4} и множества дуг [1, 2] ∪ [3, 4] ∪ {(1, 3), (2, 4), (3, 2), (4, 1)} (рис. 4.5а). Граф G 0 = h{a, b, c}; [a, b] ∪ [b, c] ∪ {(a, c), (b, b)}i является гомоморфным образом графа G при гомоморфизме ϕ, в кото- ром ϕ(1) = a, ϕ(2) = b, ϕ(3) = c, ϕ(4) = b (рис. 4.5б ). Граф G 00 , по- казанный на рис. 4.5в, изоморфен графу G посредством изоморфизма ψ, при котором ψ(1) = a, ψ(2) = b, ψ(3) = c, ψ(4) = d. Отображение χ: {1, 2, 3, 4} ↔ {1, 2, 3, 4}, при котором χ(1) = 2, χ(2) = 1, χ(3) = 4, χ(4) = 3, является автоморфизмом графа G. ¤ • • • • ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ µ ¾ ¾ @ @ @ @ @ @ @ @ @ R 1 2 4 3 • • • - ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ A A A A A A A A A ±° ²¯ a c b • • • • - @ @ @ @ @ @ @ @ @ I ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ª - b a d c а б в Рис. 4.5 4.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ 121 Информация о структуре графа может быть задана матрицей бинарного отношения. Пусть G = hM; Ri — граф, в котором множество вершин имеет n элементов: M = {a 1 , a 2 , . . . , a n }. Матрицей смежности A G = (A ij ) графа G называется матрица порядка n, определенная следующим образом: A ij ( 1, если (a i , a j ) ∈ R, 0, если (a i , a j ) / ∈ R. Если A ij = 1, то вершина a j называется последователем вершины a i , а a i — предшественником a j . Вершины a i и a j называются смежными, если A ij = 1 или A ji = 1. Если G — мультиграф, то в матрице смежности A G элемент A ij по опреде- лению равен числу дуг, исходящих из вершины a i и заходящих в вершину a j (i, j ∈ {1, . . . , n}). Пример 4.1.4. Граф G, изображенный на рис. 4.6, имеет матрицу смежности • • • • • a 5 a 1 a 2 a 3 a 4 - ¡ ¡ ¡ ª m m Рис. 4.6 A G = 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 . ¤ Отметим, что если G — неорграф, то матрица смежности A G симметрична, т. е. не меняется при транспонировании: A T G = A G Петлей в графе G называется дуга, соединяющая вершину саму с собой. Если G — граф без петель, то в матрице смежности A G по главной диагонали стоят нулевые элементы: A G = 0 0 ∗ ∗ 0 . 122 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Пусть G 1 = hM 1 ; R 1 i, G 2 = hM 2 ; R 2 i — графы, в которых M 1 = {a 1 , . . . , a n }, M 2 = {b 1 , . . . , b n }. Если ϕ — изоморфизм графов G 1 и G 2 , действующий по правилу ϕ(a i ) = 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 изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга неко- торыми перестановками строк и столбцов. ¤ 4.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ 123 • • • • 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 . 124 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Если граф 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. ¤ |