[Graphentheorie:] Pfad mit der länge des minimalsten Grades einer Ecke?!?

13.06.2005, 17:52	Asgaroth	Auf diesen Beitrag antworten »
[Graphentheorie:] Pfad mit der länge des minimalsten Grades einer Ecke?!? Hallo ihr. Ich bins mal wieder und hab wie immer keine Ahnung. 1. Sei $\begin{eqnarray} \delta(G)=\min_{e\in E}d(e) \end{eqnarray}$ der minimale Grad einer Ecke des Graphen G = (E,K). Zeige: G enthält einen Pfad (d.h. einen Weg, in dem keine Ecke mehr als einmal vorkommt) von mindestens der Länge $\begin{eqnarray} \delta(G) \end{eqnarray}$ (Hinweis: Betrachte einen maximalen Pfad.) Zeige ferner: Falls $\begin{eqnarray} \delta(G) \geq 2 \end{eqnarray}$ ist, gibt es einen Kreis von mindestens der Länge $\begin{eqnarray} \delta (G)+1 \end{eqnarray}$ . (Hinweis: Schließe den maximalen Pfad.) 2. Sei G ein Graph, in dem es Kreise gibt, und sei g(G) die kleinste Länge eines Kreises in G. Zeige: $\begin{eqnarray} 3 \le g(G) \le 2diam(G)+1 \end{eqnarray}$ (Hinweis: Teile einen Kreis in zwei Hälften.) P.S.: diam(G) ist so definiert: $\begin{eqnarray} diam(G)=\max_{a \in E}\max_{b\in E} d(a,b) \end{eqnarray}$ wobei $\begin{eqnarray} \max_{b\in E}d(a,b)= \end{eqnarray}$ der maximale Abstand zu einer Ecke b. Also zu Aufgabe 1: $\begin{eqnarray} \min_{e\in E}d(e) \end{eqnarray}$ ist doch bei einem zusammenhängenden Graphen mit mehr als einer Ecke doch 1 und in einem nicht zusammenhängenden Graphen 0 oder seh ich da irgendwas Falsch? Damit wäre ja das auch schon gezeigt, denn sobald es eine Kante gibt, also $\begin{eqnarray} d(e)=1 \end{eqnarray}$ gibt es auch einen Pfad mit der Länge 1. Wenn der Graph nicht zusammenhängend ist (oder nur eine Ecke hat) dann wäre $\begin{eqnarray} d(e)=0 \end{eqnarray*}$ und auch da "gibt" es einen Pfad mit der Länge 0... Oder sehe ich da jetzt irgendwas falsch? Wie man das andere zeigt weiß ich nicht wirklich... MfG Asgaroth P.S.: Schonmal danke im vorraus für Antworten.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »