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

'''Постдоминирование''' (''[[Postdomination]]'') -  

отношение между двумя [[вершина|вершинами]] <math>v</math> и <math>w</math> в [[управляющий граф|управляющем графе]] <math>G</math>

такое, что вершина <math>v</math> постдоминируется вершиной <math>w</math>, если каждый [[путь]]

из <math>v</math> в [[выход]] [[граф|графа]] содержит <math>w</math>. При

этом вершина <math>w</math> называется ''постдоминатором ([[обязательный преемник|обязательным

преемником]])'' вершины <math>v</math>.

Отношение постдоминирования изображается в виде [[корневое дерево|корневого]] [[ордерево|ордерева]], называемого ''постдоминаторным деревом '' (или

Его [[корень|корнем]] служит [[выход]] управляющего графа, а

[[дуга]] <math>(v,w)</math> существует в том и только том случае, когда <math>v</math>

есть непосредственный обязательный преемник (постдоминатор) вершины <math>w</math>.

==См. также ==

''[[Дерево доминаторов]]''.