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

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

См. также Дерево доминаторов.

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/88],

[Евстигнеев-Касьянов/94],

[Векторизация]