Dominanzrelation (Kontrollflussgraph)

Kontrollflussgraph $G\langle V,E,1\rangle$

Dominator-Baum des Kontrollflussgraphen $G\langle V,E,1\rangle$

Die Dominanzrelation ist eine Relation, die auf den Knoten eines Kontrollflussgraphen definiert ist.

Sei $G\langle V,E,r\rangle$ ein Kontrollflussgraph und seien $u,v\in V$ zwei seiner Knoten.

Wenn nun jeder Pfad in $G$, der in $r$ beginnt und in $v$ endet, den Knoten $u$ beinhaltet, so sagt man, dass der Knoten $u$ den Knoten $v$ dominiert. Man schreibt auch $u\ dom\ v$.

Im oben abgebildeten Kontrollflussgraph $G\langle V,E,1\rangle$ etwa dominiert Knoten 2 den Knoten 5, aber Knoten 3 dominiert Knoten 5 nicht, da es einen Pfad $1\to 2\to 4\to 5$ gibt, der den Knoten 3 nicht beinhaltet.

Klarerweise dominiert jeder Knoten sich selbst. Daher ist die Dominanzrelation reflexiv.

Da außerdem für $u,v,w\in V$ aus $u\ dom\ v$ und $v\ dom\ w$ folgt, dass $u$ den Knoten $w$ dominiert, ist die Dominanzrelation auch transitiv.

Wenn der Knoten $u$ den Knoten $v$ dominiert und $u\neq v$, dann spricht man auch davon, dass $u$ den Knoten $v$ strikt dominiert. Man schreibt dann auch $u\ stdom\ v$. Die strikte Dominanzrelation kann als Baum dargestellt werden. Dieser Baum wird auch Dominator-Baum (engl. dominator tree) genannt. Der obige Beispielgraph besitzt folgenden Dominator-Baum:

Siehe auch

• Reduzierbarer und irreduzierbarer Kontrollflussgraph