Постдоминирование

Материал из WikiGrapp
Перейти к:навигация, поиск

Постдоминирование (Postdomination) — отношение между двумя вершинами \,v и \,w в управляющем графе \,G такое, что вершина \,v постдоминируется вершиной \,w, если каждый путь из \,v в выход графа содержит \,w. При этом вершина \,w называется постдоминатором (обязательным преемником) вершины \,v. Заметим, что иногда при определении постдоминирования начальная вершина пути исключается, т.е. считается, что вершина не постдоминирует сама себя.

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


См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Векторизация программ: теория, методы, реализация. — М.: Мир, 1991.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.