Halbordnung in einem Wurzelbaum zeigen

11.10.2015, 19:22	quosego	Auf diesen Beitrag antworten »
Halbordnung in einem Wurzelbaum zeigen Meine Frage: Hallo Community ! Ich habe folgende Aufgabe: Sei $\begin{eqnarray} T=(V,E) \end{eqnarray}$ ein Baum mit der Wurzel $\begin{eqnarray} r \end{eqnarray}$ . z.z: $\begin{eqnarray} $\leq_r$ \end{eqnarray}$ ist eine Halbordnung auf $\begin{eqnarray} T \end{eqnarray}$ . Meine Ideen: Eine Halbordnung muss ja reflexiv, transitiv und antisymmetrisch sein, d.h. ich muss diese 3 Eigenschaften von $\begin{eqnarray} \leq_r \end{eqnarray}$ zeigen: reflexiv: $\begin{eqnarray} x \leq_r x \end{eqnarray}$ . $\begin{eqnarray} x \end{eqnarray}$ liegt immer auf dem Weg $\begin{eqnarray} (r,x) \end{eqnarray}$ . transitiv: $\begin{eqnarray} x \leq_r y \land y \leq_r z \Rightarrow x \leq_r z \end{eqnarray}$ . Wenn $\begin{eqnarray} x \end{eqnarray}$ auf dem Weg $\begin{eqnarray} (r,y) \end{eqnarray}$ und $\begin{eqnarray} y \end{eqnarray}$ auf dem Weg $\begin{eqnarray} (r,z) \end{eqnarray}$ liegt, muss gelten: $\begin{eqnarray} x \in (r,z) \end{eqnarray}$ , da es nur einen Weg zwischen zwei Knoten in einem Wurzelbaum gibt. Was die Antisymmetrie angeht, da habe ich kein Plan wie ich $\begin{eqnarray} x \leq_r y \land y \leq_r x \Rightarrow x=y \end{eqnarray}$ zeigen soll.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »