graphentheorie - pfade

Neue Frage »

mussNochVielLernen Auf diesen Beitrag antworten »
graphentheorie - pfade
Meine Frage:
hallo leute,
ich sitze hier vor einer aufgabe, bei der mir der rote pfaden der beweisführung fehlt.
die aufgabe lautet folgendermaßen: "Zeigen Sie: Enthalt ein Graph G einen (u, v)-Pfad und einen (v,w)-Pfad, so enthalt G auch einen (u,w)-Pfad."
danke!


Meine Ideen:
ersteinmal die definition eines pfades:"Ein Pfad ist eine Folge von Knoten, mit paarweise verschiedenen Knoten.
das war's dann aber leider schon..
Mystic Auf diesen Beitrag antworten »
RE: graphentheorie - pfade
Hm, und was wäre, wenn du die beiden Pfade einfach aneinander hängst? verwirrt

Natürlich müsste man im Falle dass dadurch Knoten mehrfach auftreten, das anschließend noch "in Ordnung bringen"...
mussNochVielLernen Auf diesen Beitrag antworten »
RE: graphentheorie - pfade
hallo, ersteinmal vielen dank für deine idee.
dein vorschlag des aneinanderlegens/aneinanderhängens ist
ebenso simpel wie genial.
ein jammer, dass ich nicht darauf gekommen bin.
das mehrfachauftreten eines knotens bereitet mir noch verständnisprobleme.
bei konstruktion eines neuen pfades (u, w) [anfangspunkt u; über v; endpunkt w] würde doch kein weg mehrfach durchlaufen werden.

oder darf es keine (ich nenn sie mal teilpfade/unterpfade) geben?
tut mir leid, dass ich so schwer von begriff bin...
Math1986 Auf diesen Beitrag antworten »
RE: graphentheorie - pfade
Zitat:
Original von mussNochVielLernen
bei konstruktion eines neuen pfades (u, w) [anfangspunkt u; über v; endpunkt w] würde doch kein weg mehrfach durchlaufen werden.
Das kann passieren. Es können bspw beide Pfade über den selben Knoten x gehen. Das musst du noch irgendwie berücksichtigen.
mussNochVielLernen Auf diesen Beitrag antworten »

tut mir leid jungs, ich steh total auf dem schlauch.
im fall, dass die pfade uv und vw beide durch den knoten x gehen,
müsste man dann doch für einen der beiden pfade nach einem alternativ-pfad
suchen, welcher nicht den knoten x beinhaltet.
ich habe auch schon versucht mir etliche szenarien zeichnerisch zu lösen, aber da die aussage ja allgemeingültig ist, bringen mich die ganzen sonderfälle nicht weiter.
RavenOnJ Auf diesen Beitrag antworten »

(u,v) und (v,w) sollen gemeinsame Knoten haben und x sei von u aus gesehen der erste dieser Knoten in (u,v). Dann wähle den Pfad (u,x)+(x,w) = (u,x,w). Da x der erste Knoten ist, gibt es keinen weiteren gemeinsamen Knoten von (u,x) und (x,w). Damit ist (u,x,w) ein erlaubter Pfad.
 
 
mussNochVielLernen Auf diesen Beitrag antworten »

Haben Sie vielen Dank!
RavenOnJ Auf diesen Beitrag antworten »

hier ist das Duzen üblich, aber bitte sehr.
Neue Frage »
Antworten »



Verwandte Themen

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