Graphentheorie |
06.12.2005, 14:57 | Carlos | Auf diesen Beitrag antworten » |
Graphentheorie Es wäre klasse, wenn mir jemand eine Anregung für den Beweis dieses einfachen Satze geben könnte: Falls zwei Knoten v,w in einem Graphen G durch einen Weg verbunden sind, dann exisitiert auch ein Pfad, der v und w verbindet. Mir ist klar, dass es so ist, aber ich finde keinen Ansatz für den Beweis Vielen Dank schon mal im Voraus! |
||
06.12.2005, 19:57 | irre.flexiv | Auf diesen Beitrag antworten » |
Hier bietet es sich an eine schärfere Aussage zu beweisen aus der dann dein Satz folgt. Endliche Graphen: Wenn es einen Weg gibt, gibt es auch einen kürzesten Weg. Jeder kürzeste Weg muss aber ein Pfad sein. Unendliche Graphen: Da bin ich mir nicht ganz sicher. |
||
07.12.2005, 19:18 | z00m | Auf diesen Beitrag antworten » |
hat vielleicht noch jemand einen anderen ansatz. Denn Wikipedia sagt dazu nur: Den Knoten v1 nennt man Startknoten von W und den Knoten vn Endknoten von W. Ferner bezeichnet man W statt als Weg, spezieller als * Pfad, falls alle Knoten in der Folge W voneinander verschieden sind, das heißt falls für alle i und j aus {1,...,n} gilt, dass vi`vj, falls i`j. Aber das reicht doch nicht als Beweis! |
||
08.12.2005, 00:36 | irre.flexiv | Auf diesen Beitrag antworten » |
So schwer ist es doch nicht. Angenommen du läufst den Weg entlang und kommst an einen Punkt an dem du schonmal warst, dann bist du einen Kreis abgelaufen. Du weißt das du zu diesem Punkt kommst ohne diesen Kreis abzulaufen, denn du warst ja schonmal da. Andererseits weißt du auch das du von diesem Punkt aus zum Ziel kommst, denn du bist immernoch auf dem Weg.. |
||
08.12.2005, 01:50 | Carlos | Auf diesen Beitrag antworten » |
Ok, darauf kann man wirklich kommen. Ich in dem Fall nicht, das schmerzt. Na ja, auf jeden Fall muchas gracias für deine Hilfe!! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|