Das Kefk Network Wiki befindet sich im Testbetrieb.

Dominanzrelation (Kontrollflussgraph)

Aus Kefk.

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$ .

Bild:Domrel.png

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:

Bild:Domtree.png

Siehe auch

Reduzierbarer und irreduzierbarer Kontrollflussgraph

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Dominanzrelation_%28Kontrollflussgraph%29, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.

Von „http://www.kefk.org/wiki/Dominanzrelation_%28Kontrollflussgraph%29“

Kategorien: Graphentheorie | Wikipedia