Beweis - zusammenhäng. Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:55 Mi 19.12.2007 | | Autor: | Kar_o |
| Aufgabe | | Sei G ein zusammenhängender Graph. Zegen Sie, dass zwei Pfade maximaler Länge in G mindestens einen gemeinsamen Knoten haben. |
Kann mir jemand Starthilfe leisten?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:18 Do 20.12.2007 | | Autor: | Zneques |
Hallo,
angenommen du hast zwei Pfade mit der maximalen Länge, die keine gemeisamen Knoten besitzen. Dann kannst du mit der Verbindung eines Knoten des ersten Pfades mit einen des zweiten Pfades (gibt es da zusammenhängend) einen längeren Pfad konstruieren. Damit ist die Annahme falsch.
Ciao.
|
|
|
|
