Ich sitze gerade am 10. Blatt und in der zweiten Aufgabe wird die topologische Sortierung als bijektive Funktion der Knoten nach N definiert. Damit dürfte es für Graphen, die nicht abzählbar unendlich viele Knoten beinhalten, keine Sortierung geben. Soll tsort vielleicht nur eine Injektion sein?

(kleine Frage zur a: Hier reicht doch ein einfaches Gegenbeispiel? Aber dafür drei Punkte?)

Nein, die Definition ist einfach falsch, es muss nicht Abbildung V -> N sein, sondern natürlich V -> {1,...,|V|}.

Ich habe die Aufgabenblätter korrigiert und werde morgen vor der Vorlesung auf die Änderung hinweisen.

Danke für den Hinweis!

Zur 2a): Zur Verdeutlichung: Gemeint ist nicht "Zeigen Sie, daß es einen zyklischen Graphen gibt, für den keine topologische Sortierung existiert", sondern "Zeigen Sie, daß es keinen zyklischen Graphen gibt, für den eine topologische Sortierung existiert". Und das lässt sich nicht per Beispiel beweisen.

Grüße
Tobias Nopper

Grüße
Tobias Nopper
Lehrstuhl für Betriebssysteme

> Und das lässt sich nicht per Beispiel beweisen.
Das ist mit nach einer Diskussion mit meinem Tutor auch klar geworden. Ich hab mich da leider bei der negation der Aussage verrechnet.
Das Forum ist wirklich eine gute Hilfe.