Главная Промышленная автоматика.

вершины расположен непосредственно справа от первой правой скобки, заключающей эту вершину.

Другое представление дерева можно получить, составив список прямых предков его вершин 1, 2, п именно в этом порядке. Чтобы опознать корень, будем считать, что его предок- это 0.

Пример 0.26. Дерево, показанное на рис. 0.14, можно представить в виде 0122441777. Здесь О на первом месте указывает


5) (6

Рис. 0.14. Дерево.

на то, что прямым предком вершины 1 является „вершина О (т. е. что вершина 1-корень). Число 1 на седьмом месте говорит о том, что прямым предком вершины 7 является вершина 1. □

0.5.8. Пути в графе

В этом разделе мы опишем эффективный с вычислительной точки зрения алгоритм построения транзитивного замыкаиия отношения R, определенного иа множестве А. Если это отношение представлять себе в виде (неупорядоченного) графа (Л, R]. то его транзитивное замыкание будет множеством пар вершин (а, &), для которых существует путь из а в Ь.

Другая возможная интерпретация состоит в том, чтобы смотреть на отношение (или граф) как на квадратную булеву матрицу (т. е. матрицу нз нулей и единиц), называемую матрицей смежностей, в которой на пересечении i-я строки и /-го столбца стоит 1 тогда и только тогда, когда элемент, соответствующий 1-й строке, находится в отношении R с элементом, соответствующим /-му столбцу. Иа рис. 0.1S показана матрица смежностей М, соответствующая графу на рис. 0.6. Если М -матрица смеж-

ностей отношения R, то M+~ [гц,е М"- матрица М, у

иоженная) на себя п раз) - матрица смежностей транзитивного замыкаиия этого отношения. Таким образом, алгоритм нахождения транзитивного замыкания можно применять и для вычисления М.

Для матрицы М, изображенной на рис. 0.15, матрица Л1+ состоит из одних единиц.

Рис. 0.15. Матрица смежпосте: графа, изображенного на рис. 0.6.

Фактически мы приведем здесь несколько более общий алгоритм. Будем предполагать, что задан (неупорядоченный ориентированный) граф, в котором каждой дуге, ведущей из вершины i в вершину /, приписан вес (или стоимость) с/у. (Если из / в / не ведет ни одна дуга, вес cj считается бесконечным.) Алгоритм будет вычислять для каждой пары вершин минимальный вес пути, ведущего из первой вершины пары во вторую. В том случае, когда мы хотим вычислить только транзитивное замыкание отношения R на множестве {а-, и„, ...,а„\, надо положить cj--0, если aiRuj, и суоо в противном случае.

Алгоритм 0.2. Минимальный вес (стоимость) путей в графе.

Вход. Граф с п вершинами, занумерованными 1, 2, п, и с весами с,уО для всех 1/, /".

Выход. Матрица M - [mj], в которой mj-минимальный нз весов путей, ведущих из вершины i в вершину / {li,jn).

Метод.

(1) Положить mjCij для всех / и / (li, i).

(2) Положить /е = 1.

1) При этом используется обычная формула для умножения матриц, но с булевыми операциями и + в качестве умножения и сложения.



(3) Для всех / и /, если т,у > m,ft-f ту, положить ш,ут,,(--ту.

(4) Если k < п, увеличить k на единицу и перейти к шагу (3). Если k = n, остановиться. □

Ядром алгоритма 0.2 является шаг (3), на котором проверяется, можно ли уменьшить стоимость (вес) перехода из вершины i в вершину /, перейдя сначала из вершины i в вершину к, а затем из вершины к в вершину /. Так как шаг (3) выполняется по одному разу для всевозможных значений i, j, k, то временная сложность алгоритма 0.2 равна

Сразу не ясно, что алгоритм 0.5 находит минимальный вес путей, ведущих из i в j. Таким образом, надо доказать, что алгоритм 0.2 делает то, что требуется.

Теорема 0.5. Когда алгоритм 0.2 останавливается, т - наименьшая из величин, представимых в виде суммыс,,-}- . .. H-Pj где Ij i и v - j. (Эта сумма - вес пути у, гк, веду-

шего из вершины i в вершину j.)

Доказательство, Чтобы доказать эту теорему, докал<ем индукцией по значению / переменной k в шаге (3) нашего алгоритма следующее утверждение:

(0.5.1) После того как шаг (3) выполнен для /г - /, значением mj- служит наименьшая из величин, представимых в виде суммы v,v,\- -+<v ib> где v-i, v-j и ни одно из не превосходит /.

Назовем эту наименьшую величину корректным значением ту для k=-l. Эта величина - вес самого легкого (или стоимость самого дешевого) пути, ведущего из вершины i в вершину /, среди путей, не проходящих через вершины, номера которых больше /.

Базис. Рассмотрим начальное условие, которое имеет вид / - 0. (Если угодно, можно рассматривать шаг (1) как шаг (3) для А = 0.) Если / - О, то т=2, и значение т-с является корректным начальным значением.

Шаг индукции. Предположим, что утверждение (0.5.1) истин-1Ю для / < /д. Рассмотрим значение после того, как шаг (3) выполнен для k - l.

Допустим сначала, что значением т для fe -является такая наименьшая сумма с.-\- . . . -V<v„-v что ни одно Vp (2 - 1) не равно /д. По предположению индукции

vv-\-" • ~v„-xv - корректное значение т,у для и

потому cp-f ...-j-c, y - корректное значение mj также и для - /д.

Теперь предположим, что значением m-j для k - lq является такая наименьшая сумма s,.с,-!- ... --cm-ivm р = К

для некоторого р, 2рт-1. Эго значит, что s.y-это вес пути f, v. Можно считать, что иа этом пути нет вер-

шины для которой дфр и Vfj = l. В противном случае путь у, содержал бы цикл и можно было бы удалить по

крайней мере один член суммы Cvv • • vm Im увеличив значения s,y. Таким образом, для s,y всегда можно найти сумму, в которой Vp ~ Iq только для одного значения р, 2 р т-1.

Пусть 2 < р < яг-I. (Случаи р = 2 п р = т-I оставляем читателю.) Рассмотрим суммы S;. = c+ ...+с, и s„y = = с -f- - -. огорые являются весами путей, веду-

щих из вершины i в вершину у, и из вершины в вершину / соответственно. По предположению индукции можно считать, что s,..y - корректное значение т для e - 1, а sj - корректное значение m.j д,ля kl-l. Таким образом, когда шаг (3) выполняется для/е -Z, переменной т присваивается корректное значение m-m.j.

Итак, мы показали, что утверждение (0.5.1) истинно для всех /. Когда / -утверждение (0.5.1) говорит о том, что в конце работы алгоритма 0.2 значением т,у является наименьшая из возможных величин. □

Распространенный частный случай нахождения минимума весов путей в графе-это случай, когда мы хотим найти множество вершин, достижимых из дайной вершины. Эквивалентная формулировка: дано отношение R на множестве А и элемент аА; надо найти множество таких ЬЛ, что aRb, где R - транзитивное замыкание отношения R. Для этой цели можно применить следующий алгоритм, имеющий квадратичную временную сложность.

Алгоритм 0.3. Нахождение множества вершин, достижимых из данной вершины а (ориентированного) графа.

Вход. Граф (Л, R), в котором Л - конечное множество, паА.

Выход. Множество таких вершин ЬА, что aRb.

Метод, Будет образован список L, меняющийся в ходе работы алгоритма. Кроме того, будут отмечаться некоторые элементы множества А. Вначале все элементы из Л не отмечены.

(1) Положить La.

(2) Если список L пуст, остановиться. В противном случае вычеркнуть из L первый элемент b и отметить его в А.

3 А, Ахо, Дж. Ульман, т. 1 65



гл. 0. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВПДЕНИЯ

(3) Поместить в конец списка L все неотмеченные элементы сА, для которых bRc, и перейти к шагу (2). □

Доказательство того, что алгоритм 0.3 работает правильно, оставляем в качестве упражнения.

УПРАЖНЕНИЯ

0.5.1. Каково максимальное число дуг, которые может иметь ациклический граф с п вершинами?

0.5.2. Докажите теорему 0.3.

0.5.3. Постройте прямой и обратный порядки вершин дерева, изображенного на рис. 0.14. Напишите левое и правое скобочное представления этого дерева.

*0,5.4. (а) Придумайте алгоритм, отображающий левое скобочное представление дерева в правое.

(б) Придумайте алгоритм, отображающий правое скобочное представление дерева в левое.

0.5.5. Во сколько разных линейных порядков можно вложить частичный порядок, заданный ациклическим графом на рис. 0.8? 0.5.6. Докажите теорему 0.4.

0.5.7. Укажите верхние границы времени и емкости, необходимых для реализации алгоритма 0.1, считая, что требуется одна ячейка памяти для хранения имени вершины или целого числа и один элементарный шаг для каждой операции из некоторого разумного множества примитивных операций, включающего арифметические операции и операции проверки или изменения ячейки массива, индексом которой является известное целое число.

0.5.8. Пусть А = {а, b,c,d) н R = {(а, Ь), (Ь, с), (а, с), (6, d)}. Найдите линейный порядок R, для которого RR. Сколько существует таких линейных порядков?

Определение. Неориентированный граф G - это тройка (A,EJ), где А-множество вершин, Е - множество имен ребер iif-отображение множества Е в множество неупорядоченных пар вершин. Запись f{e)\a,b\ означает, что ребро е соединяет вершины а я Ь. Путем в неориентированном графе называется такая последовательность вершин а, а, а., ..., a,, что для каждого i, lirt, найдется ребро, соединяющее a. с а,-. Неориентированный граф называется связным, если для каждых двух его вершин существует соединяющий их путь.

Определение. Неориентированное дерево можно определить рекурсивно следующим образом. Неориентированное дерево-это

УПРЛЖНЕ НИЯ

множество, состоящее из одной или более вершин, в котором выделена одна вершина г, называемая корнем. Остальные вершины разбиваются на нуль или более множеств Т, 7, каждое из которых образует дерево. Деревья Г, называются поддеревьями корня г и корень каждого такого поддерева соединен неориентированным ребром с г.

Остовом связного неориентированного графа G называется дерево с ребрами из графа G, содержащее все его вершины.

0.5.9. Напишите алгоритм построения остова связного неориентированного графа.

0.5.10. Пусть (А, R) - (неупорядоченный) граф, в котором Л-{1, 2, 3, 4} и ;?-{(!, 2), (2, 3), (4, 1), (4, 3)}. Найдите транзитивное замыкание R отношения R. По матрице смежностей М отношения R вычислите УИ + и покажите, что М - матрица смежностей графа (А, /?"*").

0.5.II. Покажите, что алгоритм 0.2 требует порядка элементарных шагов, подобных тем, которые упоминались в упр. 0.5.7.

0.5.12. Докажите, что алгоритм 0.3 отмечает вершину b тогда и только тогда, когда aRb.

0.5.13. Покажите, что алгоритму 0.3 требуется время, пропорциональное большему из чисел #Л и :R.

0.5.14. Какие из следующих трех неупорядоченных ориентированных графов равны?

6\-({а, Ь, с], {(а, Ь), (Ь, с},{с, а)}) G,{{a, b,c], {{Ь,а),{а, с), {Ь,с)\) Gg - ({а, Ь, с}, \{с, Ь), (с, а), ф, а)})

0.5.15. Даны три упорядоченных ориентированных графа, у которых помечены только вершины. Какие из них равны?

G,({a, b, с}, {{{а, Ь), (а, с)), {{Ь, а), (Ь, с)),{{с, Ь))\)

с разметкой 1{а) = Х, l{b) = Z и 1-{с)=У.

G = {{a, b, с\, {{{а, с)), {(Ь,с), ф, а)), {{с,Ь), [с, а))})

с разметкой 4 (а) У, I., ф)Х и 1 (с) Z.

G, = {{a,b,c\, {({а, с), (а,Ь)), {ф,с)), {{с,а), {с, Ь))\) с разметкой /д (а) = У, Lj ф)Х и 1 (с) = Z.

0.5.16. Закончите доказательство теоремы 0.5. 0.5.17. Дайте алгоритм, определяющий, связен ли неориентированный граф. *0.5.18. Дайте алгоритм, определяющий, равны ли два графа.





0 1 2 3 4 5 6 7 8 [9] 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0015