Topologische Sortierung

Topologische Sortierung bezeichnet in der Mathematik eine Reihenfolge von Dingen, bei der vorgegebene Abhängigkeiten erfüllt sind.

Anstehende Tätigkeiten einer Person etwa unterliegen einer Halbordnung: es existieren Bedingungen wie „Tätigkeit A muss vor Tätigkeit B erledigt werden“. Eine Reihenfolge, welche alle Bedingungen erfüllt, nennt man topologische Sortierung der Menge anstehender Tätigkeiten. Im Gegensatz zur Sortierung einer Totalordnung ist die Reihenfolge nicht eindeutig, sondern es kann mehrere Möglichkeiten geben. Wenn gegenseitige Abhängigkeiten bestehen, ist eine topologische Sortierung unmöglich.

Aus mengentheoretischer Sicht handelt es sich bei der topologischen Sortierung um eine lineare Erweiterung einer partiellen Ordnung. 1930 zeigte Edward Szpilrajn, dass aus dem Auswahlaxiom folgt, dass sich jede partielle Ordnung zu einer linearen Ordnung erweitern lässt.

Die topologische Sortierung für endliche Mengen (hier wird das Auswahlaxiom nicht gebraucht) ist bei vielen Anwendungen der Informatik ein wichtiges Konzept. Bereits 1961 wurde von Daniel J. Lasser ein Algorithmus entwickelt, mit dem eine topologische Sortierung ganz allgemein erstellt werden kann. Zuvor waren allerdings schon Algorithmen für spezielle Anwendungen bekannt.

Des Weiteren spielt die topologische Sortierung in der Graphentheorie bei der Untersuchung von gerichteten Graphen auf Zyklenfreiheit eine große Rolle.

Das Problem Verschiedene Objekte können nach messbaren Größen, zum Beispiel Städte nach Einwohnerzahlen, Schuhe nach Schuhgrößen, aber auch alphabetisch nach Namen eindeutig sortiert werden. Oft gelingt dies jedoch nicht mehr, wenn nur Beziehungen der Form Vorgänger/Nachfolger angegeben werden und solche Beziehungen nicht für jedes Paar von Objekten vorhanden sind. Gegenseitige Abhängigkeiten können darüber hinaus eine Sortierung unmöglich machen (etwa beim Schachspiel: Anton gewinnt gegen Bernd, Bernd gewinnt gegen Clemens und Clemens gewinnt gegen Anton). Gelingt es, die Objekte in eine Reihenfolge zu bringen, bei der Vorgänger stets vor Nachfolgern auftreten, so ist diese Reihenfolge eine topologische Sortierung der Objekte.

Je nach Art der Beziehungen kann es keine, nur eine oder mehrere verschiedene topologische Sortierungen geben. Wenn gegenseitige (zyklische) Abhängigkeiten bestehen, ist eine topologische Sortierung nicht möglich. In der Tat ist ein Anwendungsgebiet der topologischen Sortierung die Überprüfung, ob zyklische Abhängigkeiten bestehen.

Beispiel: Anziehreihenfolge von Kleidungsstücken Beim Anziehen von Kleidungsstücken müssen manche Teile unbedingt vor anderen angezogen werden. So muss ein Pullover vor einem Mantel angezogen werden. Hat man zum Beispiel eine Hose, ein Unterhemd, Pullover, Mantel, Socken, eine Unterhose und ein Paar Schuhe, so kann man die folgenden Beziehungen für das Anziehen angeben.

Das Unterhemd vor dem Pullover Die Unterhose vor der Hose Den Pullover vor dem Mantel Die Hose vor dem Mantel Die Hose vor den Schuhen Die Socken vor den Schuhen

Um eine sinnvolle Reihenfolge zu bestimmen, können die sieben Kleidungsstücke topologisch sortiert werden, also etwa Erst die Unterhose, dann die Socken, Hose, Unterhemd, Pullover, Mantel, Schuhe.

Aber auch Erst das Unterhemd, dann die Unterhose, dann Pullover, Socken, Hose, Schuhe, Mantel.

Jedoch nicht Erst den Pullover, da das Unterhemd vorher angezogen werden muss.

Mathematische Beschreibung des Problems

Die zu sortierende Menge Die zu sortierenden Objekte müssen bezüglich der Beziehung teilweise angeordnet werden können, damit sie topologisch sortierbar sind. Mathematisch bilden die Objekte die Elemente einer Menge , die bezüglich einer Relation (Beziehung) die folgenden Eigenschaften hat:

Für jeweils beliebige Elemente der Menge und der Relation gilt: Irreflexivität: ( steht nicht mit in Relation) Transitivität: Wenn und , dann gilt .

Übersetzt heißt dies: Ich kann die Hose nicht vor der Hose anziehen. Wenn ich das Unterhemd vor dem Pullover anziehen muss und den Pullover vor dem Mantel, so folgt daraus, dass ich das Unterhemd vor dem Mantel anziehen muss.

Die Menge bildet dann bezüglich der Relation eine strenge Halbordnung. Oft schreibt man statt auch einfach , weil die Relation ähnliche Eigenschaften hat wie die Kleiner-Relation für Zahlen. (Allerdings hat die Kleiner-Relation noch einige weitere Eigenschaften, die man hier nicht unbedingt hat. So kann man bei der Kleiner-Relation von zwei verschiedenen Zahlen immer entscheiden, welche der beiden kleiner ist. Hier ist dies nicht verlangt. Im Beispiel wäre dies der Vergleich von Socken und Unterhemd: Man kann nicht sagen, dass eines davon zuerst angezogen werden muss.)

Üblicherweise wird jedoch nicht die ganze Relation angegeben, sondern nur eine ausreichende Teilmenge von direkten Vorgänger-Nachfolger-Paaren. Die Relation ist dann über den transitiven Abschluss der durch die übergebenen Paare definierten Relation gegeben. Beispielsweise besagt die komplette Relation für das Beispielproblem auch, dass das Unterhemd vor dem Mantel angezogen werden muss (wegen „Unterhemd vor Pullover“ und „Pullover vor Mantel“ folgt aus der Transitivität auch „Unterhemd vor Mantel“). Der transitive Abschluss besteht nun darin, diese Paare der Relation hinzuzufügen. Bei der Implementierung eines entsprechenden Sortieralgorithmus wird allerdings die vollständige Relation nicht explizit generiert.

Die topologisch sortierte Menge Eine bestimmte Reihenfolge hingegen wird mathematisch durch eine strenge Totalordnung definiert: Für je zwei verschiedene Elemente aus ist festgelegt, ob vor oder vor kommt (Es steht z. B. fest, ob ich heute Morgen zuerst die Unterhose oder zuerst das Unterhemd angezogen habe). Die strenge Totalordnung ist also mathematisch definiert durch das zusätzliche Axiom der

Trichotomie: Für beliebige Elemente aus gilt entweder oder oder .

Die Aufgabe des topologischen Sortierens ist nun, zu einer gegebenen strengen Halbordnung eine Totalordnung zu finden, so dass für alle mit auch gilt .

Definition der topologischen Sortierung Motiviert durch die Untersuchungen der beiden vorhergehenden Abschnitte kann man nun den mathematischen Begriff einer topologischen Sortierung einführen:

Sei eine Menge und . Eine Menge heißt genau dann eine topologische Sortierung von für , wenn eine strenge Totalordnung auf ist und gilt.

Diese Definition beschränkt den Begriff einer topologischen Sortierung ausdrücklich nicht auf endliche Mengen, obwohl im Zusammenhang mit einer algorithmischen Untersuchung eine solche Beschränkung sinnvoll ist.

Azyklische Graphen und topologische Sortierungen Den bereits erwähnten Zusammenhang von topologischen Sortierungen und azyklischen Graphen kann man in folgendem Satz zusammenfassen:

Sei eine Menge und . Dann sind äquivalent:

Es gibt eine topologische Sortierung von für ist ein azyklischer Digraph

Darstellung als gerichteter Graph Stellt man eine Beziehung als Pfeil zwischen zwei Elementen dar, entsteht ein gerichteter Graph. Ein solcher gerichteter Graph besitzt eine topologische Sortierung genau dann, wenn er azyklisch ist, es also keine geschlossene Kantenrundreise gibt.

Datei:Kleidergraph.png

Die Kleidungsstücke kann man topologisch sortieren, indem man sie linear anordnet und darauf achtet, dass alle Pfeile nur von links nach rechts weisen:

Datei:Kleidergraphsortiert.png

So erhält man eine weitere Charakterisierung einer topologischen Sortierung, die auch als Definition verwendet werden kann. Zu einem gerichteten Graphen , mit Knoten- und Kantenmenge , ist demnach eine topologische Sortierung eine bijektive Abbildung, die heiße, von den Knoten in eine Teilmenge der natürlichen Zahlen (mit anderen Worten eine Eins-zu-eins-Identifikation: Jeder Knoten bekommt genau eine Zahl). Dabei soll gelten, dass für jede Kante erfüllt ist.

Im Beispiel hätte man die Abbildung

Solche Abbildungen sind niemals eindeutig. Erhöht man den Bildwert knotenweise um eine beliebige Konstante, erhält man eine weitere Sortierung mit . Beschränkt man sich auf Abbildungen in eine elementweise kleinste Teilmenge natürlicher Zahlen, hängt die Eindeutigkeit von der Graphenstruktur ab. Gerichtete Pfade sind dann eindeutig sortierbar, „echte“ gerichtete Bäume können mehrere Sortierungen haben.

Sortierbare Graphen mini|250px|ohne|Graph 1

Graph 1 ist topologisch sortierbar. Es existieren mehrere Lösungen (zum Beispiel A B C G D E F). Dabei spielt es keine Rolle, dass mehrere Elemente ohne Vorgänger existieren (A und G), dass manche Elemente mehrere Nachfolger haben (B hat zum Beispiel drei Nachfolger) und manche mehrere Vorgänger (D und E).

mini|124px|ohne|Graph 2

Graph 2 ist ebenfalls topologisch sortierbar (zum Beispiel A C B D E), obwohl er nicht zusammenhängend ist.

Alle gerichteten Graphen, die keine Zyklen enthalten, sind topologisch sortierbar.

Nicht sortierbare Graphen

Graph 3 ist nicht topologisch sortierbar, da er einen Zyklus, also eine gegenseitige Abhängigkeit enthält (Elemente B, C, E und D).

Auch wenn wie in Graph 4 nur zwei Elemente gegenseitig voneinander abhängen, ist eine topologische Sortierung unmöglich. Allgemein sind genau alle Graphen, die einen Kreis enthalten, nicht topologisch sortierbar. Topologische Sortierbarkeit ist logisch gleichwertig zur Azyklizität.

Graph 5 hat auch keine topologische Sortierung, nicht aber weil er einen „Kreis“ enthält, sondern weil er gegen die geforderte Irreflexivität verstößt. Knoten A steht mit sich selbst in Relation. Graph 5 ist also ein minimaler nicht topologisch sortierbarer Graph.

Algorithmus

Entfernung von Elementen ohne Vorgänger Der Algorithmus geht von einem gerichteten Graphen aus. Er entfernt solange Elemente ohne Vorgänger aus dem Graphen, bis keine Elemente mehr übrig sind.

Zunächst werden alle Elemente mit der Vorgängerzahl, also der Anzahl von Pfeilspitzen, die zum jeweiligen Element führen, versehen:

Graph mit Vorgängerzahlen

Elemente mit Vorgängerzahl 0 (blau markiert) haben keine anderen Vorgänger. Sie werden aus dem Graph entfernt. Hier können also die Socken, die Unterhose und das Unterhemd mit den zugehörigen Pfeilen entfernt werden. Dadurch ändern sich auch die Vorgängerzahlen von anderen Elementen:

Graph mit Vorgängerzahlen, Nullelemente blau markiert

Entfernte Elemente: Socken Unterhose Unterhemd

Jetzt haben der Pullover und die Hose keine Vorgänger mehr, sie können also entfernt werden:

Graph mit Vorgängerzahlen, Nullelemente blau markiert

Entfernte Elemente: Socken Unterhose Unterhemd Hose Pullover

Nun bleiben nur noch Mantel und Schuhe übrig, die ebenfalls entfernt werden. Die Topologische Sortierung ist fertig, wenn alle Elemente entfernt werden konnten:

Topologische Sortierung: Socken Unterhose Unterhemd Hose Pullover Mantel Schuhe

Repräsentation im Rechner Die Objekte (Elemente) selbst werden normalerweise in die

Datenstruktur einer Liste mit Objektattributen (Name, Index, …) eingetragen. Um die Beziehungen darzustellen, genügt für jedes Element jeweils eine zusätzliche Liste mit Verweisen (Referenzen oder Zeiger) auf die Nachfolger eines Objekts. Die Objekte enthalten einen Verweis auf ihre jeweilige Nachfolgerliste.

Für den Sortieralgorithmus wird Platz für weitere Daten benötigt, die vom Algorithmus beschrieben und verwendet werden:

Für jedes Objekt Platz für eine Zahl, die die Anzahl der Vorgänger aufnimmt. Optional eine Hilfsliste, die Objekte ohne Vorgänger aufnimmt.

Beispiel:

Für das Ankleidebeispiel weiter oben sähe die Objektliste z. B. folgendermaßen aus:

Hose Mantel Pullover Schuhe Socken Unterhemd Unterhose

Die Nachfolgerlisten sähen dann folgendermaßen aus:

2, 4 (leere Liste) 2 (leere Liste) 4 3 1