imported>HilberTraum: so?

2018-11-19T19:15:27Z

so?

Neue Seite

[[Bild:Dominator control flow graph.svg|mini|Kontrollflussgraph <math>G\langle V,E,1\rangle</math>]]
[[Bild:Dominator tree.svg|mini|Dominator-Baum des Kontrollflussgraphen <math>G\langle V,E,1\rangle</math>]]
Die '''Dominanzrelation''' ist eine [[Relation (Mathematik)|Relation]], die auf den Knoten eines [[Kontrollflussgraph]]en 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 (Graphentheorie)|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 (Graphentheorie)|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]]

[[Kategorie:Graphentheorie]]

Dominanzrelation (Kontrollflussgraph) - Versionsgeschichte

imported>HilberTraum: so?