1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 48
Текст из файла (страница 48)
Они выполняются двумя взаимосвязанными подпрограммами, одна из которых обрабатывает прямые ребра, а другая— поперечные. 1. Прямые ребра Предположим на время, что в С нет поперечных ребер. Если в узел о входит более одного прямого ребра, то по лемме 5.12 все прямые ребра, входящие в о, за исключением одного с наименьшим началом, можно удалить, не изменив доминаторов ни одного узла. Составным ребром назовем упорядоченную пару (1, Н), где 1— узел, называемый началом составного ребра, а Н вЂ” множество узлов, называемое концом составного ребра.
Составное ребро (1, (И„И„..., И )) представляет множество ребер (1, И1), (1, И,),... .."., (1, И,). Многократно применяем лемму 5.!2, чтобы изменить начала прямых ребер. В какой-то момент начало каждого ребра из множества ребер с общим началом 1 изменится на 1'. Чтобы сделать это эффективно, представим одним составным ребром некоторые множества прямых ребер с общим началом. Вначале каждое прямое ребро (1, И) представляется составным ребром (1, (И)). Каждому узлу о графа С поставим в соответствие множество Р[о). Зто множество содержит такие пары (1, (И„И„..., И„)), что 1 — предок узла о, каждый узел И; — потомок узла и и (1, И~)— прямое ребро в 6. Вначале Р[о)=((И (и))), где 1 — начало (с наименьшим номером) прямого ребра с концом о.
Затем проходим остовное дерево в порядке, обратном к прямому. Возвращаясь по ребру (о, ш) остовного дерева, обнаруживаем, 242 аль дОмииАТОРЫ В ОРиентиРОВАниых ГРАФАХ Рнс. Б.ЗП Корневой ориентированный апиклический граф. что множество ГЫ содержит составное ребро для каждого подлинного предка 1 узла ги, который в данный момент является началом прямого ребра для некоторого потомка узла ги.
Адалее делаем следующее, 1) Пусть (1, ()т„)т„..., й„)) — составное ребро в г"[ги), имеющее начало с наибольшим номером. Если г=и, удаляем его из ГЫ. (Это составное ребро представляет множество прямых ребер, начала которых перемещены в узел о, но больше не будут перемещаться под действием преобразования из леммы 5.12.) Удалим из 0 ребро остовного дерева с концом йы 1<1(гп. 2) Если есть в б прямое ребро (г, п) '), то для каждого составного ребра (и, (и„..., Ь„)) из г[ги), для которого и~у, (а) удаляем (и, (Л„..., Ь )) из ГЫ, (б) объединяем (гт„..., й„) с концом того составного ребра из г[п), которое представляет среди прочих и ребро (5 и), 3) Заменяем г'[о) на г[р) () ГЫ. (Шаг 1 соответствует применению леммы 5.13, а шаг 2 — леммы 5,12.) Пример 5.15. Рассмотрим корневой ориентированный ациклический граф О, изображенный на рис, 5.31.
Поиск в глубину на графе б может породить граф, изображенный на рис. 5.32,а, где указаны также Г-множества, поставленные в соответствие каждому узлу. На рис. 5.32,б — г приведены результаты преобразований прямых ребер. Окончательное доминаторное дерево изображено на рис.
5.32,г. [ ) Оставляем читателю доказать, что по достижении корня действительно получается доминаторное дерево (в предположении, что г] Напомним, что мы предполагаем, что все прямые ребра с конном и, кроме имеющих начало с наименьшим номером, удалены на П. ГЛ. Ь. АЛГОРИТМЫ НА ГРАФАХ ) ((1, Я>)) ! ((1, 133) (б] ((2,16, ГЕ (в) - (а,свн) л(4) ((1, 14И ГР) -((5,НИ) Г (5) ((2, 15И) Г(4) = ((1 (4))) Щ= ((2,(5И) 6 1 6 ((1,С5,4,5,6,7И) / ) Я ~5) Рнс. 5.32. Результаты преобразований прямых ребер: о — вначале; б — по шевращенни вдоль ребра (6, 7) остовного дерева; в — по возвращении вдоль ребра (3, 4) остовиого дерева; а — по возвращении вдоль ребра (1, 2) остовного дерева.
нет поперечных ребер). Этот алгоритм можно эффективно реалнзовать с помощью алгоритма объедннення непересекающихся множеств н обрабатывать нм множества коннов у составных ребер. Множества Г(о) составных ребер можно представить 2-3-деревьямн. Зто связано с тем, что мы должны уметь эффективно удалять составные ребра, выделять в множестве составных ребер ребро с наибольшим началом н строить объединение множеств составных ребер. Прн такой структуре данных для обработкн графа с е ребрами требуется время 0(и )оя э).
2. Поперечные ребра В общем случае нельзя предполагать, что поперечных ребер нет. Но можно с помощью метода, излагаемого ниже, заменить поперечные ребра прямыми. Однако эту замену не следует делать до работы на прямых ребрах, описанной в и. 1, нбо структура данных, ко- алс доминатОРы В ОРиентиРОВАнных ГРАФАХ торая строится в п. 1, помогает эффективно применить лемму 5.14. С другой стороны, не надо полностью выполнять и.
1 до устранения поперечных ребер, поскольку каждое устраненное поперечное ребро становится прямым. На самом деле мы должны добавить шаги Обработки поперечных ребер к тому прохождению в порядке, обратном к прямому, которое было описано применительно к прямым ребрам. Заметим, что в п. 1 требуется (из-за применения леммы 5.13), чтобы в определенные моменты времени в определенные узлы ие входили поперечные ребра. Поскольку прохождение ведется в порядке, обратном к прямому, шаги, описанные ниже, преобразуют поперечное ребро в прямое перед тем моментом, когда его наличие делало лемму 5.!3 неприменимой. Пусть 3 — глубинное остовное дерево для б. Вначале для каждого поперечного ребра (о, в) вычисляем общего предка узлов о и в с наибольшим номером.
Каждому узлу о припишем множество ЕЫ упорядоченных пар (и, в), где (и, в), и)в, представляет запрос о предке узлов и и в с наибольшим номером. Вначале Е[и[= =((о, в)[ есть поперечное ребро (в, в), в)в). Во время прохождения дерева 3 в соответствии с процедурой в п. 1 делаем следующее.
1) При прохождении древесного ребра (о, Га), о(в, удаляем из Е[в! каждую пару (х, у), в которой у -в. Узел о — общий предок с наибольшим номером узлов х и у. 2) По возвращении к в по ребру (о, в) остовного дерева заменяем Е[в1 на ЕЫ (! Е[в[. Вычисление предков с наибольшим номером можно осущест. вить не более чем за 0(еб(е)) шагов '), где и — число ребер графа б; для этого можно воспользоваться обобщением М15[-алгоритма, работающим в свободном режиме, о котором упоминается в упр.
4.21. Обработка поперечных ребер состоит в том, что они преобразуются в прямые по лемме 5.!4. Процесс преобразования поперечных ребер в прямые надо выполнять во время обработки прямых ребер. Каждому узлу о ставим в соответствие некоторое множество С!О1 составных ребер. Вначале СЫ=((о, (Ь„..., Ь ))[(о, й,) — поперечное ребро при 1<1<ГИ). По возвращении в узел О вдоль древесного ребра (о, в) совершаем помимо шагов, связанных с обработкой прямых ребер, следующие шаги, 1) Заменяем СЫ на СЫ () С[в[. 2) Удаляем каждое поперечное ребро (х, у), для которого о— предок с наибольшим номером узлов х и у, из составного ребра, где оно представлено в данный момент. Если 1 — начало этого составного ребра, заменяем поперечное ребро (х, у) а) Си.
примечание иа стр. 202. — Прим. ред. 34$ ГЛ. Е. АЛГОРИТМЫ НА ГРАФАХ С[а) [Ю, (зф / с[71-б а б Рнс, 3.33, Удаление поперечных ребер: а — вначале; б — после рассмотрения ребра (3, б). прямым ребром (2, у), Если в у уже входит прямое ребро, оставляем только прямое ребро с тем началом, у которого номер меньше.
3) Пусть (и, о) — прямое ребро (если оно есть) с концом о. Если такого ребра нет, то пусть (и, о) — древесное ребро, входящее в о. После просмотра всех потомков узла о удаляем из С[о1 все составные ребра, начала которых лежат выше и. Объединяем множества концов удаленных составных ребер и образуем новое составное ребро с началом и.
Добавляем новое составное ребро к С[о1. Пример 5.16. Рассмотрим глубинное остовное дерево на ис. 5.33,а. Значения С[о) приведены для обрабатываемых узлов. ак как из узла 2 в узел 8 идет прямое ребро, заменяем составное ребро (8, (4)) в С[81 на (2, (4)). Затем присоединяем С[81 к С[71, Так как (1, 7) — прямое ребро, преобразуем составное ребро (2, (4)) в (1, (4)). По возвращении в узел 6 множество С[61 станет равным ((1, (4)), (6, (5))). По возвращении из узла 6 в узел 3 множество С[31 становится равным ((3, (5)), (1, (4))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
