www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Frage zum Beweis
Frage zum Beweis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Frage zum Beweis: Längste Wege
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 16:32 So 05.02.2017
Autor: pc_doctor

Aufgabe
Beweise, dass in einem zusammenhängenden ungerichteten Graphen G je zwei längste Wege einen gemeinsamen Knoten haben.

Hallo,

ich habe eine Frage zu dem Beweis:

Der sieht folgendermaßen aus: Angenommen, seien { [mm] v_0,v_1,...,v_n [/mm] } und { [mm] w_0,w_1,...,w_n [/mm] } die disjunkten Knotenmengen von zwei längsten Wegen q und r der Länge n in G mit [mm] d_G(v_0,v_i) [/mm] = [mm] d_G(w_0,w_i) [/mm] = i für alle 0 [mm] \le [/mm] i [mm] \le [/mm] n. Da G zusammenhängend ist, gibt es Knoten [mm] v_l [/mm] und [mm] w_k [/mm] auf beiden Wegen, die durch einen Weg p verbunden sind. O.B.d.A liegen außer [mm] v_l [/mm] und [mm] w_k [/mm] keine anderen Knoten von q bzw. r auf p. p hat Länge [mm] \ge [/mm] 1 wegen [mm] v_l \not= w_k. [/mm] Wir betrachten die 4 Wege von [mm] v_0 [/mm] bzw. [mm] v_n [/mm] über [mm] v_l, w_k [/mm] nach [mm] w_0 [/mm] bzw. [mm] w_n [/mm] Die Summe ihrer Längen ist [mm] \ge [/mm] 4n+4. Damit gibt es einen Weg der Länge > n. Widerspruch.

Ich verstehe alles bis auf den fett markierten Satz. Wieso gibt es jetzt 4 Wege? Wie kommt man auf die 4 Wege ?

Vielen Dank im Voraus.

        
Bezug
Frage zum Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 21:44 Di 07.02.2017
Autor: HJKweseleit

Vereinfacht sieht die Situation folgendermaßen aus:


[mm] V_0 --------------v_i---------------------v_n [/mm]
                      /
                     /
                    /p
                    |
                    |
[mm] w_0------------w_i-----------------------w_n [/mm]


Die 4 betrachteten Wege sind dann

[mm] v_0-v_i-w_i-w_n [/mm]

[mm] v_0-v_i-w_i-w_0 [/mm]

[mm] v_n-v_i-w_i-w_n [/mm]

[mm] v_n-v_i-w_i-w_0. [/mm]
                    

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]