не является по-

Рис. 0.9. пример дерева.

(1) А непусто и содержится в А,

(2) R = {AxA)[\R.

{3) ни одна вершина из множества А-А томном вершины из множества А.

Например, б на рис. 0.9 - поддерево дерева а. Мы будем говорить, что корень поддерева i5o>iWHWp(/e i над этим ЕГОддеревом.

0.5.4. Упорядоченные графы

Упорядочеяшм графом называется пара (Л, R), где А обозначает как и раньше, множество вершин, а -множество лшейио упорядоченных списков дуг, каждый элемент которого имеет вид {{а, bJ, (а, Ь), ...,{а, Этот элемент указывает, что из

вершины а выходят п дуг, причем первой из них считается дуга, входящая в вершину й, второй-дуга, входтцая в вершину Ь, и т. д.

Пример 0.23. На рис. 0.J0 изображен упорядоченный граф. Линейное упорядочение дуг, выходящих из вершины, указывается

Рис. 0.10. Упорядоченный граф.

С помощью нумерации их числами 1, 2, rii где п-степень по выходу этой вершины.

, формально упорядоченный граф на рнс. 0.10 определяется как пара {А, R), где Л-{г, 6, с} HR={{{a,c), {а, Ь), (а, Ь), {а, а)),

{Ф,ст. □

Заметим, что упорядоченный граф на рис. 0.10 не является Ориентированным в смысле нашего определения, так как в нем из вершины а в вершину Ь ведут две дуги. (Напомним, что во множестве дуг графа каждый элемент встречается только один раз.)

Как и для неупорядоченных графов, определим понятия раз-мегки и равенства помеченных графов.

Определение. Разметкой упорядоченного графа С==(Л, R) назовем такую пару функций fug, что

(1)/ Л -для некоторого множества [f помечает вершины);

(2) g отображает R в последовательности символов из некоторого "множества Г так, что образом списка ((а, Ь), («,&„)) является последовательность из п символов (g помечает дуги).

Помеченные графы 0 = (Л, R) и G = {A.j., R) с разметками ffi» iftj ez) соответственно назовем равными, если существует такое биективное отображение h: Л-А, что

(I) Ri содержит ((а, Ь), ..., (а, &„)) тогда и только тогда, когда R содержит {{h (а), h (&J). ..., (А [а], к (&„)); (2> ft{u)f(h{a)) для всех аА;

т gi (((«. К),... bM=g, т (а), h (&J), ..., (Л {а), h (&J)).

Неформально можно сказать, что два помеченных упорядо-: ценных графа равны, если существует взаимно однозначное соответствие между их вершинами, сохраняющее метки вершин и дуг. Если множества значений обеих разметок состоят из едии-ствениого элемента, то граф по существу не помечен, и надо проверять только условие (1). Аналогично, если одним элементом помечены только все вершины или только все дуги, то соответственно становится тривиальным условие (2) или (3).

Для каждого упорядоченного графа (Л, R) существует неупо-.рядоченный граф (Л, R) (называемый его основой), дугами ко-.торого служат дуги графа (Л, R) без учета порядка и без повто- . ""-рений, т. е. R состоит из пар (а, Ь), для которых существует /№сок ((а, bj), ...,(а, 6„)) $и 6 = 6,-для некоторого!, lin.

Упорядоченный ациклический граф-это упорядоченный граф, ~ОСисжой которого является ациклический граф.

Упорядоченное дерево-это упорядоченный граф (Л, R), основой которого является дерево, и если {{а, Ь), ..., (а, Ь„)) R, го bibj для ij.

ГЛЦРЕДВАРИТЕЛЬНЫЕ MATM£?j4ECkHe СВЕДЕНИЯ

uu.fo оговорено противное, то предполагается, что на диаграмме упорядоченного аниклического графа или дерева пря мыепотомкн вершины всегда линейно упорядочены слева иа-

Рис. ом. Два дерева

Когда рассматривается вопрос о равенстве двух графов, существенно, являются они упорядоченными илн нет.

Например, два дерева Ту и Т, изображенные на рис. 0.11, равны, если они неупорядоченные, и различны в противном случае.

0.5.5. Индукция по ациклическому графу

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

В качестве таких параметров можно брать глубину вершины, т. е. длину минимального пути (или в случае дерева просто длину пути) от базовой вершины (в случае дерева от корня) до данной вершины, и высоту (или уровень) вершины, т. е. длину максимального пути от вершины до листа.

Другой подход к индукции по конечным упорядоченным деревьям состоит в том, чтобы каким-то образом упорядочить вершины и вестн индукцию по позиции вершины в полученной последовательности. Опишем два распространенных способа упорядочения.

Определение. Пусть Т - конечное упорядоченное дерево. Прямой порядок вершин дерева Т представляет собой список (последовательность), который получается рекурсивным применением шага 1, начиная с корня.

Шаг I; Пусть данное применение шага I относится к вершине а. Если а-лист, включить вершину а в список. Если а не лист и ее прямые потомки - вершины а, а, ..., включить а в список и затем применить шаг I к вершинам а, а, ..в этом порядке.

Обратный порядок вершин дерева Т получится, если заключительную часть последнего предложения в описании шага I заменить на „применить luar 1 к вершинам а, а, .. -, а„ в этом порядке, а затем включить в список вершину a.

Рис. 0.12. Лпорядочеииое дерево.

Пример 0.24. Рассмотрим упорядоченное дерево на рис, 0.12. Прямой порядок вершин: 123456789; обратный порядок: 342789651. □

Иногда можно провести индукцию по месту, которое занимает вершина в том или ином упорядочении.

0.5.6. Вложение частичного порядка в линейный

Если задан частичный порядок R на множестве Л, часто бывает нужен линейный порядок, содержащий этот частичный порядок. Эга проблема вложения частичного порядка в линейный называется топологической сортировкой.

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

Например, при такой деформации граф, изображенный на рис. 0.8, может превратиться в столбец, показанный на рис. 0.13.

Формально можно сказать, что частичный порядок R на множестве А вложен в линейный порядок R\ если /?- линейный порядок и RR\ т. е. aRb влечет aRb для всех а и & из Л.

гл. 0. ПРЕДВАРИТРЛьштМТРп1ТПТ1Г

СКНЕ СВЕДЕНИЯ

0.5. НЕКОТОРЫЕ понятия ТЕОРИИ ГРАФОВ

Для данного частичного порядка R существует много линейных порядков, в которые его можно вложить (упр. 0.5.5). Следующий алгоритм находит один из таких линейных порядков:

Алгоритм 0.1. Топологическая сортировка.

Вход. Частичный порядок R на конечном множестве Л.

Выход. Линейный порядок R на Л, для которого R R.

Метод. Так как А - конечное множество, линейный порядок на А можно представить в виде списка а, а, а„, для которого

aiRuj, если i<j, и А = {а,а, ...,а„\. Эта последовательность элементов строится с помощью следующих шагов:

(1) Положить /--1, = Л и Ri=R.

(2) Если Ai пусто, остановиться и выдать ,,(22» ••-,/-1 в качестве искомого линейного порядка. В противном случае выбрать в А такой элемент а., что aRa,. ложно для всех

(3) Положить Л,- ,J =Л -{а,-} и Ri+i = - П (Л- (.1 X <44.j). Затем увеличить / на единицу и повторить шаг 2. □

Если частичный порядок представлен в виде ациклического графа, то алгоритм 0.1 допускает особенно простую интерпретацию. На каждом шаге алгоритма (Л,-, R-) является ациклическим графом и Qj- - его базовая вершина. Ациклический граф /?,4.i) образуется из (Л, R) вычеркиванием вершины а- и всех выходящих из нее дуг.

Пример 0.25. Пусть А = {а, Ь, с, d) и R = \{а, Ь), {а, с), {Ь, d), (с, d)\. Так как а-единственная вершина, для которой aRa ложно при всех аА, надо взять аа.

Тогда А-={Ь, с, d] и К{{Ь, rf), (с, d)}; теперь в качестве можно взять либо Ь, либо с. Выберем аЬ. Тогда А - {с, d} и R:i={{c,d)}. Продолжая аналогично, найдем ас и a==d.

В результате получился линейный порядок R = {(а, Ь), (Ь, с), (c,rf), {а, с), {b,d), {ad)}. □

Теорема 0.4, Алгоритм 0.1 дает линейный порядок R\ в который вложен данный частичный порядок R.

Доказательство. Простое упражнение на индукцию. □

Рис. 0.13. Линейный порядок, полученный из ациклического графа на рис. 0.8.

0.5.7. Представления деревьев

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

Очевидно, что одно из одномерных представлений дерева Т - {А, R)-это запись самих множеств Л и R,

Существуют и другие представления. Например, для указания глубины вершин дерева можно использовать вложенные скобки. Напомним, что глубиной вершины называется длина пути от корня до этой вершины. Глубина вершины 1 на рис. 0.9 равна О, глубина вершины 3 равна 1, а вершина 6 находится на глубине 2. Глубиной (или высотой) дерева называется длина наибольшего пути. Глубина дерева на рис. 0.9 равна 2.

Используя скобки для указания глубины, можно представить изображенное на рис. 0.9 дерево в виде 1(2,3(4,5,6)). Такую запись будем называть левым скобочным представлением, так как поддерево представляется выражением, заключенным в скобки, а его корень записывается непосредственно слева от левой скобки.

Определение. Левое скобочное представление дерева Т (обозначается /гер(7)) можно получить, применяя к нему следующие рекурсивные правила.

(1) Если корнем дерева Т служит вершина а с поддеревьями Т, 72, ...,Tf, расположенными в этом порядке (их корни- прямые потомки вершины а), то 1гер{Т)-а(1гер{Т), кер{Т), ..•,/гер(Г,)).

(2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то /rep(7) = fl:.

Если в левом скобочном представлении стереть все скобки, получится прямой порядок вершин дерева.

-Аналогично можно определить правое скобочное представление ггер(7) дерева Т:

(1) Если корнем дерева Т служит вершина а с поддеревьями Т,, Г,,..., Г„ то тр{Т)-{тр(Т,), /-гер(Г,), .. пер(Т,))а.

(2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то ггер{Т) = а.

Таким образом, для дерева Т на рис. 0.12 ггер(Т) - ((3, 4) 2, ((7,8, 9) 6) 5) 1. В этом представлении прямой предок