Benutzer:Sledge/Topologische Sortierung

Beweis des Satzes über azyklische Graphen und topologische Sortierungen

Hilfssatz

Sei $(V,E)$ ein endlicher, nicht leerer, azyklischer Digraph. Dann gilt:

$\exists m\in V\forall v\in V:(v,m)\notin E$

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.

Satz

Sei M eine endliche Menge und $R\subseteq M\times M$. Dann sind äquivalent:

(i) Es gibt eine topologische Sortierung T von M für R

(ii) (M,R) ist ein azyklischer Digraph

Beweis: "(i) $\Rightarrow$ (ii)" Wähle eine topologische Sortierung $T$ von $M$ für $R$. Wegen $R\subseteq M\times M$ 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 $n\in \mathbb {N}$ und $v_{1},...,v_{n}\in M$ mit $W=\lbrace v_{1},...,v_{n}\rbrace ,\ v_{1}=v_{n}$ und

$\forall i\in \lbrace 1,...,n-1\rbrace :(v_{i},v_{i+1})\in R$

Wähle solche $n,v_{1},...,v_{n}$. Wegen (i) ist $R\subseteq T$, also gilt auch:

$\forall i\in \lbrace 1,...,n-1\rbrace :(v_{i},v_{i+1})\in T$

$T$ ist aber transitiv, und daher ist auch $(v_{1},v_{n})\in T$. Nun ist aber einerseits $T$ irreflexiv und andererseits $v_{1}=v_{n}$. Das ist ein Widerspruch, also muss $(M,R)$ azyklisch sein.

"(ii) $\Rightarrow$ (i)" Für den Fall, dass $M=\emptyset$ ist, ist offenbar $\emptyset$ eine topologische Sortierung von $M$ für $R$. Sei also im weiteren $M\neq \emptyset$.

Da $M$ eine endliche Menge ist, gibt es ein $n\in \mathbb {N}$ mit $|M|=n$. Wähle so ein $n$.

Beweis durch vollständige Induktion über $n$:

"$n=1$" Gelte $n=1$. Dann gibt es ein $m\in M$ mit $\lbrace m\rbrace =M$. Wähle so ein $m$. Es ist nun $M\times M=\lbrace (m,m)\rbrace$. Wegen (ii) ist nun $R=\emptyset$, da im Falle $R=M\times M\ (m,m)$ ein Zyklus von $(M,R)$ wäre. Damit ist $\emptyset$ eine topologische Sortierung von $M$ für $R$.

"$n\Rightarrow n+1$" Es ist z.z.: Falls die Aussage "(ii) $\Rightarrow$ (i)" für $n\in \mathbb {N}$ gilt, so gilt sie auch für $n+1$.

Gelte also die Aussage "(ii) $\Rightarrow$ (i)" für $n\in \mathbb {N}$ und sei $(M,R)$ ein azyklischer Digraph mit $|M|=n+1$. Nach dem Hilfssatz gilt dann:

$\exists m\in M\forall v\in M:(v,m)\notin R$

Wähle so ein $m$ und setze $M':=M\setminus \lbrace m\rbrace ,\ R':=R\cap (M'\times M')$. 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 $T:=T'\cup (\lbrace m\rbrace \times M')$.

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)