Frage zum Beweis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | 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.
|
|
| |
|
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]
|
|
|
|
