Dominanzrelation (Kontrollflussgraph)

Kontrollflussgraph $G⟨V,E,1⟩$

Dominator-Baum des Kontrollflussgraphen $G⟨V,E,1⟩$

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

Sei $G⟨V,E,r⟩$ 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 $udomv$.

Im oben abgebildeten Kontrollflussgraph $G⟨V,E,1⟩$ 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 $udomv$ und $vdomw$ 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 $ustdomv$. 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