Toplogische Sortierung von Graphen

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Toplogische Sortierung von Graphen
Moin!

Im ziemlich übersichtlichen Skript kann ich nix zu topologischer Sortierung finden und die eine Übung, die wir dazu gemacht haben (8. Übung/20b) ist bei mir auch recht aufschlussreich, hat jemand nen Plan, wie die genaue Vorgehensweise ist, um einen Graphen topologisch zu sortieren?

Da WELL '3


zuerst das vorlesungs-beispiel (AFAIR, ich guck jetzt aber net nach):

um sich anzuziehen, sind verschiedene kleidungsstücke notwendig, die in einer gewissen reihenfolge anzuziehen sind, um normal auszusehen. weiterhin nimm an, dass der mensch am anfang nackert ist :wink: zuerst kommt die unterhose, danach das t-shirt, danach socken, danach hosen, ein hemd, krawatte, jacket, schuhe und zum schluß ein hut.

auffallend ist, dass es mehrere reihenfolge gibt, um sich korrekt anzuziehen. z.b. ob zuerst die hose und dann das hemd oder andersrum ist egal. diese reihenfolgen heissen topologische sortierungen. der graph darf dabei nicht zyklisch sein! er ist es aber eigentlich, denn ob ich nu zuerst das t-shirt oder die socken nach der unterhose anziehe, ist ja völlig wurscht! (im anhang ist eine topolische beispielsortierung)

oder anders (mathematischer?):
wenn für alle kanten (e, f) im graphen g wert(e) < wert (f) gilt, dann ist wert eine topologische sortierung. (also eine funktion, die jedem knoten einen stellenwert zuordnet - sozusagen eine zuordnung :wink: ).

Attachment:
ts.gif: https://fsi.cs.fau.de/unb-attachments/post_7258/ts.gif


das dahinterstehende abstrakte problem ist folgendes:

du hast n teilaufgaben zu erledigen. zusätzlich gibt es noch bedingungen derart, dass du bestimmte teilaufgaben n[sub]i[/sub] vor anderen aufgaben n[sub]j[/sub] durchführen musst.

zweites beispiel: kaffee kochen.
teilaufgaben: (1)filter einlegen, (2)filter mit kaffee füllen, (3)wasser in den tank geben, (4)anschalten
bedingungen: (1) vor (2), (1, 2, 3) vor (4)

warum funktionieren zyklische graphen nicht?
seien e, f zwei knoten und (e, f), (f, e) zwei kanten. wenn du die erste kante betrachtest, dann müsste wert(e) < wert(f) sein, damit wert eine topologische sortierung ist. die zweite kante allerdings fordert wert(f) < wert(e) => widerspruch.

anschaulich könntest du von e=henne und f=ei (problem) sprechen :gun:
henne schlüpft aus ei. das ei wird von einer henne gelegt => derselbe widerspruch. was kommt zuerst?

ich hoffe, dass meine erklärung wenigstens einigermassen richtig ist. :slight_smile:

ein guter kaffee hat zwei f und zwei e :smiley:


Cool, ich glaub, ich habs verstanden. In der einen Klausuraufgabe war nur ein Graph ohne “Kosten”, in der Übung haben wir auch so ne komplizierte Tabelle erstellt, wie man nen Graphen mit “Kosten” topologisch sortiert, aber anscheinend is das zu schwer für die Klausur, habs jedenfalls noch nirgendwo sonst gesehen.

Da WELL '3