- Dominanzrelation (Kontrollflussgraph)
-
Die Dominanzrelation ist eine Relation, die auf den Knoten eines Kontrollflussgraphen definiert ist.
Sei ein Kontrollflussgraph und seien 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 .
Im oben abgebildeten Kontrollflussgraph etwa dominiert Knoten 2 den Knoten 5, aber Knoten 3 dominiert Knoten 5 nicht, da es einen Pfad gibt, der den Knoten 3 nicht beinhaltet.
Klarerweise dominiert jeder Knoten sich selbst. Daher ist die Dominanzrelation reflexiv.
Da außerdem für aus und folgt, dass u den Knoten w dominiert, ist die Dominanzrelation auch transitiv.
Wenn der Knoten u den Knoten v dominiert und , dann spricht man auch davon, dass u den Knoten v strikt dominiert. Man schreibt dann auch . 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
Wikimedia Foundation.