Benutzer:Sledge/Topologische Sortierung
aus Wikipedia, der freien Enzyklopädie
[Bearbeiten] Beweis des Satzes über azyklische Graphen und topologische Sortierungen
[Bearbeiten] Hilfssatz
Sei (V,E) ein endlicher, nicht leerer, azyklischer Digraph. Dann gilt:
D.h.: Es gibt ein Element m aus V, welches keinen Vorgänger hat.
Auf dieser wichtigen Eigenschaft basieren auch die diskutierten Algorithmen zum topologischen Sortieren. Einen wirklich griffigen Beweis bleibe ich z.Z. aber schuldig. Falls jemand einen guten Beweis an der Hand hat, möchte ich ihn ermutigen, diesen Artikel entsprechend zu erweitern.
[Bearbeiten] Satz
Sei M eine endliche Menge und . Dann sind äquivalent:
- (i) Es gibt eine topologische Sortierung T von M für R
- (ii) (M,R) ist ein azyklischer Digraph
Beweis: "(i) (ii)" Wähle eine topologische Sortierung T von M für R. Wegen ist (M,R) dann ein Digraph.
Es bleibt z.z.: (M,R) ist azyklisch.
Beweis durch Widerspruch: Angenommen (M,R) ist zyklisch.
Wähle einen Zyklus W von (M,R). Dann gibt es ein und mit und
Wähle solche n,v1,...,vn. Wegen (i) ist , also gilt auch:
T ist aber transitiv, und daher ist auch . Nun ist aber einerseits T irreflexiv und andererseits v1 = vn. Das ist ein Widerspruch, also muss (M,R) azyklisch sein.
- "(ii) (i)" Für den Fall, dass ist, ist offenbar eine topologische Sortierung von M für R. Sei also im weiteren .
Da M eine endliche Menge ist, gibt es ein mit | M | = n. Wähle so ein n.
Beweis durch vollständige Induktion über n:
- "n = 1" Gelte n = 1. Dann gibt es ein mit {m} = M. Wähle so ein m. Es ist nun . Wegen (ii) ist nun , da im Falle ein Zyklus von (M,R) wäre. Damit ist eine topologische Sortierung von M für R.
- "" Es ist z.z.: Falls die Aussage "(ii) (i)" für gilt, so gilt sie auch für n + 1.
Gelte also die Aussage "(ii) (i)" für und sei (M,R) ein azyklischer Digraph mit | M | = n + 1. Nach dem Hilfssatz gilt dann:
Wähle so ein m und setze . Dann ist (M',R') ein azyklischer Digraph (jeder Zyklus in (M',R') wäre auch ein Zyklus in (M,R)). Ferner ist | M' | = n. Nach der Induktionsvoraussetzung gibt es nun eine topologische Sortierung T' von M' für R'. Wähle so eine topologische Sortierung T' und betrachte .
Behauptung: T ist topologische Sortierung von M für R. (Beweis: folgt ein andermal)
Der Beweis wird so vielleicht nicht mehr fortgesetzt, da die zugrundegelegte Definition umstritten ist. --Sledge 23:02, 14. Aug 2004 (CEST)