Graphentheorie

Neue Frage »

Carlos Auf diesen Beitrag antworten »
Graphentheorie
Hi!

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 traurig


Vielen Dank schon mal im Voraus!
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.
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!
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..
Carlos Auf diesen Beitrag antworten »

Ok, darauf kann man wirklich kommen. Ich in dem Fall nicht, das schmerzt. Kotzen

Na ja, auf jeden Fall muchas gracias für deine Hilfe!! Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »