Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции), страница 13

(1) Если корнем дерева Т служит нершина а с поддеревьями Т„Т„..., Т„расположенными и этом порядке (их корнн— прямые потомки вершины а), то Пер(Т) — --а(!Тер(Т,), !гер(Т,), ..., !гер(ТА)). (2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то !Рер(Т) =а. Если в левом скобочкам представлении стереть все скобки, получится прямой порядок вершин дерева. ° Аналогично можно определить правое скобочное представление ггер(Т) дерева Т: (!) Если корнем дерева Т служит вершина а с поддеревьями Т„Т„..., Т„, то егер(Т) — (ггер(Т,), ггер(Т,), ..., ггер(ТА)) а, (2) Если корнем дерсва Т служат вершина а, не имеющая прямых потомкон, то ггер(Т) ==-а.

Таким образом, для дерева Т на рис. 0.12 ггер(Т)— = ((3,4) 2„((7,8,9) б) б) 1. В этом представлении прямой предок 1 2 э 4 Рис. О.!4. Дерево, ОЛ.З. Пути в графе 63 П! ЕДВАРИТРЛЬНЫЕ МАТЕМАТИЧЕСКие с ведения першины расположен непосредственно справа от первой правой скобки„заключающей эту вершину. Другое представление дерева можно получить, составив список прямых предков его вершин 1, 2, ..., а именно в этом порядке.

Чтобы опоанать корень, будем считать, что его предок — это О. Пример 0.26. Дерево, показанное на рис. 0.14, можно представить в виде 0122441777. Здесь 0 на первом месте указывает на то, что прямым предком вершины 1 явлнется ввершипа 0" (т. е. что вершина 1--корень). Число 1 на седьмом месте говорит о том, что прямым предком вершины 7 является вершина 1. В этом разделе мы опишем эффективный с вычислительной точки зрения алгоритм построения транзитивиого замыкания отношения )с, определенного па множестве А. Если это отношение представлять себе в виде (неупорядоченного) графа (А, 77), то его транзитивное замыкание будет множеством пар вершин (а, Ь), для которых существует путь из а в д.

Другая возможная интерпретация состоит в том, чтобы смотреть на отношение (или граф) как на квадратную булеву матрицу (т. е. матрицу из нулей и единиц), называемую жатрацей сл!езгекостей, в которой на пересечении 1'-й строки и 1-го столбца стоит 1 тогда и только тогда, когда элемент, соответствующий 1-й строке, находится В отношении )7 с элементом, соответствующим 7-му столбцу. 1!а рис.

О.! 5 показана матрица смежностей М, соответствующая графу на рис. О.б. Если М вЂ” матрица смеж- 62 О.В. НГКОТОРЫЕ ПОПЯТИЯ ТЕОРИИ ГРАФОВ ностей отношения )7, то М' =,," М" (где М" — матрица М, умЛ=1 иоженная ') на себя п раз) — матрица смежностей транзнтивного замыкании этого отношения. Таким образом, алгоритм нахож.

дения транзитивного замыкания можно применять и для вы. числения М+. Для матрипы М, изображенной на рис. 0.15, матрица М+ состоит из одних единив,. Рис. О.!5. Матрица смежпосте~! графа, изображенного на рис. 6.6. Фактически мы приведем здесь несколько более общий алгоритм. Будем предполагать, что задан (неупорядоченный ориентированный) граф, в котором каждой дуге, ведущей из Вершипы 1 в вершину !', приписан вес (илн стоимость) сг.. (Если из ! в 1 не ведет ни одна дуга, вес с; считается бесконечным.) Алгоритм будет вычислять для каждой пары вершин минимальный вес пути, ведущего из первой вершины пары во вторую.

В том случае, когда мы хотим вычислить только транзитивное замыкание отношения )7 на множестве (а„а„..., а„), надо положить е, — -О, если афау, и егу=- оо н противном случае. Алгоритм 0.2. В4 и н ямал ьиый вес (стоимость) путей в гр афе. Вход. Граф с а вершинами, занумерованными 1, 2, ..., п, и с весами е;, .

0 для всех ! (1й 1(п. Выход. Матрица М вЂ”. [1п171, в которой т,,— минималыгый нз весов путей, ведущих из вершины !' в вершйну ! (1(1, 1(п) Метод. (!) Положить тгу — -см для всех ! и 1 (1 -"1,1(п), (2) Положить й= 1. 1) !1ри этом используется обычная формула для умножения матриц, но с булевыми операциями и ' в качестве умйожения н сложения. ГЛ.

О. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВРДЕ ПНЯ (3) Для всех!'и (,еслит! >тта ! щ, поло „, „, щ нщ (4) Если Ь < п, увеличить Ь на едийицу и перейти к шагу (3). Если й=я, остановиться. П Ядром алгоритма 0.2 является шаг (3), на котором проверяется, можно ли уменьшить стоимость (вес) перехода из вершины !' в вершину !', перейдя сначала из вершины ! в вершину )5, а затем из Вершины Ь в вершину' !. Так как шаг (3) выполняется по одному разу для всевозможных значений т, !', й, то временная сложность алгоритма 0.2 равна и'". Сразу ие ясно, что алгоритм 0.5 находит миштмальный вес путей, ведущих нз !' в !.

Таким образом, надо доказать, что алгоритм 0.2 делает то, что требуется. Теорема 0.5. Когда алгорит,я 0.2 останавливается, щ! — наименьшая из величин, яредетовимых в виде суммы г, „+... -(-с. где в,=.! и о„— !. (Вта сумма — вес аути о„о„..., о„„веду- и(его из вершины ! в веришну !.) Дока за тель ство. Чтобы доказать эту теорему, докажем индукцней по значению ! переменной й в шаге (3) нашего алгоритма следующее утвсрждение: (0.5 !) После того как шаг (3) выполнен для Ь=-1, значением т! служит наименьшая из величин, представимых в виде суммы с„„+... +с,,„м, гдс о,—.

!', о„— !' и ни одно из о„..., о„! не превосходит !. Назовем эту наименьшую величину корректным значением т! для Ь-- 1, Эта величина — вес самого легкого (или стоимость самого дешевого) пути, ведущего из вершины !' в вершину 1, среди путей, не проходящих через вершины, номера которых больше !. Базис. Рассмотрим начальное условие, которое имеет вид 1=-0.

(Если угодно, можно рассматривать шаг (!) как шаг (3) для Ь вЂ” О.) Если ! — — О, то т=2, и значение т, =с„является корректным начальным значением. Шаг индукт(ии. Предположим, что утверждение (0.5.!) истинно для ! < 1,. Рассмотрил! значение т, после того, как шаг (3) выполнен для я — 1„. Допустим сначала, что значением т;, для й =1, является такая наименыпая сумма с„, +... +с„„, что ни одно ор (2 (р (т — 1) не равно 1,.

По предположению индукции с,„ + ... +с, , †корректн значение тт, для й = 1, — 1, и потому с,, + ... +с, „ †корректн значение тон также и для я=1,. ОАЧ НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ Т ерь предположим, что значением тау для ля Й = 1 является еп ',-с, что о =1, такая наименьп>ая сумма зт,=с,„- ... с, для некоторого р, 2(р т — 1. Это значит, что в! — это вес пути о„о„..., о, Можно считать, что иа этом пути нет верторой д Ф р и о — 1,, В противном случае путь а а' алить по о, о,„..., в содержал бы цикл и можно было бы уд аа '''а ю| , с , не увеличив крайней мере один член суммы с,„ + ...

с. .. е значения за,, Таким образом, для зт, всегда можно найти сум- му, в которой ор-— — 1, только для одного значения р, 2 ~р т — 1. читателю.) Рассмотрим суммы вт„==с,, с, и в, =с .+...+с„ .+... ', которые являютсн весами путей, ведур р ! «-! р о вве шин их из вершины ! в вершину ор и из вершины ор в р у ' щих и соответственно, По предположейию инду ц к ии можно считать, что зт, †корректн значение таа для й:=-! — 1, а в, ар =-.

†.. Таким об, азом, когда корректное значение т т для = —,— . Так шаг (3) выполняется для )5=1„переменной ау р — й т. п исваивается корректное значение тт, +т,, Итак, мы показали, что утверждение (0.5.!) истинно для всех !. Когда (=.п, утверждение (0.5.1) говорит о том, что в т" является наимень- конце работы алгоритма 0.2 значением тт, шая из возможных величин.

(,3 Распространенный частный случай нахождения минимума вен ей в г афе — это случай, когда мы хотим найти множество вершин, достижимых из данной вершины. н . Эквивалентная множестве А и элемент формулировка: дано отношение )с на множе иЕА; надо найти множество таких 5ЕА, что а)с Ь, где В'— ля этой цели можно транзитивное замыкание отношения, я применить следующий алгоритм, имеющий квадратичную временную сложность, лгоритм 0.3. Нахождение множества вершин, достижимых из данной вершины а (ар не нтирован- ного) графа, Вход. Граф (А, В), в котором А — конечное множество, и а 6 А.

Выход. Множество таких Вершин 5ЕА, что аД"Ь. М од. Б ет об азоваи список Т., менявшийся в ходе работы алгоритма. Кроме того, будут отмечаться некоторые эле е элементы множества А, Вначале все элементы из А не отмечены. (1) Положить Б=а. (2) Если список Б пуст„остановиться. В противном случае вычеркнуть из Б первый элемент Ь и отметить его в А. 3 А.

Аао, Да!. Ульман а, ! вд гл. о. пгздвлеитвльные млтемАтичвскиа свгдзния упилжне ния (3) Поместить в конец списка Е все неотмеченные элементы сЕА, для которых Ыс, и перейти к шагу (2). ) Доказательство того, что алгоритм 0.3 работает правильно, оставляем в качестве упражнения. улэлжнения 0.5.1. Каково максимальное число дуг, которые может иметь ациклический граф с п вершинами? 0,5.2. Докажите теорему 0.3. 0.5.3. Постройте прямой и обратный порядки вершин дерева, изображенного на рис. 0.14. Напишите левое и правое скобочное представления этого дерева.