Dominator

Материал из WEGA
Перейти к навигации Перейти к поиску

Dominator --- обязательный предшественник, доминатор.

Given a cf-graph[math]\displaystyle{ G }[/math] with the initialvertex [math]\displaystyle{ r }[/math] and two vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] in [math]\displaystyle{ G }[/math]. The vertex [math]\displaystyle{ x }[/math] is a dominator of the vertex [math]\displaystyle{ y }[/math] ([math]\displaystyle{ x }[/math] dominates [math]\displaystyle{ y }[/math]) if any path [math]\displaystyle{ P(r,y) }[/math] contains [math]\displaystyle{ x }[/math]; if [math]\displaystyle{ x \neq y }[/math] then [math]\displaystyle{ x }[/math] is a proper dominator of [math]\displaystyle{ y }[/math]. We denote as [math]\displaystyle{ DOM(x) }[/math] the set of all dominators of the vertex [math]\displaystyle{ x }[/math]. The vertex [math]\displaystyle{ x }[/math] is the immediate dominator of [math]\displaystyle{ y }[/math], denoted as [math]\displaystyle{ IDOM(y) }[/math], if [math]\displaystyle{ x }[/math] is a proper dominator of [math]\displaystyle{ y }[/math] and no vertex [math]\displaystyle{ z \not \in \{x,y\} }[/math] exists such that [math]\displaystyle{ x \in DOM(z) }[/math] and [math]\displaystyle{ z \in DOM(y) }[/math].