Topologische Sortierung

Einfache Sprache

Die Reihenfolge von Dingen bei der vorgegebene Abhängigkeiten erfüllt sind.

Graphen

Def. Topologische Sortierung in Graphen

Der Digraph $D=(V,E) mit $V={1,\ldots,n}$ besitzt eine **topologische Sortierung**, falls eine Anordnung der Knoten $(v_1,\ldots,v_n)$ existiert mit der Eigenschaft: $$\forall(v_i,v_j)\in E \text{ gilt }i

Sortierung in Graphen

Es gibt zumindest eine gültige topologische Sortierung, wenn die Beziehungen zyklusfrei sind, d.h., der Relationsgraph kreisfrei ist.