5.11. ДОМИНАТОРЫ В ОРИЕНТИРОВАННЫХ АЦИКЛИЧЕСКИХ ГРАФАХ: КОМБИНИРОВАНИЕ ПОНЯТИЙ

В этой главе мы уже познакомились с несколькими приемами, применяемыми для разработки эффективных алгоритмов, например с поиском в глубину и разумным упорядочением вычислений. В гл. 4 изучили много структур данных, полезных для представления множеств, над которыми выполняются различные операции. Эту главу мы закончим примером, иллюстрирующим, как можно строить эффективные алгоритмы, комбинируя структуры данных из гл. 4 с техникой для графов, развитой в данной главе. Мы будем

находить доминаторы в ориентированном ациклическом графе, используя, в частности, алгоритм нахождения MIN в свободном режиме, алгоритм объединения непересекающихся множеств и 2-3-деревья вместе с поиском в глубину.

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

Узел называется доминатором узла до, если любой путь из корня в до проходит через Каждый узел доминирует над самим собой, а корень доминирует над каждым узлом. Множество доминаторов узла до можно линейно упорядочить, расположив их в порядке вхождения в какой-нибудь кратчайший путь из корня в до. Доминатор узла до, ближайший к нему и отличный от него, называется его непосредственным доминатором. Так как множество доминаторов каждого узла линейно упорядочено, то отношение доминирования можно представить деревом с корнем называемым доминаторным деревом для Вычисление доминаторов полезно в задаче оптимизации кодов (Ахо, Ульман [1973], Хект [1973]).

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

Пусть граф и его подграф. Если будем писать а Через и будем обозначать соответственно транзитивное и рефлексивно-транзитивное замыкания отношения Если будем писать а

Лемма 5.12. Пусть ориентированный ациклический граф с корнем остовное дерево для него с корнем построенное поиском в глубину. Пусть такие узлы из V, что Далее, пусть и прямые ребра. Тогда замена прямого ребра прямым ребром не меняет доминаторов никакого узла в (см. рис. 5.28).

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

Рис. 5.28. Преобразование из леммы 5.12.

идущий из и не содержащий Если то замена ребра а в на путь а дает путь в графе идущий из и не содержащий Так как или то найдется путь в идущий из и не содержащий получили противоречие.

Допустим, что доминатор узла но не в Тогда в найдется путь из не содержащий Так как этот путь не проходит целиком в то он должен содержать ребро Следовательно, узел лежит на пути Таким образом, в есть путь не содержащий узел у; получили противоречие.

Лемма 5.13. Пусть те же, что и в лемме 5.12, а и прямое ребро графа Если в нет прямого ребра для которого и поперечного ребра для которого то удаление древесного ребра, входящего в не меняет доминаторов никакого узла в (см. рис. 5.29).

Рис. 5.29. Преобразование из леммы 5.13.

Рис. 5.30. Преобразование из леммы 5.14.

Доказательство. Доказательство аналогично доказательству леммы

Лемма 5.14. Пусть те же, что и в лемме 5.12, - поперечное ребро графа общий предок для с наибольшим номером. Пусть прямое ребро и Если ни в один узел пути отличный от не входит поперечное ребро, то замена поперечного ребра прямым ребром не меняет доминаторов никакого узла в (см. рис. 5.30).

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

