Dominator

Материал из WEGA
Версия от 16:52, 5 апреля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Dominator''' --- обязательный предшественник, доминатор. Given a ''cf-graph''<math>G</math> with the ''initial''vertex <math>…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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].