Постдоминирование: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Постдоминирование''' (''Postdomination'') - отношение между двумя вершинами <math>v</math...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Постдоминирование''' (''Postdomination'') -
'''Постдоминирование''' (''[[Postdomination]]'')
отношение между двумя вершинами <math>v</math> и <math>w</math> в управляющем графе <math>G</math>
отношение между двумя [[вершина|вершинами]] <math>\,v</math> и <math>\,w</math> в [[управляющий граф|управляющем графе]] <math>\,G</math>
такое, что вершина <math>v</math> постдоминируется вершиной <math>w</math>, если каждый путь
такое, что вершина <math>\,v</math> постдоминируется вершиной <math>\,w</math>, если каждый [[путь]]
из <math>v</math> в выход графа содержит <math>w</math>. При
из <math>\,v</math> в [[выход]] [[граф|графа]] содержит <math>\,w.</math> При
этом вершина <math>w</math> называется ''постдоминатором (обязательным
этом вершина <math>\,w</math> называется ''постдоминатором ([[обязательный преемник|обязательным
преемником'') вершины <math>v</math>.
преемником]])'' вершины <math>\,v</math>.
Заметим, что иногда при определении постдоминирования
Заметим, что иногда при определении постдоминирования
начальная вершина пути исключается, т.е. считается, что
начальная вершина пути исключается, т.е. считается, что
вершина не постдоминирует сама себя.
вершина не постдоминирует сама себя.


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




См. также ''Дерево доминаторов''.
==См. также ==
* ''[[Дерево доминаторов]]''.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.


[Касьянов/88],
* Векторизация программ: теория, методы, реализация. — М.: Мир, 1991.


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


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

Текущая версия от 11:27, 22 июня 2011

Постдоминирование (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.