Dominanzrelation (Kontrollflussgraph)
Die Dominanzrelation ist eine Relation, die auf den Knoten eines Kontrollflussgraphen definiert ist.
Sei <math>G\langle V,E,r\rangle</math> ein Kontrollflussgraph und seien <math>u,v\in V</math> zwei seiner Knoten.
Wenn nun jeder Pfad in <math>G</math>, der in <math>r</math> beginnt und in <math>v</math> endet, den Knoten <math>u</math> beinhaltet, so sagt man, dass der Knoten <math>u</math> den Knoten <math>v</math> dominiert. Man schreibt auch <math>u\ dom\ v</math>.
Im oben abgebildeten Kontrollflussgraph <math>G\langle V,E,1\rangle</math> etwa dominiert Knoten 2 den Knoten 5, aber Knoten 3 dominiert Knoten 5 nicht, da es einen Pfad <math>1\to 2\to 4\to 5</math> gibt, der den Knoten 3 nicht beinhaltet.
Klarerweise dominiert jeder Knoten sich selbst. Daher ist die Dominanzrelation reflexiv.
Da außerdem für <math>u,v,w\in V</math> aus <math>u\ dom\ v</math> und <math>v\ dom\ w</math> folgt, dass <math>u</math> den Knoten <math>w</math> dominiert, ist die Dominanzrelation auch transitiv.
Wenn der Knoten <math>u</math> den Knoten <math>v</math> dominiert und <math>u\ne v</math>, dann spricht man auch davon, dass <math>u</math> den Knoten <math>v</math> strikt dominiert. Man schreibt dann auch <math>u\ stdom\ v</math>. 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: