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

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

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

См. также

• Дерево доминаторов.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Векторизация программ: теория, методы, реализация. — М.: Мир, 1991.

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.