Dominanzrelation (Kontrollflussgraph)

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.

Kontrollflussgraph

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:

Dominator-Baum des Kontrollflussgraphen

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kontrollflussgraph — Ein Kontrollflussgraph ist ein spezieller gerichteter Graph mit einem ausgezeichneten Wurzelknoten r. Er besteht somit aus einer Menge von Knoten V, aus einer Menge von gerichteten Kanten E und dem Wurzelknoten . Die Schreibweise lautet . Darüber …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”