Dominanzrelation (Kontrollflussgraph)

Die Dominanzrelation i​st eine Relation, d​ie auf d​en Knoten e​ines Kontrollflussgraphen definiert ist.

Kontrollflussgraph ${\displaystyle G\langle V,E,1\rangle }$

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

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

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

Im oben abgebildeten Kontrollflussgraph ${\displaystyle G\langle V,E,1\rangle }$ etwa dominiert Knoten 2 den Knoten 5, aber Knoten 3 dominiert Knoten 5 nicht, da es einen Pfad ${\displaystyle 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 ${\displaystyle u,v,w\in V}$ aus ${\displaystyle u\ dom\ v}$ und ${\displaystyle v\ dom\ w}$ folgt, dass ${\displaystyle u}$ den Knoten ${\displaystyle w}$ dominiert, ist die Dominanzrelation auch transitiv.

Wenn der Knoten ${\displaystyle u}$ den Knoten ${\displaystyle v}$ dominiert und ${\displaystyle u\neq v}$, dann spricht man auch davon, dass ${\displaystyle u}$ den Knoten ${\displaystyle v}$ strikt dominiert. Man schreibt dann auch ${\displaystyle 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