Построение и анализ вычислительных алгоритмов
- Автор(ы)
- Хопкрофт Д, Ульман Дж, Ахо А
- Год
- 1979
- Издательство
- Мир
- Теги
- Программирование
Аннотация
5.11. ДОМИНАТОРЫ В ОРИЕНТИРОВАННЫХ ГРАФАХ торая строится в п. 1, помогает эффективно применить лемму 5.14. С другой стороны, не надо полностью выполнять п. 1 до устра- устранения поперечных ребер, поскольку каждое устраненное поперечное ребро становится прямым. На самом деле мы должны добавить шаги обработки поперечных ребер к тому прохождению в порядке, обратном к прямому, которое было описано применительно к пря- прямым ребрам. Заметим, что в п. 1 требуется (из-за применения леммы 5.13), чтобы в определенные моменты времени в определенные узлы не входили поперечные ребра. Поскольку прохождение ведется в порядке, обратном к прямому, шаги, описанные ниже, преобразуют поперечное ребро в прямое перед тем моментом, когда его наличие делало лемму 5.13 неприменимой. Пусть S — глубинное остовное дерево для G. Вначале для каж- каждого поперечного ребра (v, w) вычисляем общего предка узлов v и а) с наибольшим номером. Каждому узлу v припишем множество L[v] упорядоченных пар (и, w), где (и, w), u>w, представляет за- запрос о предке узлов и и а) с наибольшим номером. Вначале L[v]= = {(v, w)\ есть поперечное ребро {v, w), v>w}. Во время прохож- прохождения дерева S в соответствии с процедурой в п. 1 делаем следую- следующее. 1) При прохождении древесного реора (v, w), v<Cw, удаляем из L[v] каждую пару (х, у), в которой y^w. Узел v — об- общий предок с наибольшим номером узлов х и у. 2) По возвращении к v по ребру (v, w) остовного дерева заме- заменяем Llv] на L[v][jL[w]. Вычисление предков с наибольшим номером можно осущест- осуществить не более чем за O(eG(e)) шагов1), где в — число ребер графа G; для этого можно воспользоваться обобщением MIN-алгоритма, работающим в свободном режиме, о котором упоминается в упр. 4.21. Обработка поперечных ребер состоит в том, что они преобразу- преобразуются в прямые по лемме 5.14. Процесс преобразования поперечных ребер в прямые надо выполнять во время обработки прямых ребер. Каждому узлу v ставим в соответствие некоторое множество Civ] сос
Как сослаться (ГОСТ Р 7.0.5-2008)
- В списке литературы
- Хопкрофт Д., Ульман Дж., Ахо А. Построение и анализ вычислительных алгоритмов. — [Б. м.] : Мир, 1979.
- В тексте
- (Хопкрофт Д., Ульман Дж., Ахо А. Построение и анализ вычислительных алгоритмов. [Б. м.] : Мир, 1979)