Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф
 Скачать 1.36 Mb.
|
|
c d a b c a c d d d d a d Имеет ли алгебра A подалгебру с носителем а) {a, b, c}; б) {a}; в) {a, d}? 6. Являются ли термами сигнатуры Σ = {f (1) , g (2) , h (3) } следующие выражения: а) f (g(x, y)); б) g(f (x), h(x, y, z)); в) f (g(x), h(x, y, z))? 7. Указать алгоритм построения всех термов сигнатуры Σ от переменной если аи б) Σ = {g (2) }. 2.7. ЗАДАЧИ И УПРАЖНЕНИЯ 8. Построить подсистему B(X), порожденную данным множеством а) B = R; 3 √ , X = {2}; б) B = ω; + , X = {2, в) B = C; · , X = { ı}; г) B = C; ·, 2 , X = { ı}. 9. Рассмотрим алгебру A = {a, b, c, d, e}; · , определенную следующей таблицей Кэли: · a b c d e a c d a b e b d c b b e c a a b a c d b a a b d e a b e e Какое из следующих разбиений образует конгруэнцию на алгебре а) {{a, b, c}, {d, e}}; б) {a, b}, {c, d}, Построить фактор-алгебру алгебры A по найденной конгруэнции. 10. Доказать, что любое л.у.м. является решеткой. Доказать, что в решетке максимальный элемент является наибольшим, а минимальный — наименьшим. Построить пример решетки с наибольшим элементом, но без наименьшего. Построить булеву алгебру подмножеств трехэлементного (четырехэлементного) множества. Для терма x ∨ (y ∧ z) булевой алгебры найти соответствующий терм в булевом кольце. После изучения главы 2 выполняются задачи 6 и 7 контрольной работы. Задача 6 решается аналогично примеру 2.1.1, а задача 7 — аналогично примеру 2.3.4. Глава ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Виды и способы задания графов Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты называются вершинами и отмечаются точками, а связи между вершинами называются дугами и отмечаются стрелками между соответствующими точками (рис. Такие системы и образуют графы. Граф может r r r r d d d m © ! 1 2 4 Рис. изображать сеть улиц в городе вершины графа перекрестки, а дуги — улицы с разрешенным направлением движения (улицы могут быть с односторонними двусторонним движением. В виде графов можно представить блок-схемы программ (вершины блоки, а дуги — разрешенные переходы от одного блока к другому, электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. Перейдем к точным определениям. Графом называется алгебраическая система G = M ; R , где R двухместный предикатный символ. Элементы носителя M называются вершинами графа G, а элементы бинарного отношения R ⊆ дугами. Таким образом, дугами являются пары вершин (a, b) ∈ R. При этом дуга (a, b) называется исходящей из вершины a и заходящей в вершину Изображение графа G = M; R получается путем расположения различных точек на плоскости для каждой вершины a ∈ M, причем если (a, b) ∈ R, то проводится стрелка (дуга) из вершины a к вершине Пример. Изображение графа G с множеством вершин M = {1, 2, 3, 4} и множеством дуг R = {(1, 1), (1, 2), (2, 3), (3, 4), (4, 3), (4, представлено на рис. При задании графа для нас не имеет значения природа связи между 3.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ 53 вершинами a и b, важно только то, что связь существует и информация о связях содержится во множестве дуг R. Однако часто возникают ситуации, при которых такой информации оказывается недостаточно, например, в случаях, когда имеется несколько дуг, исходящих из вершины a и заходящих в вершину b. Такие дуги называются кратными (рис. 3.2). Тогда используется понятие мультиграфа. Мультиграфом G называется тройка M, U, P , в Рис. которой M — множество вершин, U — множество дуга трехместный предикат, называемый инцидентором и представляемый следующим образом, u, b) ∈ P тогда и только тогда, когда дуга u исходит из вершины a и заходит в вершину b. Отметим, что любой граф можно представить в виде мультиграфа. Граф G = M ; R называется ориентированным (орграфом, если найдется дуга (a, b) ∈ R такая, что (b, a) / ∈ R. Если же отношение симметрично, те. из (a, b) ∈ R следует (b, a) ∈ R, то граф G называется неориентированным (неорграфом). Если одновременно пары (a, и (b, a) принадлежат R (риса, то информацию об этих дугах можно представить множеством [a, b] = {(a, b), (b, a)}, называемым ребром, которое соединяет вершины a и b. При этом вершины a и b называются концами ребра [a, b]. Ребра изображаются линиями (без стрелок), соединяющими вершины (рис. б Если в мультиграфе вместо дуг рассматриваются ребра, то муль- тиграф также называется неориентированным. Отметим, что если в орграфе G = M ; R к каждой дуге (a, b) ∈ R добавить пару (b, a), тов результате образуется неорграф , который будем называть соответствующим данному орграфу G и обозначать через F Пример. Орграфу G, изображенному на рис. 3.1, соответствует неорграф F (G), изображенный на рис. Введенные в § 2.2 понятия морфизмов алгебраических систем для графов представляются следующим образом. Пусть G = M ; R , G = M ; R — графы. Тогда отображение ϕ : M → M является гомоморфизмом, если для любых вершин a, b ∈ из (a, b) ∈ R • • % B a b • • a а б Рис. 3.3 Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ следует (ϕ(a), ϕ(b)) ∈ R . Биекция ϕ : M ↔ M является изоморфизмом графов, если (a, b) ∈ R ⇔ (ϕ(a), ϕ(b)) ∈ R Пример. Рассмотрим граф G, состоя r r r r d d d m ¡ ¡ ¡ ¡ ¡ 1 2 4 Рис. 3.4 щий из множества вершин {1, 2, 3, 4} и множества дуг [1, 2] ∪ [3, 4] ∪ {(1, 3), (2, 4), (3, 2), (4, 1)} (риса. Граф G = {a, b, c}; [a, b]∪[b, c]∪{(a, c), (b, является гомоморфным образом графа G при гомоморфизме, в котором ϕ(1) = a, ϕ(2) = b, ϕ(3) = c, ϕ(4) = b (рис. б ). Граф G , показанный на рис. в, изоморфен графу G посредством изоморфизма, при котором ψ(1) = a, ψ(2) = = b, ψ(3) = c, ψ(4) = d. Отображение, при котором χ(1) = 2, χ(2) = 1, χ(3) = 4, χ(4) = 3, является автоморфизмом графа Информация о структуре графа может быть задана матрицей бинарного отношения. Пусть G = M; R — граф, в котором множество вершин имеет n элементов M = {a 1 , a 2 , . . . , a n }. Матрицей смежности) графа G называется матрица порядка n, определенная следующим образом: A ij 1, если (a i , a j ) ∈ если (a i , a j ) / ∈ Если A ij = 1, то вершина a называется последователем вершины a i , а a i — предшественником a j . Вершины a и a называются смежными, если A ij = 1 или A ji = Если G — мультиграф, тов матрице смежности элемент A ij по определению равен числу дуг, исходящих из вершины a и заходящих в вершину a j (i, j ∈ {1, . . . , Пример. Граф G, изображенный на рис. 3.6, имеет матрицу смежности d d d d d 1 2 4 3 • • • E ¡ ¡ ¡ ¡ ¡ ¡ e e e e e e k a c b • • • • E d d d d d d s © E b a d а б в Рис. 3.5 3.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 Отметим, что если G — неорграф, то матрица смежности симметрична, те. не меняется при транспонировании A T G = Петлей в графе G называется дуга, соединя- • • • • • a 5 a 1 a 2 a 3 a 4 E © m Рис. 3.6 ющая вершину саму с собой. Если G — граф без петель, тов матрице смежности по главной диагонали стоят нулевые элементы. Пусть G 1 = M 1 ; R 1 , G 2 = M 2 ; R 2 — графы, в которых M 1 = {a 1 , . . . , a n }, M 2 = {b 1 , . . . , b Если ϕ — изоморфизм графов и G 2 , действующий по правилу ϕ(a i ) = b i , i = 1, . . . , n, то матрицы смежности и совпадают. В общем случае справедлива Теорема 3.1.1. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременными перестановками строки столбцов (те. одновременно с перестановкой й и й строк переставляются й и й столбцы). Согласно этой теореме по матрице смежности граф восстанавливается однозначно с точностью до изоморфизма. В мультиграфе G = M, U, P дуга 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 исходит из вершины a i ; −1, если дуга u заходит в вершину a и u не является петлей — в противном случае. П р им ер. Мультиграф G, изображенный на рис. 3.7, имеет матрицу инцидентности Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ −1 0 0 0 0 1 1 1 1 −1 1 0 0 0 −1 1 −1 . Мультиграфы G = M, U, P и G = = M , U , называются изоморфными, если существуют биекции ϕ : M ↔ M и ψ : U ↔ такие, что (a, u, b) ∈ P тогда и только тогда, когда (ϕ(a), ψ(u), ϕ(b)) ∈ ∈ P Аналогично теореме 3.1.1. справедлива Теорема 3.1.2. Мультиграфы G и G изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строки столбцов. Во многих задачах требуется дополнитель- • • • ' k B a 1 a 3 a 2 1 2 3 4 Рис. 3.7 ная информация о вершинах и ребрах, например, о расстоянии между населенными пунктами в случае, когда граф представляет собой сеть дорог, или о времени прохождения сигнала от одного узла связи к другому и т. д. В таких задачах используются взвешенные графы. Пусть S M , S R — множества меток. Пометкой или распределением меток графа G = M ; R называется пара функций распределение меток вершин, g : R → распределение меток дуг. Четверка M, R, f, g называется взвешенным или помеченным графом. Для вершины a ∈ M элемент f (a) называется весом вершины a, а для дуги u ∈ R элемент g(u) — весом дуги u. Часто бывают помеченными только вершины (в этом случае g = const) или дуги (в этом случае f = Пример. Пусть 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 ) Павлодар, a 2 ]) = 681, g([a 2 , a 3 ]) = 274, g([a 1 , a 4 ]) = 413, g([a 2 , a 4 ]) = 589. Помеченный граф M, R, f, g изображен на рис. и представляет собой схему автомобильных дорог с указанием их про- тяженности. Информацию о весах дуг во взвешенном графе можно представлять в виде матрицы весов W = (w ij ), где w ij — вес дуги (a i , a j ), если дуга i , a j ) существует, а для несуществующих дуг веса обычно помечают нулем или знаком ∞ в зависимости от приложений. В примере 3.1.6 3.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ Павлодар Кемерово a 2 Новосибирск Омск a 1 413 274 Рис. матрица весов имеет вид = 0 681 ∞ 413 681 0 274 589 ∞ 274 0 ∞ 413 589 Если граф G = M; R является разреженным, те. число дуг достаточно мало по сравнению с числом вершин |M |, то более эффективным, чем с помощью матрицы смежности, является представление дуг графа посредством списка дуг. Этот список задается двумя наборами) и n = = (n 1 , n 2 , . . . , n |R| ), где (a m i , a n i ) я дуга графа Пример. Орграф, изображенный на рис. 3.6, представляется следующим списком дуг m = (1, 1, 2, 3, 4, 4), n = = (1, 2, 3, 4, 3, Для представления рассматриваемого графа матрицей смежности требуется элементов, а списком дуг — только 6 · 2 = 12 элементов. Другим представлением графа, удобным при работе с графами, в которых удаляются или добавляются вершины, является структура смежности, получаемая составлением для каждой вершины a списка номеров ее последователей, те. номеров вершин b, для которых имеется дуга (a, Пример. Орграф, изображенный на рис. 3.6, представляется следующей структурой смежности: Вершины Списки последователей, 2 2: 3 3: 4 4: 3, 4 5: Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 3.2. Подграфы и части графа. Операции над графами Граф G = M ; R называется подграфом графа G = M ; R , если ⊆ M и R = R ∩ (M ) 2 . Граф G называется частью графа G, если ⊆ M и R ⊆ R ∩ (M Пример. Граф G = {1, 2, 3}; [1, 2] ∪ [2, 3] ∪ {(1, 3)} (рис. 3.9б ) является подграфом графа G = {1, 2, 3, 4}; [1, 2]∪ ∪[1, 4]∪[2, 3]∪ [3, 4] ∪ {(1, 3)} (риса, аграф (рис. 3.9в) — частью графа Рассмотрим некоторые основные операции, производимые над гра- фами. Операцией добавления к графу G = M ; R вершины a образуется граф M ∪ {a}; R . Операция добавления дуги (a, b) к графу G состоит в образовании графа M ∪{a, b}; R ∪{(a, b)} . Под операцией удаления дуги (a, b) из графа G понимается операция, заключающаяся в удалении пары (a, b) из множества дуг R, в результате получается граф R \ {(a, b)} . Операция удаления вершины a из графа G заключается в удалении вершины a вместе с инцидентными ей дугами \ {a}; R \ {(b, c)|b = a или c = a} Операция отождествления вершин a и b графа G = M; R состоит в удалении из графа G вершин a и b и присоединении новой вершины a , дуг (a , c), если (a, c) ∈ R или (b, c) ∈ R, и дуг (c, a ), если (c, a) ∈ или (c, b) ∈ R: (M \ {a, b}) ∪ {a }; (R \ {(c, d)|c = a или d = a, или c = или d = b}) ∪ {(a , c)|(a, c) ∈ R, или (b, c) ∈ R}∪ ∪{(c, a )|(c, a) ∈ R, или (c, b) ∈ R} Говорят, что построенный граф получается из графа G отождествлением вершин a и b. В случае, когда a и b соединены дугой, операцию d d d d d 1 1 1 3 3 3 2 2 2 4 • • • E d d d • • • d d d а б в Рис. 3.9 3.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ c c c c • • • • g g g g gg £ £ £ £ ££ ¡ ¡ ¡ ¡ ¡ ¡ E ¡ ¡ ¡ ¡ ¡ ¡ 1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 1 2 1 4 Рис. отождествления вершин a и b называют стягиванием дуги (a, Пример. Из графа G, показанного на рис. 3.10, добавлением вершины 5 образуется граф G 1 , добавлением дуги (3, 1) — граф удалением дуги (3, 2) — граф G 3 , удалением вершины 2 — граф отождествлением вершин 1 и 4 — граф G 5 , стягиванием дуги (2, 3) граф Дополнением графа без петель G = M ; R называется граф G = M; M 2 \ (R ∪ id M ) Пример. Дополнением графа G, изображенного на рис, является граф G, показанный на рис. Пусть G 1 = M 1 ; R 1 , G 2 = M 2 ; R 2 — графы. Объединением графов и называется граф M 1 ∪ M 2 ; Если M 1 ∩ M 2 = ∅, то пересечением графов d d d d d T 1 4 2 Рис. и называется граф M 1 ∩ M 2 ; Кольцевой суммой G 1 ⊕ графов и называется граф M 1 ∪ M 2 ; R 1 ⊕ R 2 , где R 1 ⊕ R 2 = (R 1 \ R 2 ) ∪ (R 2 \ R 2 Пример. Для графов G 1 = {a 1 , a 2 , a 3 }; [a 1 , a 2 ] ∪ {(a 2 , ирис) найдем G 1 ∪G 2 , G 1 ∩G 2 , G 1 ⊕G 2 . По определению имеем G 1 ∪ G 2 = {a 1 , a 2 , a 3 , a 4 }; [a 1 , a 2 ] ∪ {(a 2 , a 3 ), (a 4 , a 1 )} , G 1 ∩ G 2 = {a 1 , a 2 }; {(a 1 , a 2 )} , G 1 ⊕ G 2 = {a 1 , a 2 , a 3 , a 4 }; {(a 2 , a 1 ), (a 2 , a 3 ), (a 4 , a 1 )} . • • • d d a 1 a 2 a 3 G 1 • • • y $$$ $ X a 1 a 4 a 2 G 2 • • • • d d s d d a 1 a 2 a 3 a 4 G 1 ∪ G 2 • • T a 1 a 2 G 1 ∩ G 2 • • • • d d s © d d a 1 a 2 a 3 a 4 G 1 ⊕ Рис. 3.12 Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ e e e ee ' a 1 a 3 a 2 • • • ¡ ¡ ¡ ¡ ¡ ¡ e e e e e eu a 2 a 4 a 5 а • • • • • ' a 1 a 3 a 4 a 5 a 2 б Рис. Соединением G 1 + графов и называется граф M 1 ∪ M 2 ; R 1 ∪ R 2 ∪ ∪{[a, b]|a ∈ M 1 , b ∈ M 2 , a = b} Пример. Для графов и G 2 , показанных на рис. 3.13а, соединением G 1 + является граф, представленный на рис. 3.13б. Произведением G 1 × графов и называется граф M 1 × M 2 ; R , в котором ((a 1 , b 1 ), (a 2 , b 2 )) ∈ R тогда и только тогда, когда a 1 = и (b 1 , b 2 ) ∈ R 2 , или b 1 = и (a 1 , a 2 ) ∈ Пример. На рис. 3.14 изображено произведение G 1 × графов G 1 = {1, 2}; {(1, 1), (2, 1)} и G 2 = {a, b, c}; [a, b] ∪ {(b, c)} . Неорграф без петель называется полным, если его любые две различные вершины смежны. Полный граф, имеющий n вершин, обозначается через С помощью операции произведения определим по индукции важный класс графов, называемых мерными кубами (кубами. Рассмотрим граф K 2 , вершины которого обозначим 0 и 1. Мерный куб, или куб Q n , определяется последующим правилам Q 0 — граф без петель, состоящий из одной вершины, Q 1 K 2 , Q n K 2 × Q n−1 , n > 1. Вершинами мерного куба Q n являются всевозможные n-ки, состоящие из нулей и единиц (всего таких наборов 2 n ), а ребра задаются последующему правилу вершины смежны тогда и только тогда, когда соответствующие кортежи различаются ровно одной координатой. На рис. 3.15 показаны двумерный и трехмерный кубы 1 G 1 × • • • E a b c G 2 = • • • • • • T T T E E (2, a) (2, b) (2, c) (1, a) (1, b) (1, c) G 1 × Рис. 3.14 3.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ, 0) (1, 0) (0, 1) (1, 1) • • • • • • • • ¨¨ ¨ ¨¨ ¨ rr r rr r (0, 0, 0) (0, 1, 0) (0, 0, 1) (0, 1, 1) (1, 0, 0) (1, 1, 0) (1, 0, 1) (1, 1, Рис. 3.15 • • • • • • T T T E m m m d d d d d s d d d d d s ¨¨ ¨¨ ¨¨ ¨¨ ¨ B r r r r r r r r r (2, a) (2, b) (2, c) (1, a) (1, c) (1, b) • • • • • • T T T E E m m m d d d d d d d d d d (a, 2) (b, 2) (c, 2) (a, 1) (c, 1) (b, Рис. Рис. Композицией G 1 [G 2 ] графов и называется граф M 1 ×M 2 ; R в котором ((a 1 , b 1 ), (a 2 , b 2 )) ∈ R тогда и только тогда, когда выполняется одно из следующих условий) (a 1 , a 2 ) ∈ R 1 ; 2) a 1 = и (b 1 , b 2 ) ∈ Пример. Композицией G 1 [G 2 ] графов и G 2 , рассмотренных в примере 3.2.6, является граф, изображенный на риса композицией G 2 [G 1 ] — граф, представленный на рис. Неформально композиция G 1 [G 2 ] означает, что каждая вершина a графа заменяется на изоморфную копию G a графа G 2 , а затем, если (a 1 , a 2 ) ∈ R 1 , то между любыми вершинами из и из проводится дуга (b 1 , b 2 ). § Маршруты. Достижимость. Связность Пусть G = M ; R — граф. Последовательность a 1 , u 1 , a 2 , u 2 , . . . , u n , a где a 1 , a 2 , . . . , a n+1 ∈ M, u 1 , u 2 , . . . , u n ∈ R, называется маршрутом, соединяющим вершины и a n+1 ((a 1 , a маршрутом, если u i = (a i , a i+1 ), i = 1, 2, . . . , n (рис. Очевидно, что маршрут (3.1) можно задать последовательностью a 1 , . . . , a его вершина также последовательностью u 1 , . . . , u дуг. Число n дуг в маршруте (3.1) называется его длиной. Пусть G — неорграф. Маршрут (3.1) называется цепью, если все ребра [a 1 , a 2 ], . . . , [a n , a n+1 ] различны, и простой цепью, если все его Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ d d d d d d a 1 a 3 a n a 2 a n+1 u 1 u 2 u n · · Рис. вершины, кроме, возможно, первой и последней, различны. Маршрут) называется циклическим, если a 1 = a n+1 . Циклическая цепь называется циклом, ациклическая простая цепь — простым циклом. Неорграф без циклов называется ациклическим. Минимальная из длин циклов неорграфа называется его обхватом. П р им ер. Рассмотрим граф, изображен e e e e e 1 2 3 4 5 6 7 Рис. 3.19 ный на рис. 3.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) — простой цикл. Обхват этого графа равен Пусть G — граф, возможно, ориентированный d d d E E 2 4 5 Рис. Маршрут (3.1) называется путем, если все его дуги различны. Путь (3.1) называется контуром, если a 1 = a n+1 . Граф, не имеющий контуров, называется бесконтурным. Вершина b называется достижимой из вершины a, если существует (a, b)-путь. П р им ер. Граф, изображенный на рис. 3.20, имеет контур, 2, 3). Вершина 5 достижима из любой другой вершины, а из вершины недостижима ни одна из вершин. Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф G называется связным, если соответствующий ему неорграф F (G) тоже является связным. Граф называется сильно связным, если для каждой пары различных вершин и b существуют (a, маршрут и (b, маршрут. Аналогично определяются понятия связности и сильной связности для мультигра- фов. П р им ер. Граф, показанный на рис. 3.19, является связным, орграф, представленный на рис. 3.20, — связным, ноне сильно связным, аграф, изображенный на рис. 3.21, не является связным 3.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ rr rr rr 1 3 2 4 • • • ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡e e e e e e e e 5 Рис. Заметим, что любой связный неорграф является сильно связ- ным. Всякий максимальный по включению (сильно) связный подграф данного графа называется его (сильной) связной компонентой или (сильной) компонентой связности. Граф, показанный на рис. 3.21, имеет две компоненты связности с множеством вершин {1, 2, 3, 4} и {5, 6, 7}. Граф, представленный на рис. 3.20, имеет три сильные компоненты, задаваемые множествами вершин {1, 2, 3}, {4} и Теорема 3.3.1. Любой граф представляется в виде объединения непересекающихся связных (сильных) компонент. Разложение графа на связные (сильные) компоненты определяется однозначно. Таким образом, множества вершин связных компонента также сильных компонент образуют разбиение множества вершин графа, а число c(G) связных компонент графа G определяется однозначно. Следующая теорема позволяет по матрице смежности исследовать маршруты данного графа Теорема 3.3.2. Если A G — матрица смежности графа G, той элемент матрицы A k G = A G · . . . · A G k раз есть число (a i , a маршрутов длины Следствие 3.3.3. 1. В графе G мощности n тогда и только тогда существует (a i , a маршрут (a i = a j ), когда (i, й элемент матрицы A G + A 2 G + . . . + неравен нулю. В графе G мощности n тогда и только тогда существует цикл, содержащий вершину a i , когда (i, й элемент матрицы A G + A 2 G + . . . + неравен нулю Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ П р им ер. Определим с помощью матрицы смежности существование, маршрута в графе G, изображенном на рис. В матрице 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 (1, элемент равен 0, те, маршрутов длины 1 нет. В матрице 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, элемент также равен 0. В матрице 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, элемент равен 1, те. существует один (1, маршрут длины Из рисунка видно, что этот маршрут определя- • • • • ' 1 2 3 Рис. 3.22 ется набором вершин (1, 4, 2, 3). Эту последовательность можно найти на основе перемножения матрицы смежности элемент (1, 3) матрицы получается при перемножении элемента (1, 2) матрицы и элемента (2, 3) матрицы A G ; в свою очередь элемент) матрицы образуется при перемножении элемента (1, матрицы на элемент (4, 2) матрицы A G ; следовательно, двигаясь от 1 к 3 затри шага, получаем маршрут (1, 4, 2, В матрице элемент (4, 2) равен 3, те. существует 3 (4, маршрута длины 3: (4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, Образуем из матрицы (b ij ) = E + A G + A 2 G + · · · + матрицу = (c ij ) порядка n последующему правилу ij 1, если b ij = 0, 0, если b ij = Матрица C называется матрицей связности, если G — неорграф, и матрицей достижимости, если G — орграф. В графе G тогда и 3.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ 65 только тогда существует (a i , a маршрут (i = j), когда c ij = 1. Таким образом, в матрице C содержится информация о существовании связей между различными элементами графа посредством маршрутов. Если — связный неорграф, то все элементы матрицы связности C равны единице. В общем случае матрица связности неорграфа является матрицей отношения эквивалентности, соответствующего разбиению множества вершин графа на компоненты связности. Определим следующим образом матрицу контрдостижимости Q = (q ij ): q ij 1, если вершина a достижима из вершины a или i = в противном случае. Нетрудно заметить, что если C — матрица достижимости, то Q = Матрицы достижимости и контрдостижимости C = (c ij ) и Q = (q ij ) можно использовать для нахождения сильных компонент графа. Рассмотрим матрицу S = C ∗Q, где операция ∗ означает поэлементное произведение матриц C и Q: s ij = c ij · q см. § 1.5). Элемент s ij матрицы S равен 1 тогда и только тогда, когда i = j или вершины a и a j взаимно достижимы, те достижима из a и a достижима из a Таким образом, матрица S является матрицей следующего отношения эквивалентности E: a i E a j ⇔ a и a находятся водной сильной компоненте. Следовательно, сильная компонента, содержащая вершину a i , состоит из элементов a j , для которых s ij = Пример. Матрицы достижимости C и контрдостижимости Q графа, изображенного на рис. 3.20, имеют вид = 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 Пой строке матрицы S находим, что сильная компонента, содержащая вершину 2, состоит из вершин {1, 2, 3}. Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Расстояния в графах Пусть G = M ; R — связный неорграф, a, b — две его несовпада- ющие вершины. Длина кратчайшего (a, маршрута называется расстоянием между вершинами a и b и обозначается через ρ(a, b). Положим. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики ρ(a, b) 0; — ρ(a, b) = 0 ⇔ a = b; — ρ(b, a) = ρ(a, b) (симметричность ρ(a, b) ρ(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 ) равен наибольшему из чисел, стоящих в й строке. Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G): d(G) max{e(a) | a ∈ M Вершина a называется периферийной, если e(a) = Пример. Найдем диаметр графа G, изображенного на рис. Матрица расстояний P имеет вид 1 3 1 2 1 0 2 1 1 3 2 0 2 1 1 1 2 0 1 2 1 1 1 отсюда e(1) = 3, e(2) = 2, e(3) = 3, e(4) = 2, e(5) = 2 и, следовательно) = 3. Вершины 1 и 3 являются периферийными. Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r(G): r(G) min{e(a) | a ∈ M}. 3.5. НАХОЖДЕНИЕ КРАТЧАЙШИХ МАРШРУТОВ 67 Вершина a называется центральной, если e(a) = r(G). Множество всех центральных вершин графа называется его центром. П р им ер. Радиус графа, показанного на рис. 3.23, равен, а его центром является множество {2, 4, 5}. 2. В полном графе K n все различные вершины смеж- • • • • • d d d 1 3 2 Рис. 3.23 ны, и поэтому d(K n ) = r(K n ) = Задача нахождения центральных вершин возникает в практической деятельности людей. Пусть, например, граф представляет собой сеть дорог, те. вершины соответствуют населенным пунктам, а ребра — дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т. п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной тем, что приходится учитывать и другие обстоятельства — расстояния между населенными пунктами, стоимость, время проезда и т. д. Для учета этих параметров используются взвешенные графы. Пусть G = M ; R — взвешенный граф, в котором вес каждой дуги) есть некоторое вещественное число µ(a, b). Весом маршрута a 1 , a 2 , . . . , a n , a называется число µ = n i=1 µ(a i , a i+1 ). Взвешенным расстоянием (расстоянием) ρ w (a, b) между вершинами a и b называется минимальный из весов (a, маршрутов. (a, Маршрут, вес которого равен расстоянию ρ 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 Пример. Во взвешенном графе G, показанном на рис. центральной вершиной является вершина Новосибирска Нахождение кратчайших маршрутов Пусть G = M ; R — взвешенный граф, имеющий n вершин и матрицу весов W = (w ij ), w ij ∈ R. Опишем некоторые методы нахож- Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ дения взвешенного расстояния от фиксированной вершины a i ∈ называемой источником) до всех вершин графа Мы будем предполагать, что в G отсутствуют контуры с отрицательным весом, поскольку, двигаясь по такому контуру достаточное количество раз, можно получить маршрут, имеющий вес, меньший любого заведомо взятого числа, и тем самым задача нахождения расстояния становится бессмысленной. Определим алгоритм Форда—Беллмана. Зададим строку D (1) = (d (1) 1 , d (1) 2 , . . . , полагая d (1) i = 0, d (1) j = w ij , i = j. В этой строке d (1) j (j = i) есть вес w ij дуги (a i , a j ), если дуга (a i , a j ) существует, и 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 маршрутов, состоящих не более чем из двух дуг (рис. Продолжая процесс, на шаге s определим стро- • • • rr rr rr j ¨¨ ¨¨ ¨¨ B T a i a k a j w kj d (1) k Риску, полагая d (s) j min{d (s−1) j , d (s−1) k + +w kj } k=1,...,n . Искомая строка расстояний получается при s = n − 1: d (n−1) j = ρ w (a i , a j ). Действительно, на этом шаге из весов всех (a i , a маршрутов, содержащих не более n − 1 дуг, выбирается наименьший, а каждый маршрут более чем с n − 1 дугами содержит контур, добавление которого к маршруту не уменьшает расстояния, так как мы предположили отсутствие контуров отрицательного веса. Работу алгоритма можно завершить на шаге k, если D (k) = Пример. Продемонстрируем работу ал- • • • • • d d d E E d d d d d © c T 1 2 3 Рис. 3.25 горитма Форда—Беллмана на примере взвешенного графа с матрицей весов = 0 1 ∞ ∞ 3 ∞ 0 3 3 8 ∞ ∞ 0 1 −5 ∞ ∞ 2 0 ∞ ∞ ∞ ∞ 4 показанного на рис. 3.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. 3.6. СТЕПЕНИ ВЕРШИН 69 Отметим, что, зная расстояние от источника a до всех остальных вершин графа, можно найти и сами кратчайшие (a i , a маршруты. Действительно, пусть a i , b 1 , b 2 , . . ., b r , a j — кратчайший (a i , a j )- маршрут. Тогда по строке вершина b r = a находится из соотношения, вершина b r−1 = a k 2 — из соотношения i , a k 1 ) = ρ w (a i , a k 2 )+ +w и т. д. П р им ер. В примере 3.5.1 кратчайший (1, маршрут определяется следующим образом ρ w (1, 4) = 3 = −1 + 4 = ρ w (1, 5) + тогда 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, маршрут задается последовательностью вершин (1, 2, 3, 5, 4). § Степени вершин Степенью или валентностью вершины a неорграфа G называется число ребер, инцидентных вершине a, те. число ребер, концом которых является вершина a (при этом петли считаются дважды). Если G — орграф, то степени его вершин определяются как степени вершин в соответствующем неорграфе F (G). Аналогично вводится понятие степени вершины в мультиграфах. Степень вершины a будем обозначать через deg G a или просто deg a. Вершина степени 0 называется изолированной, вершина степени 1 — концевой или висячей. П р им ер. Вершины графа G, изобра- • • • • • d d d d g 2 3 5 Рис. 3.26 женного на рис. 3.26, имеют следующие валентности 1 = deg 2 = deg 3 = 1 те висячие вершины те изолированная вершина). Рассмотрим сумму степеней всех вершин графа. Поскольку каждое ребро входит в эту сумму дважды, справедливо Утверждение 3.6.1 (лемма о рукопожатиях. Сумма степеней всех вершин графа является четным числом и равна удвоенному числу ребер. Пусть G — бесконтурный орграф. Полустепенью исхода deg + a вершины a называется число дуг, исходящих из a. Полустепенью захода вершины a называется число дуг, которые заходят в вершину. Справедливо соотношение deg a = = deg + a + В примере 3.6.1 имеем deg + 4 = 2, deg − 4 = 2. Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Обходы графов Опишем одну из задач, положивших начало теории графов, — задачу о кенигсбергских мостах . На рис. 3.27 схематично изображена карта г. Кенигсберга в XVIII в. Город был расположен на берегах и двух островах реки Преголи. Острова между собой и с берегами были связаны семью мостами. Возник вопрос можно ли, выйдя из дома, |