[Graphentheorie] - Abschätzung eines längsten Pfades in einem Baum

28.11.2011, 13:09

wdposchmann

[Graphentheorie] - Abschätzung eines längsten Pfades in einem Baum

Hallo zusammen,

ich sitze vor folgender Aufgabe der Graphentheorie:

Zitat:

Sei T = (V,E) ein Baum, in welchem kein Knoten Grad 2 hat. Zeigen Sie, dass für die Anzahl d von Kanten eines längsten Pfades in T die Abschätzung $\begin{eqnarray*} d \leq \frac{|V|}{2} \end{eqnarray*}$ gilt. (|V| ist die Anzahl der Knoten in diesem Baum)

Also ich weiss (das dürfen wir auch verwenden), dass ein Baum genau |V|-1 Kanten hat. Wären also auch Knoten vom Grad 2 erlaubt, so könnte der längste Pfad des Baumes so lang sein, es würde also $\begin{eqnarray*} d \leq |V|-1 \end{eqnarray*}$ gelten.

Nur wie komme ich jetzt auf die gesuchte Abschätzung. Ich habe versucht, dass in Worten zu formulieren (denn wenn man beginnt es sich aufzuzeichnen, kann man es ja folgern) aber ich denke um es zu zeigen, sollte schon ein formaler Beweis dort stehen.

Kann mir da jemand weiterhelfen bzw. einen Tipp geben, wie ich diesen Beweis beginne?

Vielen Dank schon mal!

Viele Grüße

28.11.2011, 18:28

Abakus

Auf diesen Beitrag antworten »

RE: [Graphentheorie] - Abschätzung eines längsten Pfades in einem Baum
Hallo,

vielleicht ja Induktion?

Abakus smile

28.11.2011, 19:30

wdposchmann

Auf diesen Beitrag antworten »

RE: [Graphentheorie] - Abschätzung eines längsten Pfades in einem Baum
Danke für deine Antwort. Hab es jetzt mal per Induktion nach d versucht:

Induktionsanfang: d=1

Dann besteht der Graph T aus mindestens 2 Knoten (beide sind vom Grad 1, also hat keiner Grad 2). Somit gilt 1=1. Also stimmt die Aussage für d=1.

Induktionsvoraussetzung: $\begin{eqnarray*} d \leq \frac{|V|}{2} \end{eqnarray*}$ für $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ .

Induktionsschritt: d -> d+1

Vorüberlegung: Wenn d um 1 wächst, so muss |V| um mindestens 2 wachsen. Denn würde man nur einen neuen Knoten und somit eine neue Kante hinzufügen, so hätte der ursprünglich letzte Knoten des Pfades Grad 2 (davon gehe ich deswegen aus, da der Anfangs- als auch Endknoten eines längsten Pfades Blätter dieses Baums sind, also Knoten vom Grad 1).

$\begin{eqnarray*} d+1 \leq \frac{|V|+2}{2} \end{eqnarray*}$

$\begin{eqnarray*} \longleftrightarrow d+1 \leq \frac{|V|}{2}+1 \end{eqnarray*}$

$\begin{eqnarray*} (IV)\longleftrightarrow d+1 \leq d+1 \end{eqnarray*}$

Was ja stimmt. Die Frage ist nur, darf ich im letzten Schritt |V|/2 wirklich einfach so durch d ersetzen? Denn es ist ja eine Ungleichung, keine Gleichung?

(Die Pfeile sollen natürlich Äquivalenzpfeile sein, in Latex werden sie auch so dargestellt, hier nicht)

Wäre nett, wenn du/ihr mal drüber schaut, ob das so passt.

Viele Grüße

29.11.2011, 20:32

Abakus

Auf diesen Beitrag antworten »

RE: [Graphentheorie] - Abschätzung eines längsten Pfades in einem Baum
Ich hatte an eine Induktion über die Anzahl der Knoten gedacht. Aber so geht es auch.

Was die Sache schwierig macht, ist dass die Graphen mit längstem Weg d vermutlich eine Klasse bilden (keine Menge) und du musst es zB im IA für alle diese Graphen verifizieren. Du nimmst hier nur einen Graph T, obwohl das eine ganze Klasse ist.

Abakus smile

Neue Frage »

Antworten »

[Graphentheorie] - Abschätzung eines längsten Pfades in einem Baum

Verwandte Themen