Dominanzrelation (Kontrollflussgraph)

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\ne 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