следует участок пути Р от d до w. Если узел v лежит на Pi, то он должен лежать и на х zs d, причем v>x. Если он лежит на Ра, то должен лежать на г zs - Так как ах, то один из этих путей в G не содержит v; получили противоречие. □

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

Говоря неформально, можно сказать, что мы строим доминатор-ное дерево для данного ориентированного ациклического графа G= {V, Е) следующим образом. Сначала поиском в глубину строим в G, отправляясь от корня, соответствующее остовное дерево S= = (V, Т). Номера узлов графа G меняем на их номера, порожденные поиском в глубину. Затем применяем к G преобразования из лемм 5.12-5.14. Они выполняются двумя взаимосвязанными подпрограммами, одна из которых обрабатывает прямые ребра, а другая - поперечные.

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

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

Составным ребром назовем упорядоченную пару (t, Н), где t - узел, называемый началом составного ребра, а Я - множество узлов, называемое концом составного ребра. Составное ребро {t, {hi, Ла, . . ., /tfc}) представляет множество ребер (t, hi), {t, ha), . . .

..., {t. К).

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

Каждому узлу v графа G поставим в соответствие множество F[v]. Это множество содержит такие пары {t, {hi, ha, . . ., h}), что t - предок узла v, каждый узел hi - потомок узла v и {t, hi) - прямое ребро в G. Вначале F[v]={{t, {v})}, где - начало (с наименьшим номером) прямого ребра с концом и.

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

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

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

1) Пусть (t, {hi, hi, . . ., h„)) - составное ребро в F[w], имеющее начало с наибольшим номером. Если t=v, удаляем его из F[w]. (Это составное ребро представляет множество прямых ребер, начала которых перемещены в узел v, но больше не будут перемещаться под действием преобразования из леммы 5.12.) Удалим из G ребро остовного дерева с концом hi, 1<1</п.

2) Если есть в G прямое ребро [t, v) то для каждого составного ребра {и, {hi, . . ., h„)) из Fiw], для которого ut,

(а) удаляем (н, {hi, . . ., h„}) из Flw],

(б) объединяем {hi, . . ., h„} с концом того составного ребра из F[v], которое представляет среди прочих и ребро (t, v).

3) Заменяем F[v] на Flv] и F[w].

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

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

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

1) Напомним, что мы предполагаем, что все прямые ребра с концом v, кроме имеющих начало с наименьшим номером, удалены из С

/[1] = 0 Г[2] = 0

\-[б] = {(2,{6})} /

* [4]-{(1,<4»>/

[7] = {(3,<7»}

[ll=0 Ш-0

\ ум={(1.-!3))>

W6]={(2.-(6,7})}

[3]={(1Д3.4,5,6.7})}

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

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

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

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