Допустим, что доминатор узла но не в Тогда в найдется путь из не содержащий Понятно, что содержит ребро Запишем в виде Путь с должен содержать узел, лежащий на пути поскольку нет поперечных ребер, входящих в узлы на пути с (исключая узел Пусть такой узел с наибольшим номером, а участок пути от за которым следует а за ним участок пути от до Пусть путь за которым

следует участок пути от до Если узел у лежит на то он должен лежать и на причем Если он лежит на то должен лежать на Так как то один из этих путей в не содержит у; получили противоречие.

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

Говоря неформально, можно сказать, что мы строим доминаторное дерево для данного ориентированного ациклического графа следующим образом. Сначала поиском в глубину строим в отправляясь от корня, соответствующее остовное дерево Номера узлов графа меняем на их номера, порожденные поиском в глубину. Затем применяем к преобразования из лемм Они выполняются двумя взаимосвязанными подпрограммами, одна из которых обрабатывает прямые ребра, а другая — поперечные.

1. Прямые ребра

Предположим на время, что в нет поперечных ребер. Если в узел у входит более одного прямого ребра, то по лемме 5.12 все прямые ребра, входящие в у, за исключением одного с наименьшим началом, можно удалить, не изменив доминаторов ни одного узла.

Составным ребром назовем упорядоченную пару где узел, называемый началом составного ребра, множество узлов, называемое концом составного ребра. Составное ребро представляет множество ребер

Многократно применяем лемму 5.12, чтобы изменить начала прямых ребер. В какой-то момент начало каждого ребра из множества ребер с общим началом изменится на Чтобы сделать это эффективно, представим одним составным ребром некоторые множества прямых ребер с общим началом. Вначале каждое прямое ребро представляется составным ребром

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

Затем проходим остовное дерево в порядке, обратном к прямому. Возвращаясь по ребру остовного дерева, обнаруживаем,

Рис. 5.31. Корневой ориентированный ациклический граф.

что множество содержит составное ребро для каждого подлинного предка узла который в данный момент является началом прямого ребра для некоторого потомка узла Далее делаем следующее.

1) Пусть составное ребро в имеющее начало с наибольшим номером. Если удаляем его из (Это составное ребро представляет множество прямых ребер, начала которых перемещены в узел но больше не будут перемещаться под действием преобразования из леммы 5.12.) Удалим из ребро остовного дерева с концом

2) Если есть в прямое ребро то для каждого составного ребра ( из для которого

(а) удаляем ( из

объединяем с концом того составного ребра из которое представляет среди прочих и ребро

3) Заменяем на

(Шаг 1 соответствует применению леммы 5.13, а шаг 2 — леммы 5.12.)

Пример 5.15. Рассмотрим корневой ориентированный ациклический граф изображенный на рис. 5.31. Поиск в глубину на графе может породить граф, изображенный на рис. 5.32,а, где указаны также -множества, поставленные в соответствие каждому узлу. На рис. приведены результаты преобразований прямых ребер. Окончательное доминаторное дерево изображено на рис. 5.32,г.

Оставляем читателю доказать, что по достижении корня действительно получается доминаторное дерево (в предположении, что

Рис. 5.32. Результаты преобразований прямых ребер: а — вначале; б - по возвращении вдоль ребра (6, 7) остовного дерева; в — по возвращении вдоль ребра остовного дерева; г- по возвращении вдоль ребра остовного дерева.

нет поперечных ребер). Этот алгоритм можно эффективно реализовать с помощью алгоритма объединения непересекающихся множеств и обрабатывать им множества концов у составных ребер. Множества составных ребер можно представить 2-3-деревьями. Это связано с тем, что мы должны уметь эффективно удалять составные ребра, выделять в множестве составных ребер ребро с наибольшим началом и строить объединение множеств составных ребер. При такой структуре данных для обработки графа с ребрами требуется время

2. Поперечные ребра

В общем случае нельзя предполагать, что поперечных ребер нет. Но можно с помощью метода, излагаемого ниже, заменить поперечные ребра прямыми. Однако эту замену не следует делать до работы на прямых ребрах, описанной в п. 1, ибо структура данных,

которая строится в п. 1, помогает эффективно применить лемму 5.14. С другой стороны, не надо полностью выполнять п. 1 до устранения поперечных ребер, поскольку каждое устраненное поперечное ребро становится прямым. На самом деле мы должны добавить шаги обработки поперечных ребер к тому прохождению в порядке, обратном к прямому, которое было описано применительно к прямым ребрам. Заметим, что в п. 1 требуется (из-за применения леммы 5.13), чтобы в определенные моменты времени в определенные узлы не входили поперечные ребра. Поскольку прохождение ведется в порядке, обратном к прямому, шаги, описанные ниже, преобразуют поперечное ребро в прямое перед тем моментом, когда его наличие делало лемму 5.13 неприменимой.

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

1) При прохождении древесного ребра удаляем из каждую пару в которой Узел общий предок с наибольшим номером узлов х и у.

2) По возвращении к о по ребру остовного дерева заменяем на

Вычисление предков с наибольшим номером можно осуществить не более чем за шагов, где в — число ребер графа для этого можно воспользоваться обобщением MIN-алгоритма, работающим в свободном режиме, о котором упоминается в упр. 4.21.

Обработка поперечных ребер состоит в том, что они преобразуются в прямые по лемме 5.14. Процесс преобразования поперечных ребер в прямые надо выполнять во время обработки прямых ребер. Каждому узлу ставим в соответствие некоторое множество составных ребер. Вначале поперечное ребро при По возвращении в узел вдоль древесного ребра совершаем помимо шагов, связанных с обработкой прямых ребер, следующие шаги.

1) Заменяем на

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

Рис. 5.33. Удаление поперечных ребер: а — вначале; б - после рассмотрения ребра

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

3) Пусть прямое ребро (если оно есть) с концом Если такого ребра нет, то пусть древесное ребро, входящее в у. После просмотра всех потомков узла удаляем из все составные ребра, начала которых лежат выше и. Объединяем множества концов удаленных составных ребер и образуем новое составное ребро с началом и. Добавляем новое составное ребро к

Пример 5.16. Рассмотрим глубинное остовное дерево на рис. 5.33,а. Значения приведены для обрабатываемых узлов. Так как из узла 2 в узел 8 идет прямое ребро, заменяем составное ребро на Затем присоединяем Так как прямое ребро, преобразуем составное ребро По возвращении в узел 6 множество станет равным

По возвращении из узла 6 в узел 3 множество становится равным Узел 3 является предком с наибольшим номером узлов 6 и 5 и узлов 8 и 4. Поэтому удаляем из состав ребра и добавляем к прямые ребра и Результат показан на рис. Последующая часть поиска не приводит ни к каким изменениям.

Составные поперечные ребра можно представить 2-3-деревьями. Предлагаем в качестве упражнения формальное описание доминаторного алгоритма. Если вы сможете найти подходящие структуры, вы освоили технику гл. 4 и 5.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Сведения по теории графов можно почерпнуть из книг Бержа [1958] и Харари [1969]. Алгоритм 5.1, строящий остовные деревья наименьшей стоимости, взят из работы Крускала [1956]. Прим [1957] указывает другой подход к этой задаче. Алгоритм, предложенный в упр. 5.3, указал нам Спира.

Алгоритм, касающийся двусвязности и использующий поиск в глубину, принадлежит Хопкрофту. Алгоритм для сильно связных компонент взят у Тарьяна [1972]. В литературе отражены многочисленные применения поиска в глубину для построения оптимальных или наилучших из известных алгоритмов. Хопкрофг, Тарьян [1973а] дают линейную проверку планарности. В другой работе Хопкрофг, Тарьян [19736] описывают линейный алгоритм нахождения -связных компонент. Тарьян [1973а] на основе той же идеи разработал наилучший из известных алгоритмов нахождения доминаторов. Кроме того, Тарьян [19736] предлагает тест для «редуцируемости потоковых графов».

Алгоритм 5.5, т. е. общий алгоритм нахождения путей, по существу, принадлежит Клини [1956], который использовал его в связи с «регулярными выражениями» (разд. 9.1). Данная здесь форма этого алгоритма заимствована у Мак-Нотона, Ямады [1960]. Алгоритм сложности строящий транзитивное замыкание, взят из работы Уоршола [1962]. Аналогичный алгоритм, отыскивающий кратчайшие пути для всех пар узлов, заимствован у Флойда [1962] (см. также Ху [1968]). Алгоритм для случая одного источника изложен по работе Дейкстры [1959]. Сайра, Пан [1973] показывают, что алгоритм Дейкстры, по существу, оптимален, если в качестве модели брать деревья решений.

Данциг, Блаттнер, Рао [1967] заметили, что наличие ребер с отрицательными стоимостями не влияет на решение задачи нахождения кратчайших путей между всеми парами точек, если нет цикла с отрицательной стоимостью. Джонсон [1973] обсуждает задачи с одним источником при наличии ребер с отрицательными стоимостями; он же приводит решения упр. 5.21 и 5.22. Спира [1973] дает алгоритм нахождения кратчайшего пути за среднее время

Связь между задачей нахождения путей и умножением матриц описана в работах Мунро [1971] и Фурмана [1970] (теорема 5.7) и Фишера, Мейера [1971] (теорема 5.6). Связь с транзитивной редукцией (упр. 5.13-5.15) заимствована у Ахо, Гэри, Ульмана [1972]. Ивен [1973] обсуждает -связность графов.