Определение графа

§1. Определение графа Определение 1.1. Пара hV, Ei называется простым графом, если V – непустое конечное множество элементов, называемых вершинами, а E – множество неупорядоченных пар различных элементов из V , называемых рёбрами. Обозначения. Пусть G – граф, тогда V (G) – множество его вершин, а E (G) – множество его рёбер. Если ребро {u, v} принадлежит E (G), то говорят, что оно соединяет вершины u и v. При этом вершины u и v называют смежными. Также их называют инцидентными ребру {u, v} (а ребро – инцидентным этим вершинам). Два различных ребра графа называют смежными, если они инцидентны общей вершине. 1 Пример. (Простой граф G.) Граф на языке DOT: 1 2 a e g 3 4 5 b f 6 7 8 c d 9 10 11 V (G) = {a, b, c, d, e, f, g} E (G) = {{a, b} , {b, c} , {a, c} , {b, d} , {e, f }} 12 13 14 graph { a b c d e f g a−−b b−−c b−−d a−−c e−− f } 2 Степень вершины v – это количество рёбер, инцидентных вершине v. Степень обозначается как deg v. Вершина степени 0 называется изолированной вершиной. Вершина степени 1 называется концевой вершиной. Ребро, инцидентное концевой вершине, также называют концевым ребром. Утверждение 1.1. Сумма степеней вершин графа G равна удвоенному P числу его рёбер: deg u = 2 |E (G)|. u∈V (G) B Доказательство утверждения тривиально: поскольку любое ребро инцидентно двум вершинам, в сумме степеней всех вершин графа каждое ребро учитывается дважды. C 3 В программировании чаще всего применяются не простые графы, а так называемые мультиграфы. В мультиграфе две вершины могут соединяться несколькими рёбрами, и допускаются петли, то есть рёбра, соединяющие вершину с ней самой. Мультиграф можно определить через введение понятия мультимножества рёбер, разрешающего повторное вхождение одного и того же элемента. Возможен и другой путь. Принимая во внимание, что на практике соединение двух вершин несколькими рёбрами имеет смысл только в случае, если эти рёбра чем-то отличаются, мы будем помечать рёбра мультиграфа некоторыми атрибутами, и мультимножество нам не понадобится. 4 Определение 1.2. Тройка hV, A, Ei называется размеченным мультиграфом, если V – непустое конечное множество вершин, A – множество атрибутов, а E – отображение множества одно- и двухэлементных подмножеств множества V в A. Элементами множества E являются упорядоченные пары вида h{u, v} , ai и h{u} , ai. Их мы будем называть рёбрами мультиграфа. Очевидно, что пары h{u} , ai соответствуют петлям. Мы будем считать, что петля добавляет 2 к степени инцидентной ей вершины. 5 Пример. (Мультиграф G.) Мультиграф на языке DOT: 1 a c 3 3 4 2 b 2 5 2 1 6 7 1 3 8 9 d 10 11 12 graph { a b c d a−−d a−−b d−−b b−−d b−−b c−−c } [ [ [ [ [ [ label label label label label label = = = = = = "1"] "2"] "3"] "1"] "2"] "3"] V (G) = {a, b, c, d} A (G) = {1, 2, 3} E (G) = {h{a, b} , 2i , . . . , h{c} , 3i} 6 Так как мы не определяем, какими именно объектами являются вершины графа, то de facto можно считать, что в любом графе вершины помечены какой-то информацией. Более того, как мы уже выяснили, рёбра тоже могут быть помечены атрибутами. Понятие изоморфизма позволяет абстрагироваться от разметки и учитывать только структуру (форму) графа. Определение 1.3. Два графа G1 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число рёбер, соединяющих любые две вершины в G1 (необязательно различные), равно числу рёбер, соединяющих соответствующие вершины в G2. ∼G . Обозначение. G1 = 2 7 Пример. (Два изоморфных графа.) a d 4 g 1 1 2 b f 2 3 c h 1 2 e Взаимно однозначное соответствие: ha, ei , hb, f i , hc, gi , hd, hi. 8 Определение 1.4. Абстрактный граф – это множество изоморфных помеченных графов. Пример. (Схематическое изображение некоторых абстрактных графов, имеющих 4 вершины) 9 §2. Подграфы Определение 2.1. Граф G0 = V 0, E 0 называют подграфом графа G = hV, Ei, если V 0 ⊆ V и E 0 ⊆ E, причём ребро {u, v} может содержаться в E 0 только тогда, когда u ∈ V 0 и v ∈ V 0. В свою очередь, граф G по отношению к своему подграфу G0 является надграфом. Определение 2.2. Остовным называется подграф G0 = V 0, E 0 , включающий в себя все вершины надграфа G = hV, Ei: V = V 0. 10 Пример. (Подграф.) На языке DOT: 1 2 a 3 4 5 b d e 6 7 8 c f g 9 10 11 12 13 14 graph { a [ c o l o r=g r a y ] b [ c o l o r=g r a y ] c; d e [ c o l o r=g r a y ] f; g a−−b [ c o l o r=g r a y ] b−−c c−−a a−−e [ c o l o r=g r a y ] e−−g d−− f e−− f } 11 Пример. (Остовный подграф.) На языке DOT: 1 2 a 3 4 5 b d e 6 7 8 c f g 9 10 11 12 13 14 15 16 graph { a [ c o l o r=g r a y ] b [ c o l o r=g r a y ] c [ c o l o r=g r a y ] d [ c o l o r=g r a y ] e [ c o l o r=g r a y ] f [ c o l o r=g r a y ] g [ c o l o r=g r a y ] a−−b [ c o l o r=g r a y b−−c [ c o l o r=g r a y c−−a a−−e e−−g [ c o l o r=g r a y d−− f e−− f [ c o l o r=g r a y } 12 ] ] ] ] Определение 2.3. Вершинно-порождённым называется подграф G0 = V 0, E 0 , включающий в себя те и только те рёбра надграфа G = hV, Ei, концы которых принадлежат V 0. Определение 2.4. Рёберно-порождённым называется подграф G0 = V 0, E 0 , включающий в себя те и только те вершины надграфа G = hV, Ei, которые инцидентны рёбрам из E 0. 13 Пример. (Верш.-порожд. подграф.) На языке DOT: 1 2 a 3 4 5 b d e 6 7 8 c f g 9 10 11 12 13 14 15 graph { a [ c o l o r=g r a y ] b [ c o l o r=g r a y ] c; d e [ c o l o r=g r a y ] f [ c o l o r=g r a y ] g a−−b [ c o l o r=g r a y ] b−−c c−−a a−−e [ c o l o r=g r a y ] e−−g d−− f e−− f [ c o l o r=g r a y ] } 14 Пример. (Рёб.-порожд. подграф.) На языке DOT: 1 2 a 3 4 5 b d e 6 7 8 c f g 9 10 11 12 13 14 15 16 graph { a [ c o l o r=g r a y ] b [ c o l o r=g r a y ] c [ c o l o r=g r a y ] d e [ c o l o r=g r a y ] f [ c o l o r=g r a y ] g a−−b b−−c [ c o l o r=g r a y ] c−−a [ c o l o r=g r a y ] a−−e e−−g d−− f e−− f [ c o l o r=g r a y ] } 15 §3. Маршруты в графе Определение 3.1. Маршрутом в графе называется конечная последовательность рёбер, в которой любые два последовательных ребра различны и смежны. Длина маршрута – это количество принадлежащих ему рёбер. Маршрут нулевой длины называется тривиальным. Пример. 1. 2. 3. 4. a b c {a, b} , {b, c} , {a, c} , {a, b} – маршрут; {a, b} , {b, c} , {b, d} – маршрут; {a, b} , {b, c} , {b, c} – не маршрут; {a, b} , {b, c} , {a, d} – не маршрут. d 16 Определение 3.2. Маршрут называется цепью, если все принадлежащие ему рёбра различны. Говорят, что цепь {u, x1} , {x1, x2} , . . . , {xn−1, xn} , {xn, v} соединяет вершины u и v. Говорят, что цепь {u, v} единичной длины соединяет вершины u и v. Тривиальная цепь соединяет любую вершину с ней самой. Пример. 1. 2. 3. 4. 5. a b c {a, b} , {b, c} , {a, c} , {a, b} – не цепь; {a, b} , {b, c} , {b, d} – цепь, соединяющая a и d; {a, b} , {b, c} – цепь, соединяющая a и c; {a, b} , {b, d} , {a, d} – цепь, соединяющая a и a; {a, c} – цепь, соединяющая a и c. d 17 Определение 3.3. Цепь называется простой, если каждая вершина графа инцидентна не более, чем двум принадлежащим этой цепи ребрам. Пример. 1. 2. 3. 4. a b c {a, b} , {b, c} , {b, d} – не простая цепь; {a, b} , {b, c} – простая цепь; {a, b} , {b, d} , {a, d} – простая цепь. {a, c} , {b, c} , {a, b} , {a, d}– не простая цепь. d 18 Простую цепь, имеющую вид {v0, v1} , {v1, v2} , . . . , {vm−1, vm} принято записывать как v0 ↔ v1 ↔ v2 ↔ . . . ↔ vm. В этой записи хорошо видно, что цепь соединяет вершины v0 и vm. Определение 3.4. Циклом (простым циклом) называется цепь (простая цепь), соединяющая вершину с ней самой. Определения маршрута, (простой) цепи и (простого) цикла справедливы и для мультиграфов. Простую цепь в мультиграфе, имеющую вид h{v0, v1} , a1i , h{v1, v2} , a2i , . . . , h{vm−1, vm} , ami можно записывать как a1 a2 a3 am v0 ↔ v1 ↔ v2 ↔ ... ↔ vm. 19 Замечание. Из определения следует, что любая вершина графа либо вообще не инцидентна ни одному ребру простого цикла в этом графе, либо инцидентна сразу двум рёбрам. Утверждение 3.1. Из множества рёбер таких, что любая вершина графа либо вообще не инцидентна ни одному ребру из этого множества, либо инцидентна сразу двум рёбрам, можно составить один или несколько простых циклов. Утверждение 3.2. Если вершины u и v графа соединены двумя различными простыми цепями, то в графе существует один или несколько простых циклов, составленных из рёбер, принадлежащих симметрической разности этих цепей. 20 §4. Классификация графов Определение 4.1. Граф называется пустым, если он вообще не имеет рёбер. Определение 4.2. Простой граф, имеющий максимальное количество рёбер, называется полным. Пример. (Полный граф.) c d b a 21 Определение 4.3. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным. Пример. (Регулярный граф.) e d c f a b 22 Определение 4.4. Граф несвязен, если множество его вершин распадается на два (или более) непересекающихся подмножества, таких, что нет ни одного ребра, концы которого принадлежат разным подмножествам. В противном случае, граф называется связным. Другими словами, несвязный граф состоит из двух и более частей, не соединённых рёбрами. Эти части называются компонентами связности. 23 Определение 4.5. Дерево – это связный граф с минимальным количеством рёбер: |E (G)| = |V (G)| − 1. Пример. (Дерево.) a d b c e g f 24 Определение 4.6. Граф называется двудольным, если существует такое разбиение множества его вершин на два непересекающихся подмножества, что концы любого ребра принадлежат разным подмножествам. (В общем случае определение может быть расширено на k-дольные графы.) Пример. (Двудольный граф.) b a c e d 25 Утверждение 4.1. Граф является двудольным тогда и только тогда, когда он не содержит нетривиальных простых циклов нечётной длины. B Необходимость. Предположим, что некоторый двудольный граф содержит нетривиальный простой цикл длины m, где m – нечётно. Так как граф – двудольный, то множество вершин цикла разбивается на два непересекающихся подмножества – V1 и V2, и концы любого ребра цикла принадлежат разным подмножествам. Пусть |V1| = k. Каждой вершине из V1 инцидентно два ребра цикла. При этом не существует ребра, инцидентного сразу двум вершинам из V1, иначе эти две вершины не могли бы обе принадлежать V1. Поэтому все рёбра, инцидентные вершинам из V1, различны, и всего этих рёбер – 2k. Один конец любого ребра цикла принадлежит V1. Так как цикл – простой, то все рёбра в нём различны. Значит количество рёбер, инцидентных вершинам из V1, равно m. Тем самым m = 2k – чётное. 26 Достаточность. Пусть граф не содержит нетривиальных простых циклов нечётной длины. Будем последовательно рассматривать все компоненты связности этого графа и разделять вершины каждого компонента на два непересекающихся подмножества, помеченных знаками «+» и «−», таких, что концы любого ребра компоненты принадлежат разным подмножествам. Возьмём произвольную вершину v компоненты связности и пометим её знаком «+». Покажем, что любую вершину u той же компоненты мы можем пометить знаком «−», если простая цепь из v в u имеет нечётную длину, и знаком «+» – в противном случае. 27 Если длины всех простых цепей, соединяющих v и u, имеют одинаковую чётность, то, очевидно, никакой проблемы нет. Поэтому предположим, что существуют две соединяющие v и u простые цепи, одна из которых имеет чётную длину, а другая – нечётную. Эти две цепи образуют нетривиальный цикл v ↔ . . . ↔ u ↔ . . . ↔ v нечётной длины. Если этот цикл – непростой, значит какая-то вершина w входит в него дважды и разбивает цикл на два подцикла, один из которых имеет нечётную длину. Повторяя рассуждение для этого подцикла, мы в конце концов придём к тому, что в графе существует простой цикл нечётной длины, что невозможно. Теперь покажем, что вершины, имеющие один знак, не могут быть смежными. Для этого предположим, что две смежные вершины u1 и u2 имеют один знак. Тогда, опять же, в графе имеется нетривиальный цикл v ↔ . . . ↔ u1 ↔ u2 ↔ . . . ↔ v нечётной длины, что невозможно. C 28 §5. Матрицы графов Определение 5.1. Матрица смежности h iпростого графа G – это симметричная квадратная матрица A = ai,j порядка n = |V (G)|, в которой n o элемент ai,j равен 1, если в графе есть ребро vi, vj , и 0, если такого ребра нет. Из определения следует, что сумма элементов i-той строки матрицы смежности равна степени вершины vi, а сумма элементов j-того столбца равна степени вершины vj . Матрица смежности пустого графа состоит из одних нулей, а матрица смежности полного графа – из одних единиц. Определение 5.2. Матрица смежности h i мультиграфа G – это симметричная квадратная матрица A = ai,j порядка n = |V (G)|, в которой n o элемент ai,j равен множеству атрибутов рёбер vi, vj , если они есть в графе, и пустому множеству в противном случае. 29 Если граф несвязен и имеет q компонент, то путём перестановки строк и столбцов его матрица смежности может быть приведена к блочнодиагональному виду, где каждый диагональный блок Ai,i является матрицей смежности соответствующей компоненты.   A11 0 ··· 0 0 A22 · · · 0   ... ... ...  ...  · · · Aqq   A=  (В случае мультиграфа элементы нулевых блоков – пустые множества.) 30 В случае k-дольного графа его матрица смежности может быть приведена к блочному виду, когда по главной диагонали идут только нулевые блоки:  A12 ... Ak1 Ak2 A  A =  ..21  .  · · · A1k · · · A2k   ...  ...  ··· 0 (В случае мультиграфа элементы нулевых блоков – пустые множества.) 31 Определение 5.3. Матрица инцидентности простого графа G – это пряh i моугольная матрица B = bi,j размера n × m, где n = |V (G)|, m = |E (G)|, в которой элемент bi,j равен 1, если вершина vi инцидентна ребру ej , и 0 в противном случае. Из определения следует, что сумма элементов i-той строки матрицы инцидентности равна степени вершины vi, а столбцы содержат по две единицы. Строки матрицы B называют векторами инцидентности и обозначают как Bi. 32 §6. Представление графов в памяти компьютера Пусть дан граф G, причём |V (G)| = n, |E (G)| = m. Представление графа в виде матрицы смежности предполагает использование двух структур данных: 1. матрица A размера n × n, при этом элемент ai,j матрицы равен некоторому специальному значению nil, если вершины vi и vj не являются смежными, в противном случае ai,j содержит атрибут ребра, соединяющего вершины vi и vj ; 2. массив размера n атрибутов вершин. Замечание 6.1. Для неориентированного графа возможно хранить не всю матрицу A, а только её половину, так как матрица – симметричная. Замечание 6.2. Если G – мультиграф, то ai,j содержит список (или массив) атрибутов рёбер, соединяющих вершины vi и vj . 33 Свойства представления простого графа в виде матрицы смежности:   Размер в памяти O n2 Время определения смежности двух вершин O (1) Достаточно посмотреть в ai,j Время нахождения всех рёбер, инцидентных вершине Время добавления новой вершины Время удаления вершины Время добавления нового ребра Время удаления ребра O (n) Нужно пройти по строке или столбцу матрицы  O n2 O (1)  Придётся создавать новую матрицу и копировать в неё содержимое старой матрицы Достаточно изменить ai,j 34 Свойства представления мультиграфа в виде матрицы смежности:  Размер в памяти O n2 + m Время определения смежности двух вершин Время нахождения всех рёбер, инцидентных вершине Время добавления новой вершины Время удаления вершины Время добавления нового ребра Время удаления ребра O (1)  O (max {n, m})  O n2  O (m) – нужно перебрать все рёбра, соединяющие заданные две вершины Замечание 6.3. Если предполагается частое удаление рёбер из мультиграфа, атрибуты рёбер лучше хранить в виде списка, а не в виде массива. 35 Представление (мульти)графа в виде списка инцидентности означает, что множество вершин графа хранится в виде массива структур размера n. i-тый элемент массива соответствует вершине vi и содержит её атрибут, а также указатель наDnсписок рёбер. o инцидентных E Для каждого ребра vi, vj , a , инцидентного вершине vi, заводится отдельный элемент списка, содержащий номер вершины vj , атрибут ребра и указатель на следующий элемент списка. Пример. A x C y 0) A 1 x 1) B x 3) D 4 z 4) E 3 z 3 y y 2) C B D z E 36 Свойства представления (мульти)графа в виде списка инцидентности: Размер в памяти Время определения смежности двух вершин Время нахождения всех рёбер, инцидентных вершине O (n + m) O (m) Время добавления новой вершины O (n) O (1) Время удаления вершины O (n + m) Время добавления нового ребра Время удаления ребра O (1) O (m) Нужно перебрать список рёбер Список инцидентных рёбер непосредственно доступен из структуры, описывающей вершину Придётся создавать новый массив вершин Придётся создавать новый массив вершин и перебирать списки рёбер Нужно добавить один или два элемента списка Нужно перебрать один или два списка рёбер 37 Замечание 6.4. В списке инцидентных рёбер, растущем из структуры, описывающей вершину простого графа, все рёбра оканчиваются в разных вершинах. Поэтому этот список можно считать списком смежных вершин, и представление простого графа в виде списка инцидентности можно назвать представлением в виде списка смежности. Замечание 6.5. Если граф – связный, то необязательно хранить структуры, описывающие вершины, в массиве. Структуры могут быть расположены в памяти как угодно, при этом в списках инцидентных рёбер вместо номеров вершин нужно использовать указатели на вершины. Это позволяет свести время добавления новой вершины к O (1), а время удаления вершины – к O (m). Замечание 6.6. Представление графа в виде матрицы смежности оправдано в случае плотного графа. В случае разреженного графа лучше использовать список инцидентности. 38 §7. Остовные деревья Утверждение 7.1. Любые две вершины связного графа, не содержащего циклов, соединяются единственной простой цепью. B Доказательство утверждения тривиально: если бы некоторые вершины u и v соединялись двумя различными простыми цепями, то согласно утверждению 3.2 граф содержал бы циклы. C Напомним, что дерево – это связный граф с минимальным количеством рёбер: |E (G)| = |V (G)| − 1. Утверждение 7.2. Чтобы связный граф был деревом, необходимо и достаточно, чтобы он не содержал циклов. B Необходимость. Предположим, что в дереве T имеется цикл. Удалив из этого цикла одно ребро, мы не нарушим связность дерева, но при этом количество рёбер уменьшится. Значит, T – не дерево. 39 Достаточность. Доказывать будем индукцией по числу рёбер графа. Можно показать, что связные графы с количеством рёбер 0, 1 и 2, не содержащие циклов, являются деревьями. Пусть любой не содержащий циклов связный граф с количеством рёбер, меньше или равным m, является деревом. Рассмотрим не содержащий циклов связный граф G с m + 1 рёбер. Пусть произвольные вершины u и v графа соединены простой цепью, содержащей некоторое ребро e. Согласно утверждению 7.1, эта цепь – единственна. Поэтому, лишившись ребра e, граф станет несвязным, и разобьётся на два компонента с количеством рёбер m1 и m2, где m1 + m2 = m. Согласно гипотезе индукции, эти компоненты – деревья, поэтому количество вершин в них равно m1 + 1 и m2 + 1, соответственно. Значит в графе G ровно m1 + m2 + 2 = m + 2 вершин, что на единицу больше количества в нём рёбер. Поэтому G – дерево. C 40 Следствие из утверждения 7.2. Добавив к дереву T ребро e, мы получим связный граф G, в котором есть ровно один цикл, и этот цикл содержит ребро e. B Так как T – связный граф, то и G – связный граф. При этом G – не дерево, так как в нём на одно ребро больше, чем в дереве T . Поэтому, согласно утверждению 7.2, G содержит некоторый цикл. Предположим, что e не входит в этот цикл. Тогда получается, что цикл состоит из рёбер дерева T , что невозможно, потому что, согласно утверждению 7.2, дерево не содержит циклов. Предположим, что e = {u, v} входит сразу в два разных цикла. Значит вершины u и v в дереве T соединяются сразу двумя цепями, что противоречит утверждению 7.1. C 41 Утверждение 7.3. Любой не содержащий циклов граф G, имеющий n вершин и n − 1 рёбер, является деревом. B Предположим, что G – несвязный. Тогда он разбивается на k > 1 компонент, имеющих m1, m2, . . ., mk рёбер. Причём k P i=1 mi = n − 1. Так как G не содержит циклов, то, согласно утверждению 7.2, каждый компонент является деревом и имеет mi +1 вершин. Поэтому получается, что общее количество вершин графа G равно k P i=1 (mi + 1) = n − 1 + k > n. Поэтому G – связный, и, согласно утверждению 7.2, он является деревом. C 42 Напомним, что остовным называется подграф G0 = V 0, E 0 , включающий в себя все вершины надграфа G = hV, Ei и часть рёбер: V = V 0, E 0 ⊆ E. Определение 7.1. Остовное дерево графа G – это остовный подграф графа G, являющийся деревом. Следствие из утверждения 7.3. Любой не содержащий циклов остовный подграф графа G, имеющий n вершин и n − 1 рёбер, является остовным деревом. B Доказательство непосредственно следует из утверждения 7.3. C Тем самым, если нам удастся выбрать ровно n − 1 не образующих циклов рёбер графа, имеющего n вершин, мы построим для этого графа остовное дерево. В противном случае граф несвязен, и для него невозможно построить остовное дерево. 43 §8. Обход графа Обход – это основа, на которой строится большое количество алгоритмов, выполняющих анализ графов. В некотором смысле, обход графа является аналогом перебора элементов массива, списка или дерева, приспособленным для работы с графом. При обходе вершины графа рассматриваются одна за другой в соответствии с принятым порядком обхода. При этом, как правило, ни одна вершина не обрабатывается дважды. 44 Пример. A I B D C G E F J H Пусть вершины графа рассматриваются в следующем порядке: A, B, C, E, F , G, D, H, I, J. Это – один из возможных вариантов обхода графа в глубину. Ещё один вариант обхода в глубину может выглядеть как E, C, A, B, D, G, F , H, J, I Если мы будем обрабатывать вершины в порядке A, B, C, D, E, F , G, H, I, J, то получится обход графа в ширину. 45 Рассмотрим схему работы алгоритма обхода графа в глубину (Depth-First Search – DFS) от вершины v. 1. Изначально все вершины графа белые. 2. Начиная с вершины v, мы строим в графе маршрут, последовательно добавляя к нему рёбра, инцидентные хотя бы одной белой вершине. При этом после добавления каждого ребра мы помечаем инцидентные этому ребру вершины серым цветом. Построение маршрута заканчивается в тот момент, когда мы попадаем в тупик, т.е. в вершину, у которой нет белых смежных вершин. 3. Возвращаемся по построенному маршруту до первой вершины u, у которой есть хотя бы одна белая смежная вершина. В процессе возвращения помечаем все вершины, у которых нет белых смежных вершин, чёрным цветом. Переходим к пункту 2 для v = u. 46 Мы будем считать, что структура, представляющая вершину в памяти, имеет поле mark, показывающее, каким цветом помечена данная вершина. Если граф – несвязный, то запуск обхода от произвольной вершины v позволит посетить все вершины из компоненты связности, которой принадлежит вершина v. Если мы хотим обойти все вершины несвязного графа, нам надо последовательно запускать обход от каждой непосещённой (т.е. белой) вершины. Алгоритм обхода графа в глубину имеет сложность O (|V | + |E|). 47 Алгоритм обхода графа в глубину: 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 DFS ( i n G ) f o r each v ∈ V (G) : v.mark ← w h i t e f o r each v ∈ V (G) : i f v.mark = w h i t e : V i s i t V e r t e x (G , v) Visi tVertex ( in G , in v) v.mark ← g r a y Действия при заходе в вершину v f o r each h{v, u} , ai ∈ E(G) : i f u.mark = w h i t e : Действия при проходе по ребру h{v, u} , ai V i s i t V e r t e x (G , u) v.mark ← b l a c k Действия перед выходом из вершины v 48 Нерекурсивный алгоритм обхода графа в глубину: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DFS ( i n G ) f o r each v ∈ V (G) : v.mark ← w h i t e I n i t S t a c k ( out s ) f o r each w ∈ V (G) : i f w.mark = w h i t e : Push ( s , w ) w h i l e not S t a c k E m p t y ( s ) : v ←Pop ( s ) i f v.mark = w h i t e : v.mark ← g r a y Действия при заходе в вершину v Push ( s , v ) f o r each h{v, u} , ai ∈ E(G) : i f u.mark = w h i t e : Push ( s , u ) e l s e i f v.mark = g r a y : v.mark ← b l a c k Действия перед выходом из вершины v 49 Алгоритм обхода графа в ширину (Breadth-First Search – BFS) от вершины v сначала посещает все вершины, смежные с вершиной v, затем все вершины, смежные со смежными вершинами, и т.д. Аналогично обходу в глубину, все посещаемые вершины помечаются, но не цветом, а булевским значением true. Соответственно, изначально все вершины помечены значением false. В случае несвязного графа обход запускается от каждой непосещённой вершины. Рекурсивный алгоритм обхода в ширину нерационален, поэтому применяется итерационный алгоритм, аналогичный нерекурсивному алгоритму обхода в глубину, но использующий не стек, а очередь. Алгоритм обхода графа в ширину работает за время O (|V | + |E|). 50 Алгоритм обхода графа в ширину: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BFS ( i n G ) f o r each v ∈ V (G) : v.mark ← f a l s e I n i t Q u e u e ( out q ) f o r each w ∈ V (G) : i f not w.mark : w.mark ← t r u e Enqueue (q , w ) w h i l e not QueueEmpty ( q ) : v ←Dequeue (q ) Действия при заходе в вершину v f o r each h{v, u} , ai ∈ E(G) : i f not u.mark : u.mark ← t r u e Enqueue (q , u) 51 §9. Компоненты рёберной двусвязности Определение 9.1. Мост в простом графе – это ребро, после удаления которого увеличивается число компонент связности графа. Пример. (мосты помечены серым) a b e c f d g h 52 Утверждение 9.1. В связном простом графе нет мостов тогда и только тогда, когда между любыми двумя вершинами этого графа существуют хотя бы две не имеющие общих рёбер цепи. B Необходимость. Предположим, что в не имеющем мостов связном графе существуют две вершины u и v такие, что все соединяющие их цепи имеют хотя бы одно общее ребро. Тогда удаление этого ребра приведёт к разбиению графа на две компоненты. Достаточность. Пусть любые две вершины связного графа соединяются хотя бы двумя не имеющими общих рёбер цепями. Тогда удаление любого ребра графа приведёт к разрыву не более одной из этих цепей. C Определение 9.2. Компоненты связности, получающиеся в простом графе после удаления всех мостов, называются компонентами рёберной двусвязности. 53 Алгоритм построения компонент рёберной двусвязности простого графа включает два обхода графа в глубину. Приведём схему работы алгоритма. 1. В каждой компоненте связности графа произвольно выбирается главная вершина. Из неё стартует первый обход графа в глубину, в результате которого формируется ориентированное остовное дерево компоненты связности с корнем в главной вершине. Кроме того, все вершины компоненты помещаются в очередь queue в том порядке, в котором они были посещены. 2. Последовательно выбираем из очереди queue вершины графа и, если очередная вершина v ещё не участвовала во втором обходе, запускаем из неё второй обход графа в глубину. Этот обход имеет одну особенность: через ребро, принадлежащее остовному дереву, можно проходить только в направлении к его корню. Все вершины, пройденные в процессе второго обхода графа из вершины v, будут принадлежать одной компоненте рёберной двусвязности. 54 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 DFS1 ( i n G , i n / out queue ) f o r each v ∈ V (G) : v.mark ← w h i t e f o r each v ∈ V (G) : i f v.mark = w h i t e : v.parent ←NULL V i s i t V e r t e x 1 (G , v , i n / out queue ) V i s i t V e r t e x 1 ( i n G , i n v , i n / out queue ) v.mark ← g r a y E n q u e u e ( queue , v ) f o r each h{v, u} , ai ∈ E(G) : i f u.mark = w h i t e : u.parent ← v V i s i t V e r t e x 1 ( G , u , i n / out queue ) v.mark ← b l a c k 55 1 2 3 4 5 6 7 8 9 11 12 13 14 15 DFS2 ( i n G , i n queue ) f o r each v ∈ V (G) : v.comp ← −1 component ← 0 w h i l e not QueueEmpty ( queue ) : v ← D e q u e u e ( queue ) i f v.comp = −1 : V i s i t V e r t e x 2 ( G , v , component ) component ← component + 1 V i s i t V e r t e x 2 ( i n G , i n v , i n component ) v.comp ← component f o r each h{v, u} , ai ∈ E(G) : i f u.comp = −1 and u.parent 6= v : V i s i t V e r t e x 2 ( G , u , component ) 56 §10. Алгоритм Крускала В принципе, остовное дерево легко получить в процессе обхода графа в глубину или в ширину, но мы рассмотрим другой способ, который пригодится для алгоритма Крускала. Пусть имеется последовательность {e [i]} рёбер графа G, имеющего n вершин. Будем формировать множество рёбер E 0 остовного дерева следующим образом: до тех пор, пока размер E 0 меньше n − 1, будем просматривать последовательность {e [i]} и добавлять i-тое ребро в E 0, если оно не образует циклов с рёбрами, уже добавленными в E 0. Для конкретного графа можно построить не одно остовное дерево. Какие именно рёбра попадут в остовное дерево, зависит от того, в каком порядке они записаны в последовательности {e [i]}. 57 В общем случае в процессе формирования множества E 0 мы будем получать несвязные остовные подграфы графа G: G0, G1, G2, . . . Gn−2, и только финальный подграф Gn−1 точно будет связным, так как по следствию из утверждения 7.3 он будет являться остовным деревом. Обратите внимание на то, что G0 соответствует пустому множеству E 0, т.е. вообще не содержит рёбер. Чтобы в процессе работы алгоритма эффективно отбрасывать рёбра, образующие циклы с уже добавленными рёбрами, мы будем использовать лес непересекающихся множеств, в узлами которого будут являться вершины графа. 58 Алгоритм формирования множества рёбер E 0 остовного дерева по последовательности {e [i]} рёбер графа: 1 2 3 4 5 6 7 8 9 10 0) S p a n n i n g T r e e ( i n G , i n {e[i]}m−1 , out E E ←∅ i←0 w h i l e i < m and |E 0| < |V (G)| − 1 : l e t e[i] = {u, v} : i f F i n d ( u ) 6= F i n d ( v ) : E 0 ← E 0 ∪ e[i] Union (u , v) i←i+1 i f |E 0| 6= |V (G)| − 1 : p a n i c " Несвязный граф " Предполагается, что перед началом работы алгоритма каждая вершина графа является отдельным деревом в лесу непересекающихся множеств. Время работы алгоритма – O (mα (n)). 59 Рассмотрим связный мультиграф, размеченный вещественными или целыми числами. То есть каждому ребру в таком мультиграфе соответствует свой вес. Вес ребра e будем обозначать как w (e). Определение 10.1. Минимальное остовное дерево связного мультиграфа – это остовное дерево, сумма весов рёбер которого минимальна. Алгоритм Крускала построения минимального остовного дерева предполагает, что рёбра мультиграфа сортируются по возрастанию их весов, после чего вызывается рассмотренный алгоритм SpanningTree: 1 2 3 4 MST_Kruskal ( i n G , out T ) V (T ) ← V (G) e ← S o r t ( E(G) ) S p a n n i n g T r e e ( e , |V (G)| , out E(T ) ) Время работы алгоритма Крускала определяется временем сортировки рёбер, т.е. в общем случае оно равно O (m lg m), где m – число рёбер. 60 Утверждение 10.1. Остовные подграфы G0, G1, . . . , Gn−1 связанного мультиграфа G, получающиеся в процессе работы алгоритма Крускала, являются подграфами минимального остовного дерева мультиграфа G. B Будем доказывать это утверждение индукцией по номеру подграфа Gi (другими словами, по количеству рёбер в подграфе). Для пустого подграфа G0 утверждение выполняется тривиально. Пусть Gi является подграфом некоторого минимального остовного дерева. Докажем, что при добавлении к Gi очередного ребра e с минимальным среди оставшихся рёбер весом, не образующего циклов с рёбрами Gi, получается Gi+1, который тоже является подграфом некоторого минимального остовного дерева. 61 Предположим, что e не входит ни в одно минимальное остовное дерево T , подграфом которого является Gi. Добавим e в T . По следствию из утверждения 7.2 мы получим единственный цикл c, и этот цикл будет содержать ребро e. Заметим, что цикл c не входит в Gi, потому что при добавлении e к Gi мы циклов не получаем. Поэтому c обязательно содержит рёбра, не входящие в Gi. Вес каждого из этих рёбер по крайней мере не меньше, чем w (e), потому что w (e) – минимальный среди весов рёбер, не входящих в Gi. Удалив из цикла c одно ребро с весом, не меньшим, чем w (e), мы получим граф T 0. Этот граф имеет такое же число вершин и рёбер, что и дерево T , и при этом не содержит циклов, так как цикл c – единственный. Согласно утверждению 7.3, T 0 является деревом. При этом сумма весов рёбер дерева T 0 не превышает суммы весов рёбер дерева T . Значит либо T не является минимальным, либо T 0, содержащее e, тоже является минимальным. В любом случае приходим к противоречию. C 62 §11. Алгоритм Прима В отличие от алгоритма Крускала, алгоритм Прима строит минимальное остовное дерево мультиграфа G путём последовательного наращивания единственного древовидного фрагмента, то есть в процессе работы алгоритма мы будем получать последовательность деревьев T0, T1, . . . , Tn−1, в которой T0 – пустое дерево, содержащее одну произвольно выбранную вершину G, а Tn−1 – минимальное остовное дерево мультиграфа G. На каждом шаге алгоритм Прима добавляет к Ti ребро с минимальным весом из числа рёбер, соединяющих одну из вершин из Ti с вершиной графа, не принадлежащей Ti. 63 Алгоритм Прима использует для поиска ребра с минимальным весом очередь с приоритетами, в которой содержатся вершины мультиграфа, не принадлежащие Ti, но к которым ведут рёбра от вершин, принадлежащих Ti . Каждая вершина графа при этом представляется тройкой hindex, key, valuei, в которой: • index содержит номер вершины в пирамиде, через которую реализована очередь с приоритетами; • key равен весу ребра, соединяющего вершину с одной из вершин, принадлежащих Ti (если таких рёбер несколько, выбирается ребро с минимальным весом); • value хранит другой конец вышеупомянутого ребра. Поле index у вершин, не входящих в очередь с приоритетами, равно -2, если вершина уже принадлежит Ti, и -1 – в противном случае. 64 Алгоритм Прима: 1 MST_Prim ( i n G , out T ) 2 f o r each v ∈ V (G) : 3 v.index ←−1 4 V (T ) ← V (G) , E(T ) ← ∅ 5 I n i t P r i o r i t y Q u e u e ( out q , |V (G)| − 1 ) 6 l e t v ∈ V (G) : 7 loop : 8 v.index ←−2 9 f o r each h{v, u} , ai ∈ E(G) : 10 i f u.index = −1 : 11 u.key ← a , u.value ← v 12 I n s e r t (q , u) 13 e l s e i f u.index 6= −2 and a < u.key : 14 u.value ← v 15 D e c r e a s e K e y ( q , u.index , a ) 16 i f QueueEmpty ( q ) : b r e a k 17 v ←ExtractMin (q) 18 E(T ) ← E(T ) ∪ h{v, v.value}, v.keyi Время работы: O (m lg n + n lg n), где n = |V (G)|, m = |E (G)|. 65 Утверждение 11.1. Деревья T0, T1, . . . , Tn−1, получающиеся в процессе работы алгоритма Прима для мультиграфа G, являются поддеревьями минимального остовного дерева мультиграфа G. Докажите самостоятельно! 66 §12. Ориентированные графы Определение 12.1. Пара hV, Ei называется простым орграфом, если V – непустое конечное множество элементов, называемых вершинами, а E – множество упорядоченных пар различных элементов из V , называемых дугами. Орграф можно рассматривать как пару hV, Γi, где Γ ⊆ V 2 – отображение, заданное на множестве V . Тогда Γ (v ) – множество конечных вершин всех дуг, исходящих из вершины v, а Γ−1 (v ) – множество начальных вершин всех дуг, входящих в v. При описании орграфов используют те же понятия, термины и характеристики, что и для неориентированных графов. Однако орграфы имеют свою специфику, обусловленную наличием ориентации дуг. Например, для каждой вершины v орграфа наряду с её степенью deg v определены полустепень исхода deg+ v = |Γ (v )| и полустепень захода deg− v = Γ−1 (v ) . При этом deg v = deg+ v + deg− v и P u∈V (G) deg+ u = P deg− u = |E (G)|. u∈V (G) 67 Определение 12.2. Матрица h i смежности простого орграфа G – это квадратная матрица A = ai,j порядка n = |V (G)|, в которой элемент ai,j D E равен 1, если в орграфе есть дуга vi, vj , и 0, если такой дуги нет. Из определения следует, что сумма элементов i-той строки матрицы смежности равна полустепени исхода вершины vi, а сумма элементов j-того столбца равна полустепени захода вершины vj . Определение 12.3. Матрица инцидентности простого орграфа G – это h i прямоугольная матрица B = bi,j размера n × m, где n = |V (G)|, m = |E (G)|, в которой элемент bi,j : – равен 1, если вершина vi является начальной вершиной дуги ej ; – равен −1, если вершина vi является конечной вершиной дуги ej ; – равен 0, если вершина vi и дуга ej не инцидентны. Ориентированный мультиграф определяется аналогично неориентированному. 68 Определение 12.4. Ориентированным маршрутом в орграфе называется конечная последовательность дуг, в которой для любых двух последовательных дуг a и b справедливо, что a входит в вершину, из которой исходит b. При этом длина ориентированного маршрута – это количество принадлежащих ему дуг. Нетрудно заметить, что все дуги в ориентированном маршруте направлены от начальной вершины к конечной. Если разрешить «свободную» ориентацию дуг, то получится полумаршрут – аналог маршрута в неориентированном графе. Определение 12.5. Ориентированный маршрут называется ориентированной цепью, если все принадлежащие ему дуги различны, и ориентированной простой цепью, если в добавок любая вершина графа инцидентна не более, чем двум дугам маршрута. 69 Ориентированная простая цепь также называется путём. Кроме того, для определения слабо связного орграфа нам понадобится понятие полупуть – полумаршрут, в котором различны все дуги и вершины (кроме, возможно, начальной и конечной). Говорят, что вершина u достижима из вершины v, если существует путь v → . . . → u. Если при этом v достижима из u, то u и v – взаимно достижимы. Мы будем использовать обозначение u ∼ v, чтобы показать, что вершины u и v взаимно достижимы. Определение 12.6. Ориентированным циклом (ориентированной простым циклом) называется ориентированная цепь (ориентированная простая цепь), начальная и конечная вершины которой совпадают. 70 Определение 12.7. Орграф называется сильно связным, если любые две вершины в нём взаимно достижимы. Определение 12.8. Орграф называется односторонне связным, если в любой паре его вершин хотя бы одна достижима из другой. Определение 12.9. Орграф называется слабо связным, если в нём любые две вершины соединены полупутём. Кроме того, выделяют ациклические орграфы, не имеющие ни одного цикла. Алгоритмы обхода вершин и рёбер графа легко распространяются и на орграфы, поэтому мы не будем их отдельно рассматривать. 71 §13. Классификация дуг орграфа Рассмотрим обход вершин орграфа в глубину. При этом для каждой вершины будем записывать время захода T 1 и время выхода T 2: 1 g l o b a l time ← 1 3 C a l c u l a t e T i m e s ( i n G) f o r each v ∈ V (G) : v.T 1 ← v.T 2 ← 0 f o r each v ∈ V (G) : i f v.T 1 = 0 : V i s i t V e r t e x (G , v) 4 5 6 7 8 10 11 12 13 14 15 Visi tVertex ( in G , in v) v.T 1 ← time ; time ← time + 1 f o r each hv, ui ∈ E(G) : i f u.T 1 = 0 : V i s i t V e r t e x (G , u) v.T 2 ← time ; time ← time + 1 72 D (4,5) C (3,6) B (2,7) E (8,13) A (1,14) F (9,12) G (10,11) 73 Рассмотрим некоторую дугу e = hu, vi орграфа, вершины которого размечены временами захода и выхода. Пусть e – не петля. Возможны три варианта соотношений между временани захода и выхода для вершин u и v: 1. u.T 1 < v.T 1 < v.T 2 < u.T 2 – вершина v была посещена после захода в вершину u и до выхода из вершины u. Тогда если при обходе орграфа в глубину мы встретили дугу e в момент, когда вершина v была не помеченной, то дуга e – древесная (TREE). В противном случае дуга e – прямая (FWD). 2. v.T 1 < u.T 1 < u.T 2 < v.T 2 – вершина u была посещена после захода в вершину v и до выхода из вершины v. Тогда дуга e – обратная (BACK). 3. v.T 2 < u.T 1 – вершина u была посещена после выхода из вершины v. Тогда дуга e – поперечная (CROSS). Все петли будем классифицировать как обратные дуги. 74 Пример. (Справа из графа удалены недревесные дуги) I (17,20) CROSS TREE B (2,7) BACK D (4,5) TREE CROSS J (18,19) I (17,20) TREE A (1,16) TREE TREE C (3,6) FWD J (18,19) A (1,16) TREE TREE E (8,15) TREE B (2,7) TREE BACK TREE CROSS H BACK (10,11) TREE F (9,14) E (8,15) TREE FWD TREE G (12,13) F (9,14) TREE TREE H (10,11) G (12,13) C (3,6) TREE D (4,5) 75 Если оставить в орграфе только древесные дуги, получится так называемый лес обхода в глубину. Этот лес состоит из ориентированных деревьев. Подграф леса обхода в глубину называется поддеревом, если он хотя бы слабо связен. Каждое поддерево имеет корень, из которого достижимы все остальные вершины поддерева. По логике алгоритма обхода в глубину ясно, что время захода для корня любого поддерева меньше времени захода для всех остальных вершин поддерева, а время выхода – больше времени выхода для всех остальных вершин поддерева. 76 §14. Компоненты сильной связности Отношение взаимной достижимости является отношением эквивалентности: Рефлексивность. u ∼ u, так как всегда существует путь u 7→ u. Симметричность. Если u ∼ v, то существуют пути u 7→ v и v 7→ u. Из этого следует v ∼ u. Транзитивность. Пусть u ∼ v и v ∼ w. Тогда существуют пути u 7→ v и v 7→ w, откуда следует существование пути u 7→ w. Аналогично, существуют пути w 7→ v и v 7→ u, откуда следует существование пути w 7→ u. Поэтому u ∼ w. 77 Любое отношение эквивалентности разбивает множество, на котором оно определено, на классы эквивалентности. Класс эквивалентности обозначается как [x], где x – один из его элементов, и определяется следующим образом: [x] = {y | x ∼ y} Легко доказать, что классы эквивалентности не пересекаются. Определение 14.1. Подграфы, порождённые классами эквивалентности, на которые отношение взаимной достижимости разбивает множество вершин орграфа, называются компонентами сильной связности. Несложно доказать, что если вершины u и v принадлежат одной компоненте связности, то все вершины, принадлежащие любому пути u → 7 v (а также v 7→ u), также принадлежат этой компоненте. 78 Компонента сильной связности для вершины u вычисляется в два этапа. На первом этапе мы выполняем обход графа (не важно, в ширину или в глубину) от вершины u и формируем множество вершин A, достижимых из вершины u. На втором этапе мы меняем направление всех дуг графа на противоположное и опять запускаем обход графа от вершины u, формируя множество вершин B, из которых достижима вершина u. Компонента сильной связности [u] = A ∩ B. Этот простой алгоритм работает за время O (m), где m – количество дуг в графе. 79 В §13 мы выяснили, что в результате обхода орграфа в глубину получается лес, состоящий из ориентированных деревьев. Можно показать, что компонента сильной связности, если оставить в ней только древесные дуги, образует поддерево леса обхода в глубину. Мы будем называть корень такого поддерева корнем компоненты. Пусть в процессе обхода графа в глубину для каждого узла u вычисляется время захода в него u.T 1. Так как компонента связности образует поддерево леса обхода в глубину, то время захода для корня компоненты будет меньше времени захода для любого другого узла той же компоненты. 80 Алгоритм Тарьяна выполняет обход орграфа в глубину и вычисляет все компоненты сильной связности в том порядке, в котором завершается обход соответствующих им поддеревьев леса обхода в глубину. При этом компоненты нумеруются, и в поле comp каждой вершины орграфа записывается номер её компоненты. 1 2 4 5 6 7 8 9 10 g l o b a l time ← 1 g l o b a l count ← 1 Tarjan ( i n G) f o r each v ∈ V (G) : v.T 1 ← v.comp ← 0 I n i t S t a c k ( out s , |V (G)| ) f o r each v ∈ V (G) : i f v.T 1 = 0 : V i s i t V e r t e x _ T a r j a n (G , v , s) 81 Основная идея алгоритма Тарьяна заключается в том, что в процессе обхода для каждого узла u вычисляется значение u.low, равное минимальному времени захода для всех узлов, достижимых из u, но не принадлежащих ещё ни одной вычисленной компоненте. При завершении обхода каждого поддерева с корнем в некотором узле u алгоритм смотрит, не равны ли значения u.low и u.T 1. Если они оказываются равны, значит u – корень новой компоненты. 12 13 14 15 16 17 18 19 20 21 22 V i s i t V e r t e x _ T a r j a n ( i n G , i n v , i n / out s ) v.T 1 ← v.low ← time ; time ← time + 1 Push ( s , v ) f o r each hv, ui ∈ E(G) : i f u.T 1 = 0 : V i s i t V e r t e x _ T a r j a n (G , u , s) i f u.comp = 0 and v.low > u.low : v.low ← u.low i f v.T 1 = v.low : do : u ←Pop ( s ) ; u.comp ← count w h i l e u 6= v count ← count + 1 82 I (17,20) Low: 17 D (4,5) Low: 2 J (18,19) Low: 18 H (10,11) Low: 1 A (1,16) Low: 1 I (17,20) TREE B (2,7) Low: 2 E (8,15) Low: 1 J (18,19) A (1,16) TREE TREE E (8,15) TREE C (3,6) Low: 2 F (9,14) Low: 1 F (9,14) TREE TREE G (12,13) Low: 12 H (10,11) G (12,13) B (2,7) TREE C (3,6) TREE D (4,5) 83 §15. Доминаторы в управляющих графах Определение 15.1. Управляющий граф – это орграф G = hV, E, ri с выделенной начальной вершиной r, из которой достижима любая другая вершина этого орграфа. Начальную вершину в управляющем графе принято называть входом или корнем. Пример. r a b c d e f 84 Определение 15.2. Говорят, что в управляющем графе G = hV, E, ri вершина v доминирует над вершиной u, если все пути из r в u проходят через v. Вершина v при этом называется доминатором вершины u. Определение 15.3. Вершина v является непосредственным доминатором вершины u, если v доминирует над u, и любой другой доминатор вершины u доминирует над v. Обозначение: v = idom(u). Определение 15.4. Дерево доминаторов для управляющего графа G = hV, E, ri – это ориентированное дерево на множестве вершин V с корнем в r, в котором дуги соединяют вершины с их непосредственными доминаторами. 85 Пример. (Управляющий граф и его дерево доминаторов) r a c r f d a h c e d f b e g h g b 86 Простейший способ построения дерева доминаторов заключается в том, что сначала строится предпорядок вершин при обходе управляющего графа G = hV, E, ri в глубину от корня r, а затем для каждой вершины v из предпорядка выполняются следующие действия: 1. все вершины графа, кроме v, помечаются «белым» цветом, а вершина v помечается «чёрным» цветом; 2. выполняется обход графа в глубину от корня r (а можно и в ширину); 3. находятся вершины, оставшиеся «белыми»; вершина v становится непосредственным доминатором для этих вершин. Заметим, что в процессе работы описанного алгоритма непосредственный доминатор вершины графа может несколько раз поменяться. Сложность алгоритма – O (nm), где n и m – количество вершин и рёбер, соответственно. 87 Эффективный алгоритм построения дерева доминаторов был представлен Ленгауэром и Тарьяном в 1979 году. Прежде чем перейти к рассмотрению этого алгоритма, договоримся, что на управляющем графе G = hV, E, ri, для которого мы будем строить дерево доминаторов, был выполнен обход в глубину от его корня r, в результате которого мы получили: 1. дерево обхода в глубину T с корнем в r, которое задаётся полями parent в каждой вершине графа; 2. отношение строгого порядка ≺ на множестве вершин такое, что v ≺ w тогда и только тогда, когда при выполненном обходе в глубину время захода для вершины v меньше времени захода для вершины w. 88 Лемма 15.1. Если v и w – такие вершины орграфа G, что v ≺ w, то любой путь p из v в w должен содержать общего предка вершин v и w в дереве T . B Пусть Tu – самое маленькое поддерево дерева T , содержащее все вершины пути p, причём некоторая вершина u – корень этого поддерева. Отметим, что так как вершины v и w входят в Tu, то u – один из общих предков вершин v и w в дереве T . T r Tu u v p w 89 Если u = v, то лемма выполняется сразу. r T Tu u=v p w Отметим, что u 6= w, так как в этом случае было бы w ≺ v, что противоречит условию нашего утверждения. 90 Расположим непосредственных потомков вершины u в дереве Tu в порядке возрастания. В результате у нас получится последовательность вершин u1, u2, . . ., uk , являющихся корнями дочерних поддеревьев T1, T2, . . ., Tk вершины u. Так как дерево T было получено путём обхода графа G в глубину, то дуга может исходить из вершины дерева Ti и входить в вершину дерева Tj только в том случае, если j < i. (Это будет перекрёстная дуга.) Tu u u1 u2 T1 T2 ··· uk Tk 91 Пусть v принадлежит поддереву Tj , а w принадлежат поддереву Ti, и эти поддеревья различны. Так как v ≺ w, то uj ≺ ui. T r Tu u ··· uj ··· ui ··· w v p Tj Ti В силу направления поперечных дуг, соединяющих поддеревья вершины u, из вершины v невозможно добраться до вершины w, минуя вершину u. 92 Если Ti и Tj – одно и то же дочернее поддерево вершины u, то вершина u входит в p в силу минимальности дерева Tu. T r Tu u ··· ··· ui = uj v p w Ti = Tj C 93 Определение 15.5. Путь v → u1 → . . . → ui → . . . → uk → w называется полудоминаторным, если ∀i = 1, k : w ≺ ui. Заметим, что согласно определению любой путь единичной длины является полудоминаторным. Определение 15.6. Вершина v называется полудоминатором вершины w 6= r, если v – минимальная из вершин, соединённых с w полудоминаторным путём, оканчивающимся на w: v = sdom (w) = min {u | u → . . . → w – полудоминаторный путь}. ≺ Понятие полудоминатора важно для алгоритма Ленгауэра–Тарьяна, потому что алгоритм работает в два этапа: сначала для каждой вершины вычисляется её полудоминатор, а потом на основании полудоминатора определяется непосредственный доминатор. 94 Пример. (Полудоминаторные пути и полудоминаторы.) 5 1 2 4 3 К вершине 3 ведут два полудоминаторных пути – красный и синий. 1 = sdom (3), 0 = idom (3). (Дуги дерева обхода в глубину – жирные.) 95 Лемма 15.2. В дереве T существует путь из sdom (w) в w 6= r. B Пусть v – непосредственный предок вершины w в дереве T , то есть v ≺ w. Путь v → w – полудоминаторный, поэтому по определению полудоминатора sdom (w)  v. Отсюда следует, что sdom (w) ≺ w. T r u sdom(w) p v По определению полудоминатора, существует полудоминаторный путь p из sdom (w) в w. Согласно лемме 15.1 путь p содержит общего предка u вершин sdom (w) и w в дереве T . w Так как u – предок w, то u ≺ w. А так как путь p – полудоминаторный, то все его промежуточные вершины больше w, поэтому u – начальная вершина p, то есть u = sdom (w) – предок w в дереве T .C 96 Утверждение 15.1. Пусть w 6= r, тогда sdom (w) = min (A ∪ B ), где ≺ A = {v | hv, wi ∈ E (G) и v ≺ w} , B = {sdom (u) | w ≺ u и ∃ hv, wi ∈ E (G) : из u в v в дереве ведёт путь} . B Пусть x = min (A ∪ B ). Докажем сначала, что sdom (w)  x. ≺ Если x ∈ A, т.е. hx, wi ∈ E (G) и x ≺ w, то по определению полудоминатора sdom (w)  x. T r x w 97 Если x ∈ B, то x = sdom (u) для некоторой вершины u такой, что w ≺ u и существует дуга hv, wi такая, что из u в v в дереве T ведёт путь. r T x q u p v w По определению полудоминатора существует полудоминаторный путь q = x → . . . → u, все промежуточные вершины которого превышают u. Так как путь p = u → . . . → v – древесный, то все его вершины также превышают или равны u. В итоге, соединив пути q, p и дугу hv, wi, мы получим полудоминаторный путь x → . . . → w, откуда по определению полудоминатора следует, что sdom (w)  x. 98 Теперь нам осталось доказать, что x  sdom (w). По определению полудоминатора существует полудоминаторный путь s = sdom (w) → . . . → w. Если это путь единичной длины, то в графе существует дуга hsdom (w) , wi, причём, согласно лемме 15.2, sdom (w) ≺ w. По условию нашего утверждения A = {v | hv, wi ∈ E (G) и v ≺ w}. Нетрудно убедиться, что sdom (w) ∈ A. Учитывая, что x = min (A ∪ B ), приходим к выводу, что x  sdom (w). ≺ 99 Теперь рассмотрим случай, когда длина пути s больше 1: s = sdom (w) → v0 → . . . → vk → w. Пусть вершина vj будет первой промежуточной вершиной пути s такой, что существует древесный путь из vj в vk . Такая вершина всегда найдётся, так как в крайнем случае vj = vk . r T sdom(w) v0 vj vk w Предположим, что не все вершины пути s от v0 до vj−1 превышают vj . Пусть vi – минимальная среди них. Так как vi ≺ vj , то по лемме 15.1 должен существовать древесный путь vi → . . . → vj , что противоречит выбору vj . Тогда путь sdom (w) → . . . → vj – полудоминаторный,  и  по определению полудоминатора sdom vj  sdom (w). 100 Напомним, что B = {sdom (u) | w ≺ u и ∃ hv, wi ∈ E (G) : из u в v в дереве ведёт путь} .   Нетрудно убедиться, что sdom vj ∈ B: w ≺ vj , так как vj – промежуточная вершина полудоминаторного пути s; ∃ hvk , wi ∈ E (G) : из vj в vk в дереве ведёт путь.   Учитывая, что x = min (A ∪ B ), приходим к выводу, что x  sdom vj . Ну ≺   а принимая во внимание, что sdom vj  sdom (w), получаем x  sdom (w).C 101 На основании утверждения 15.1 можно построить алгоритм вычисления полудоминаторов. Итак, sdom (w) = min (A ∪ B ), где ≺ A = {v | hv, wi ∈ E (G) и v ≺ w} , B = {sdom (u) | w ≺ u и ∃ hv, wi ∈ E (G) : из u в v в дереве ведёт путь} . Обратим внимание на то, что в A входят только вершины, предшествующие w, а в B входят полудоминаторы вершин, которым предшествует w. Таким образом, для того чтобы вычислить полудоминатор для некоторой вершины w, достаточно знать полудоминаторы вершин, которым предшествует w, а полудоминаторы других вершин могут оставаться невычисленными. Это наблюдение диктует порядок рассмотрения вершин в алгоритме вычисления полудоминаторов, а именно: вершины должны рассматриваться в порядке убывания. 102 Пусть в каждой вершине имеется поле sdom для хранения указателя на полудоминатор этой вершины. Если полудоминатор для некоторой вершины w ещё не вычислен, то пусть w.sdom = w. Сначала рассмотрим простой, но неэффективный алгоритм вычисления полудоминаторов: 1 2 3 4 5 6 7 8 9 10 11 Semidominators_naive ( i n G , i n ≺) f o r each w ∈ V (G) : w.sdom ← w f o r each w ∈ V (G) в п о р я д к е убывания по ≺ : f o r each hv, wi ∈ E(G) : loop : i f v.sdom ≺ w.sdom : w.sdom ← v.sdom i f v.sdom = v : break v ← v.parent   2 Время работы алгоритма: O n , где n – количество вершин. 103 Наивный алгоритм вычисления полудоминаторов неэффективен, главным образом, из-за линейного поиска вершины с минимальным полудоминатором (цикл в строчках 6..11). Время поиска можно значительно сократить, применив эвристику сжатия пути (аналогично операции Find в лесе непересекающихся множеств). Добавим в граф вспомогательные размеченные дуги, «срезающие» пути в дереве T . Пусть наличие «срезающей» дуги hv, ui, помеченной вершиной x, означает, что в дереве T имеется путь p = u → . . . → x → . . . → v, на котором вершина x имеет минимальный полудоминатор. «Срезающие» дуги будут представлены полями ancestor (цель дуги) и label (метка дуги) в вершинах графа. 104 Рекурсивный алгоритм поиска вершины с минимальным полудоминатором, выполняющий сжатие пути: 1 2 3 5 6 7 8 9 10 11 12 F i n d M i n ( i n v , i n ≺ ) : min SearchAndCut (v , ≺) min ← v.label S e a r c h A n d C u t ( i n v , i n ≺ ) : root i f v.ancestor =NULL : root ← v else : root ← S e a r c h A n d C u t ( v.ancestor , ≺ ) i f v.ancestor.label.sdom ≺ v.label.sdom : v.label ← v.ancestor.label v.ancestor ← root 105 Нерекурсивная версия алгоритма: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 F i n d M i n ( i n v , i n ≺ ) : min i f v.ancestor =NULL : min ← v else : stack ← I n i t S t a c k ( |V (G)| ) u←v w h i l e u.ancestor.ancestor 6=NULL : Push ( stack , u ) u ← u.ancestor w h i l e not S t a c k E m p t y ( stack ) : v ←Pop ( stack ) i f v.ancestor.label.sdom ≺ v.label.sdom : v.label ← v.ancestor.label v.ancestor ← u.ancestor min ← v.label 106 Алгоритм вычисления полудоминаторов (время – O (n lg n)): 1 2 3 4 5 6 7 8 9 10 Semidominators ( i n G , i n ≺) f o r each w ∈ V (G) : w.sdom ← w.label ← w w.ancestor ←NULL f o r each w ∈ V (G) в п о р я д к е убывания по ≺ : f o r each hv, wi ∈ E(G) : u ←FindMin (v , ≺) i f u.sdom ≺ w.sdom : w.sdom ← u.sdom w.ancestor ← w.parent 107 Лемма 15.3. В дереве T существует путь из idom (w) в w 6= r. B Дерево T – подграф G. А согласно определению доминатора, любой путь вида r → . . . → w в графе G проходит через вершину idom (w). T r idom(w) w Соответственно, путь из корня дерева в w тоже проходит через idom (w). C 108 Лемма 15.4. В дереве T существует путь из idom (w) в sdom (w) для любой вершины w 6= r. B Согласно леммам 15.2 и 15.3, idom (w) и sdom (w) – предки вершины w, значит они расположены на пути из r в w в дереве T . T r idom(w) sdom(w) w Соединим древесный путь r → . . . → sdom (w) с полудоминаторным путём sdom (w) → . . . → w. Так как все промежуточные вершины полудоминарного пути больше w, то они не принадлежат древесному пути из sdom (w) в w. Поэтому если бы idom (w) принадлежал древесному пути из sdom (w) в w, то наш соединённый путь его бы обходил, что противоречит определению доминатора. C Следствие из леммы 15.4. Для любой вершины w 6= r справедливо: idom (w)  sdom (w). 109 Лемма 15.5. Пусть в дереве T существует путь из v в w. Тогда в дереве T существует один из двух путей: (a) из v в idom (w), либо (b) из idom (w) в idom (v ). r T B Пусть вершина x находится на пути в дереве из idom (v ) к v. idom(v) x v w Тогда в графе G существует путь из r к v, обходящий x. Соединив этот путь с древесным путём из v в w, мы получим путь из r к w, обходящий x. Значит idom (w) не может находиться в дереве между idom (v ) и v, то есть idom (w) либо предок idom (v ), либо наследник v. C 110 Утверждение 15.2. Пусть w 6= r, и среди вершин, расположенных в дереве T на пути из sdom (w) в w и не совпадающих с sdom (w), вершина u имеет минимальный полудоминатор. Тогда если sdom (u) = sdom (w), то idom (w) = sdom (w). B Пусть p – произвольный путь из r к w. Пусть x – последняя вершина на пути p такая, что x  sdom (w). Она всегда существует, так как в крайнем случае x = r. Вершина x разбивает путь p на две части: p1 и p2. r T p1 x sdom(w) По лемме 15.2 sdom (w) ≺ w, а значит x ≺ w. p2 u w По лемме 15.1 на пути p2 существует общий предок вершин x и w в дереве T . Так x – минимальная вершина пути p2, то этот общий предок – вершина x. 111 Предположим, что x 6= sdom (w). r p1 Т.к. x ≺ sdom (w) в силу сделанного предположения, то путь p2 – не полудоминаторный. T x sdom(w) y u p2 w Значит минимальная промежуточная вершина пути p2 – назовём её y – предшествует вершине w. По лемме 15.1 y и w имеют общего предка в дереве T , а т.к. y – минимальная вершина на участке y → . . . → w пути p2, то этот общий предок – вершина y, причём sdom (w) ≺ y в силу выбора вершины x. 112 p1 Отрезок x → . . . → y пути p2 – полудоминаторный путь в силу выбора вершины y. Значит sdom (y )  x. sdom(w) Получается, что sdom (y ) ≺ sdom (w), что невозможно, т.к. u – вершина с минимальным полудоминатором на древесном пути из sdom (w) в w, и по условию нашего утверждения sdom (u) = sdom (w). Тем самым, мы пришли к противоречию, и x = sdom (w). r T x y p2 w Так как мы выбирали путь p произвольно, то любой путь из r в w проходит через sdom (w). Значит sdom (w) доминирует над w, т.е. sdom (w)  idom (w). По следствию из леммы 15.4, idom (w)  sdom (w), откуда следует, что idom (w) = sdom (w). C 113 Утверждение 15.3. Пусть w 6= r, и среди вершин, расположенных в дереве T на пути из sdom (w) в w и не совпадающих с sdom (w), вершина u имеет минимальный полудоминатор. Тогда sdom (u)  sdom (w) и idom (w) = idom (u). B Пусть z – первая после sdom (w) вершина, расположенная в дереве T на пути из sdom (w) в w. r T Тогда по условию: sdom (u)  sdom (z ). sdom(w) А так как z непосредственно следует после sdom (w), то sdom (z )  sdom (w). z Объединяя два неравенства, получаем sdom (u)  sdom (w). u w Тем самым, мы доказали первую часть утверждения. 114 Согласно лемме 15.4, в дереве T существует путь idom (w) → . . . → sdom (w) и, следовательно, путь idom (w) → . . . → u. r T idom(u) Тогда по лемме 15.5 в дереве T существует один из двух путей: (a) из idom (w) в idom (u); (b) из idom (u) в idom (idom (w)). (b) idom(idom(w)) idom(w) u w Если существует путь (b), то из предположения, что idom (u) 6= idom (w), следует, что можно построить путь из idom (u) в u (и далее в w), обходящий idom (w). Значит наше предположение неверно, и в случае существования пути (b) вторую часть нашего утверждения можно считать доказанной: idom (w) = idom (u). 115 В случае существования в дереве пути (a) из idom (w) в idom (u) для доказательства того, что idom (w) = idom (u), достаточно показать, что idom (u) доминирует над w. r T idom(w) (a) p1 x idom(u) p2 Рассмотрим произвольный путь p из idom (w) в w. Пусть x – последняя вершина на пути p такая, что x  idom (u). Она всегда существует, так как в крайнем случае x = idom (w). Вершина x разбивает путь p на две части: p1 и p2. По лемме 15.3 idom (u) ≺ u, по условию нашего утверждения u  w. Тогда idom (u) ≺ w, откуда следует, что x ≺ w. u w По лемме 15.1 на пути p2 существует общий предок вершин x и w в дереве T . Так как x – минимальная вершина пути p2, то этот общий предок – вершина x. 116 Вершина x не может находиться в дереве T на пути из r в idom (w), т.к. в этом случае мы могли бы объединить древесный путь r → . . . → x с путём p2, получив тем самым путь из r в w, обходящий idom (w). r idom(w) T Поэтому x находится в дереве T на пути из idom (w) в idom (u). p1 x Предположим, что x 6= idom (u). Тогда x ≺ idom (u)  sdom (u). idom(u) Мы доказали, что sdom (u)  sdom (w), поэтому x ≺ sdom (w), и путь p2 – не полудоминаторный. y p2 u w Пусть y – минимальная промежуточная вершина пути p2. Тогда y ≺ w, и по лемме 15.1 y – предок w в дереве. Причём idom (u) ≺ y в силу выбора вершины x. 117 Отрезок x → . . . → y пути p2 – полудоминаторный путь в силу выбора вершины y. Значит sdom (y )  x. А так как x ≺ sdom (u), то sdom (y ) ≺ sdom (u). r idom(w) Т.к. среди вершин, расположенных в дереве T на пути из sdom (w) в w и не совпадающих с sdom (w), вершина u имеет минимальный полудоминатор, то y  sdom (w) ≺ u. T p1 x Значит y расположена в дереве T на пути idom (u) → . . . → u. idom(u) y p2 u w Если соединить путь r → . . . → idom (w) с путём p1, добавить отрезок x → . . . → y пути p2 и древесный путь из y в u, то получится путь из r в u, не проходящий через idom (u). Тем самым мы пришли к противоречию, и x = idom (u). Таким образом, idom (u) лежит на любом пути из r к w и, тем самым, доминирует над вершиной w. C 118 Пусть каждая вершина графа имеет поле dom, предназначенное для хранения указателя на непосредственный доминатор вершины. Модифицируем алгоритм вычисления полудоминаторов, добавив в него код, вычисляющий непосредственные доминаторы. Нам придётся добавить в каждую вершину поле bucket, представляющее подмножество вершин графа. Поясним смысл поля bucket. Пусть имеются некоторые вершины v и w, причём v = sdom (w). Тогда w ∈ v.bucket, если для вершины w ещё не посчитан непосредственный доминатор. 119 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Dominators ( i n G , i n ≺) f o r each w ∈ V (G) : w.sdom ← w.label ← w w.ancestor ←NULL w.bucket ← ∅ f o r each w ∈ V (G) \ {r(G)} в п о р я д к е убывания по ≺ : f o r each hv, wi ∈ E(G) : u ←FindMin (v , ≺) i f u.sdom ≺ w.sdom : w.sdom ← u.sdom w.ancestor ← w.parent w.sdom.bucket ← w.sdom.bucket ∪ {w} f o r each v ∈ w.parent.bucket : u ←FindMin (v , ≺) v.dom ← i f u.sdom = v.sdom : v.sdom e l s e : u w.parent.bucket ← ∅ f o r each w ∈ V (G)\{r(G)} в п о р я д к е в о з р а с т а н и я по ≺ : i f w.dom 6= w.sdom : w.dom ← w.dom.dom r(G).dom ←NULL 120 §16. Постановка задачи поиска кратчайших путей Пусть дан орграф, каждой дуге которого присвоен вес (целое или вещественное число). Вес пути в таком орграфе – это сумма весов дуг, входящих в путь. Если две вершины орграфа соединяются несколькими путями, то кратчайшим путём между этими вершинами считается путь с наименьшим весом. Если задана начальная вершина s, то поиск кратчайших путей в орграфе заключается в вычислении для каждой вершины v двух атрибутов: v.dist – вес кратчайшего пути из s в v (оценка кратчайшего пути для вершины v); v.parent – вершина, непосредственно предшествующая вершине v на кратчайшем пути из s в v (родитель вершины v). Условимся, что если не существует пути от начальной вершины к вершине v, то v.dist = ∞, v.parent = N U LL. 121 Будем считать, что перед началом поиска кратчайших путей из начальной вершины s атрибуты вершин установлены следующим образом: s.dist = 0, s.parent = N U LL, v.dist = ∞, v.parent = N U LL, если v 6= s. Базовой операцией для алгоритмов поиска кратчайших путей является операция релаксации дуги, уточняющая оценку кратчайшего пути для вершины v, в которую входит дуга с весом w, исходящая из вершины u: 1 2 3 4 5 R e l a x ( i n u , i n v , i n w ) : changed changed ← (u.dist + w < v.dist) i f changed : v.dist ← u.dist + w v.parent ← u В реализации операции релаксации подразумевается, что x + ∞ = ∞ и ∞ ≮ ∞. Операция возвращает true, если оценка кратчайшего пути для вершины v была уточнена, и false – в противном случае. Важным свойством операции релаксации является то, что она не может увеличить оценку кратчайшего пути для вершины v. 122 Пусть дан орграф G = hV, Ei, начальная вершина s ∈ V , множество вершин V 0 ⊂ V , для которых посчитаны веса кратчайших путей из s, и некоторая вершина v ∈ V \ V 0, причём v.dist = ∞. Утверждение 16.1. После релаксации всех дуг, ведущих из вершин V 0 в v, значение v.dist будет равно весу c кратчайшего пути из s в v в подграфе G?, порождённом вершинами из V 0 ∪ {v}. B Если ни одной дуги не ведёт из вершин V 0 в v, то v.dist останется равным ∞. Это правильно, так как в этом случае в орграфе G? вершина v не достижима из s, и c = ∞. То же самое будет, если все дуги, входящие в v, исходят из вершин, не достижимых из s. 123 Пусть в вершину v входят дуги, исходящие из вершин, достижимых в орграфе G? из s. Предположим, что после релаксации всех этих дуг v.dist > c. Так как релаксация не увеличивает v.dist, то это условие было верно для каждого вызова операции релаксации. На кратчайшем пути из s в v вершине v предшествует некоторая вершина u. Поэтому при выполнении релаксации дуги hu, v, wi выполнялось неравенство u.dist + w = c < v.dist, в результате чего v.dist должно было получить значение c. Значит наше предположение неверно. Теперь предположим, что после релаксации всех дуг, исходящих из вершин V 0 и входящих в v, v.dist < c. Это значит, что при релаксации некоторой дуги, ведущей из какой-то вершины u в v, значение u.dist+w оказалось меньше c, то есть вес пути s → . . . → u → v меньше кратчайшего, и наше второе предположение тоже неверно. Отсюда v.dist = c.C 124 §17. Алгоритм Дейкстры Основная идея алгоритма Дейкстры: на каждом шаге алгоритма выбирается вершина v с минимальной оценкой кратчайшего пути, эта вершина помечается как обработанная (мы к ней больше не вернёмся), и затем производится релаксация всех дуг, исходящих из v: 1 2 3 4 5 6 7 8 9 10 11 12 D i j k s t r a ( i n G , i n s) f o r each v ∈ V (G) : v.dist ← ∞ v.parent ←NULL s.dist ← 0 M ← V (G) w h i l e M 6= ∅ : v ←вершина и з M с минимальной оценкой кратчайшего пути M ← M \ {v} f o r each hv, u, wi ∈ E(G) : Relax (v , u , w) 125 Алгоритм Дейкстры работает в случае, когда веса дуг – неотрицательные. В случае линейного поиска вершины с минимальной   оценкой кратчайшего пути сложность алгоритма Дейкстры: O n2 + m , где n – количество вершин, m – количество дуг. Утверждение 17.1. Вес кратчайшего пути от вершины s до вершины v, которая выбирается на каждой итерации внешнего цикла алгоритма Дейкстры, равен оценке кратчайшего пути для вершины v. B Доказательство утверждения проводится индукцией по номеру итерации. На первой итерации, очевидно, выбирается вершина s с оценкой пути 0, которая равна весу кратчайшего пути из s в s. Пусть на i-той итерации выбрана вершина v. При этом веса кратчайших путей для (i − 1) вершин, удалённых из множества M на предыдущих итерациях, уже посчитаны. 126 Так как на предыдущих итерациях были релаксированы все дуги, исходящие из вершин, принадлежащих V (G) \M , то, согласно утверждению 16.1, v.dist равно весу кратчайшего пути из s в v в подграфе G?, образованном вершинами (V (G) \ M ) ∪ {v}. Предположим, что в графе G имеется путь из s в v, вес которого c < v.dist. Тогда этот путь выходит за пределы подграфа G?, то есть выглядит как s → . . . → x → y → . . . → v, где x ∈ V (G) \ M , а y ∈ M . Вес пути s → . . . → x → y не меньше, чем y.dist, так как, согласно утверждению 16.1, y.dist равно весу кратчайшего пути из s в y в подграфе G??, образованном вершинами (V (G) \ M ) ∪ {y}, а путь s → . . . → x → y не выходит за пределы G??. Тогда вес пути s → . . . → x → y → . . . → v тоже не меньше, чем y.dist, то есть y.dist ≤ c. Вершина v имеет минимальную оценку кратчайшего пути среди всех вершин из M , значит v.dist ≤ y.dist ≤ c.C 127 Пример. (алгоритм Дейкстры не работает для графов с отрицательными весами) z 3 x s 5 10 -8 y В результате работы алгоритма Дейкстры z.dist = 8, в то время как путь s → y → x → z имеет вес 5. 128 Алгоритм Дейкстры целесообразно реализовывать через очередь с приоритетами: 1 Dijkstra ( in G , i n s) 2 I n i t P r i o r i t y Q u e u e ( out q , V (G) ) 3 f o r each v ∈ V (G) : 4 if v = s: 5 v.dist ← 0 6 else : 7 v.dist ← ∞ 8 v.parent ←NULL 9 Q u e u e I n s e r t (q , v) 10 w h i l e not QueueEmpty ( q ) : 11 v ←ExtractMin (q) 12 v.index ← −1 13 f o r each hv, u, wi ∈ E(G) : 14 i f u.index 6= −1 and R e l a x ( v , u , w ) : 15 D e c r e a s e K e y ( q , u.index , u.dist ) В случае использования очереди с приоритетами, реализованной на базе двоичной пирамиды, сложность алгоритма Дейкстры: O ((n + m) · lg n), где n – количество вершин, m – количество дуг. 129 §18. Алгоритм Беллмана-Форда Алгоритм Беллмана-Форда может работать в случае, когда веса части дуг орграфа – отрицательные. В основе алгоритма лежит следующее соображение: если в орграфе есть кратчайший путь s → x → y → . . . → u → v, то выполняя релаксацию дуг hs, xi, hx, yi, . . ., hu, vi в той последовательности, в какой они входят в путь, мы получим правильно установленные атрибуты dist и parent для всех вершин кратчайшего пути. Кратчайший путь в графе не может содержать больше, чем |V | − 1 вершин, а операция релаксации не может увеличивать оценку dist, поэтому, чтобы обеспечить нахождение всех кратчайших путей, можно |V | − 1 раз запустить релаксацию всех дуг графа. 130 Алгоритм Беллмана-Форда: 1 2 3 4 5 6 7 8 9 10 BellmanFord ( i n G , i n s) f o r each v ∈ V (G) : v.dist ← ∞ v.parent ←NULL s.dist ← 0 i←1 w h i l e i < |V (G)| : f o r each hu, v, wi ∈ E(G) : Relax (u , v , w) i←i+1 Время выполнения алгоритма Беллмана-Форда: O (nm), где n – количество вершин, m – количество дуг. 131 Если граф содержит циклы с отрицательным весом, то, очевидно, вес некоторых путей в графе может становиться сколь угодно мал. Чтобы обнаружить наличие таких циклов, достаточно запустить операцию релаксации ещё один раз и посмотреть, изменились ли оценки кратчайшего пути в вершинах графа. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 B e l l m a n F o r d ( i n G , i n s ) : negative cycles f o r each v ∈ V (G) : v.dist ← ∞ v.parent ←NULL s.dist ← 0 i←1 w h i l e i < |V (G)| : f o r each hu, v, wi ∈ E(G) : Relax (u , v , w) i←i+1 f o r each hu, v, wi ∈ E(G) : i f Relax (u , v , w ) : return true return fa lse 132 §19. Топологическая сортировка ациклического орграфа Утверждение 19.1. Орграф не содержит циклов тогда и только тогда, когда в нём нет обратных дуг. BНеобходимость. Пусть дан ациклический ограф. Докажем, что при любом его обходе в глубину не будет ни одной обратной дуги. Предположим, что какой-то обход в глубину выявил обратную дугу hu, vi. Обратная дуга соединяет вершину u с её предком v в дереве обхода в глубину. Значит в дереве имеется путь v 7→ u. Обратная дуга hu, vi замыкает этот путь в цикл. Достаточность. Пусть ни один обход графа в глубину не выявляет ни одной обратной дуги. Предположим, что граф содержит цикл c, а вершина v, принадлежащая циклу c, имеет минимальное время захода среди всех вершин цикла. Очевидно, что все остальные вершины цикла являются потомками v в дереве обхода в глубину, включая вершину u, непосредственно предшествующую вершине v в цикле. Поэтому дуга hu, vi – обратная.C 133 Топологический порядок на множестве вершин ациклического орграфа top G = hV, Ei – это такое бинарное отношение ≺ , что top ∀u, v ∈ V : u ≺ v ⇐⇒ ∃путь u 7→ v. top Отношение ≺ является отношением частичного порядка, т.к. обладает следующими свойствами: top • рефлексивность: ∀u : u ≺ u; top top • антисимметричность: ∀u, v : u ≺ v ∧ v ≺ u ⇒ u = v; top top top • транзитивность: ∀u, v, w : u ≺ v ∧ v ≺ w ⇒ u ≺ w. 134 Напомним, что в процессе обхода в глубину каждой вершине x графа можно присвоить время захода x.T 1 и время выхода x.T 2. top Утверждение 19.2. Если u ≺ v, где u и v – вершины ациклического орграфа G, то для любого обхода в глубину v.T 2 < u.T 2. BПо определению топологического порядка, существует путь u 7→ v. Согласно утверждению 19.1, при любом обходе в глубину этот путь не содержит обратных дуг. Рассмотрим любую дугу hx, yi, принадлежащую пути u 7→ v. Если hx, yi – древесная или прямая, то x.T 1 < y.T 1 < y.T 2 < x.T 2. Если hx, yi – поперечная, то y.T 2 < x.T 1, и, следовательно, y.T 2 < x.T 2. Исходя из этих соотношений, индукцией по номеру дуги на пути u 7→ v можно показать, что v.T 2 < u.T 2. C 135 Топологическая сортировка ациклического орграфа – это формирование последовательности {ui}, составленной из всех вершин графа таким образом, что top ∀ui, uj : ui ≺ uj ⇒ i < j. Алгоритм топологической сортировки, предложенный Тарьяном, составлен на основе следующего соображения. Согласно утверждению 19.2: top ∀ui, uj : ui ≺ uj ⇒ uj .T 2 < ui.T 2. Поэтому для получения топологической сортировки достаточно выполнить обход орграфа в глубину и расположить его вершины в порядке убывания времени выхода (другими словами, достаточно построить обратный постпорядок): ∀ui, uj : i < j ⇔ uj .T 2 < ui.T 2. 136 §20. Транзитивное замыкание орграфа Пусть дана пара вершин u и v орграфа G и требуется выяснить, существует ли путь u 7→ v. Эта задача называется запросом достижимости. Самое простое решение запроса достижимости заключается в запуске обхода орграфа из вершины u. Если в процессе обхода будет достигнута вершина v, значит путь существует. В противном случае, путь не существует. Обход орграфа выполняется за время O (n + m), где n и m – количества вершин и дуг орграфа, соответственно. Поэтому в случае, когда нужно выполнить большое количество запросов достижимости, такой подход оказывается неэффективным. Существует ряд эффективных алгоритмов вычисления запросов достижимости. Все эти алгоритмы работают на ациклических орграфах. Если граф, на котором требуется выполнять запросы достижимости, содержит циклы, сначала строится его конденсация. 137 Конденсация орграфа G – это орграф, множество вершин которого состоит из компонент сильной связности орграфа G, а множество дуг содержит дугу hu, vi тогда и только тогда, когда в графе G имеется дуга, исходящая из вершины компоненты u и заходящая в вершину компоненты v. Утверждение 20.1. Конденсация орграфа не содержит циклов. BПредположим, что конденсация ографа G содержит цикл c. Возьмём две разные компоненты сильной связности, принадлежащие этому циклу, и выберем в каждой из них произвольную вершину. Обозначим эти вершины как u и v. Легко показать, что из существования цикла c следует существование в графе G двух путей: u 7→ v и v 7→ u, т.е. вершины u и v взаимно достижимы и должны принадлежать одной компоненте сильной связности графа G.C 138 Итак, для любого орграфа G можно построить его конденсацию C. Пусть вершины u и v принадлежат компонентам сильной связности cu и cv , соответственно. Очевидно, что путь u 7→ v существует в орграфе G тогда и только тогда, когда в его конденсации C существует путь cu 7→ cv . Это соображение позволяет нам в дальнейшем рассматривать вычисление запросов достижимости только для ациклических орграфов. 139 Вычислять запросы достижимости за константное время можно, построив так называемое транзитивное замыкание оргафа. Если на множестве вершин ациклического орграфа G = hV, Ei построеtop но отношение частичного ≺ , то его транзитивным замыканием * порядка + top будет орграф T C (G) = V, ≺ . Очевидно, что в орграфе G существует путь u → v тогда и только тогда, когда в орграфе T C (G) содержится дуга hu, vi.   2 Размер транзитивного замыкания в памяти равен O n . 140 Алгоритм построения транзитивного замыкания перебирает вершины ациклического оргафа в обратном топологическом порядке и для каждой вершины строит множество исходящих из неё дуг в транзитивном замыкании. При построении множества исходящих дуг используется тот факт, что дуги транзитивного замыкания для вершин, непосредственно достижимых из данной вершины, уже построены. 1 2 3 4 5 6 7 8 T r a n s i t i v e C l o s u r e ( in G ) : TC V (T C) ← V (G) E(T C) ← ∅ f o r each u ∈ V (G) в обр . т о п о л о г и ч е с к о м п о р я д к е : E(T C) ← E(T C) ∪ {hu, ui} f o r each hu, vi ∈ E(G) : f o r each hv, wi ∈ E(T C) : E(T C) ← E(T C) ∪ {hu, wi} Время работы алгоритма – O (nm), так как для каждой вершины перебирается не более m дуг. 141 §21. Интервальное кодирование транзитивного замыкания дерева Если орграф является деревом, то можно применить эффективную схему представления его транзитивного замыкания, требующую O (n) памяти. Пусть выполнен обход дерева в глубину от корня, и в каждой вершине дерева записано её время выхода T 2. Из любой вершины дерева u достижимы только вершины, принадлежащие растущему из неё поддереву. При этом у всех этих вершин время выхода T 2 меньше, чем u.T 2. Пусть у каждой вершины имеется поле index, равное минимальному времени выхода для вершин растущего из неё поддерева. Тогда u 7→ v ⇔ u.index ≤ v.T 2 ≤ u.T 2. 142 Алгоритм построения интервалов, кодирующих транзитивное замыкание ориентированного дерева: 1 2 3 4 5 6 7 8 9 T r e e C l o s u r e ( i n / out T ) time ← 0 f o r each u ∈ V (T ) в обр . т о п о л о г и ч е с к о м п о р я д к е : u.T 2 ← time i f u − л и с т о в а я вершина : u.index ← time else : u.index ← min {v.index | hu, vi ∈ E (T ) } time ← time + 1 Алгоритм выполнения запроса достижимости: 1 2 T r e e Q u e r y ( i n T , i n u , i n v ) : verdict verdict ← u.index ≤ v.T 2 ≤ u.T 2 143 Утверждение 21.1. Любые два интервала, кодирующие транзитивное замыкание ориентированного дерева, либо не пересекаются, либо один из них вложен в другой. BПредположим, что интервалы, вычисленные для двух вершин дерева u и v пересекаются, но при этом ни один из них не вложен в другой, т.е. v.index < u.index ≤ v.T 2 < u.T 2. Так как v.T 2 попадает в интервал, соответствующий вершине u, то u 7→ v. Обозначим как w вершину с временем выхода v.index. Тогда v 7→ w. Получается, что u 7→ w, но при этом w.T 2 не попадает в интервал, соответствующий вершине u. C 144 §22. Интервальное кодирование транзитивного замыкания ациклического орграфа Пусть дан ациклический орграф G. Построим для этого орграфа остовный лес. Это можно сделать простым обходом в глубину, а можно воспользоваться способом, который будет рассмотрен в дальнейшем. Пусть транзитивное замыкание для деревьев остовного леса закодировано интервалами в каждой вершине леса. Для построения этих интервалов можно воспользоваться алгоритмом TreeClosure, т.к. он, очевидно, годится не только для ориентированного дерева, но и для ориентированного леса. Ясно, что интервалы в вершинах остовного леса не годятся для вычисления запросов достижимости в орграфе G, так как они построены без учёта дуг орграфа G, не попавших в остовный лес. 145 Запишем алгоритм, который строит в каждой вершине u орграфа G множество интервалов u.ranges, состоящее из интервалов вершин, достижимых из u (включая и интервал, которым помечена сама вершина u): u.ranges = {hv.index, v.T 2i | u 7→ v} , и выбрасывает из этого множества все интервалы, которые вкладываются в другие интервалы множества: 1 2 3 4 5 D a g C l o s u r e ( i n / out G ) f o r each u ∈ V (G) в обр . т о п о л о г и ч е с к о м п о р я д к е : u.ranges ← {hu.index, u.T 2i} f o r each hu, vi ∈ E(G) : u.ranges ← M e r g e R a n g e s ( u.ranges , v.ranges ) Вспомогательный алгоритм MergeRanges объединяет два множества интервалов, не включая в результат интервалы, вкладывающиеся в другие интервалы. 146 Согласно утверждению 21.1, интервалы в остовном лесу либо не пересекаются, либо вкладываются. Так как множество интервалов, соответствующее вершине орграфа, избавлено от интервалов, вкладывающихся в другие интервалы множества, то получается, что все интервалы не пересекаются. Эффективным представлением множества интервалов является последовательность, в которой интервалы отсортированы по возрастанию, т.е. для любых двух подряд идущих интервалов a = hal , ar i и b = hbl , br i справедливо, что ar < bl . Такое представление позволяет реализовать алгоритм MergeRanges по схеме, похожей на алгоритм слияния двух последовательностей в алгоритме сортировки слиянием. 147 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 M e r g e R a n g e s ( i n a , i n b ) : res res ← п у с т а я п о с л е д о в а т е л ь н о с т ь i ← 0; j←0 w h i l e i