aufpannender gerichteter Weg im Turnier gesucht

16.12.2017, 20:30	FelNa1109	Auf diesen Beitrag antworten »
aufpannender gerichteter Weg im Turnier gesucht Hallo, ich bräuchte Hilfe bei folgender Aufgabe: Ein Turnier ist ein gerichteter Graph $\begin{eqnarray} T = (V,E) \end{eqnarray}$ , bei dem zwischen je zwei Knoten genau eine gerichtete Kante verläuft. Zeigen Sie, dass $\begin{eqnarray} T \end{eqnarray}$ einen aufspannenden gerichteten Weg enthält, d.h. einen gerichteten Weg, der alle Knoten aus $\begin{eqnarray} V \end{eqnarray}$ enthält. Meine Idee: Induktion über $\begin{eqnarray} n = \| V \| \end{eqnarray}$ IA: Sei $\begin{eqnarray} n=2: u,v\in V \end{eqnarray}$ und $\begin{eqnarray} T=(V,E) \end{eqnarray}$ ein Turniergraph. Nach der Definition des Turniergraphs ist entweder die Kante $\begin{eqnarray} (u,v) \end{eqnarray}$ oder $\begin{eqnarray} (v,u) \end{eqnarray}$ in $\begin{eqnarray} E \end{eqnarray}$ . $\begin{eqnarray} \Rightarrow \end{eqnarray}$ es existiert ein gerichteter Weg, der alle Knoten enthält. IV: Aussage sei für ein $\begin{eqnarray} n\in \mathbb N_{\geq 2} \end{eqnarray}$ bewiesen. IS: Sei $\begin{eqnarray} (v_1, ... , v_n) \end{eqnarray}$ ein gerichteter Weg und $\begin{eqnarray} u:=v_{n+1} \end{eqnarray}$ ein weiterer Knoten. Weiterhin sei $\begin{eqnarray} k \end{eqnarray}$ der kleinste Index, für den gilt: $\begin{eqnarray} \forall i: 1\leq i <k : u>v_i \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \end{eqnarray}$ $\begin{eqnarray} (v_1, ... , v_{k-1} , u , v_k, ... , v_n) \end{eqnarray}$ ist gerichteter Weg. Irgendwie bin ich damit nicht wirklich zufrieden, und ich glaube es man kann das besser zeigen (sollte meine Idee den überhaupt stimmen...). Als Tipp sollte ich einen maximalen gerichteten Weg betrachten.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »