graphentheorie - pfade |
06.01.2013, 23:25 | mussNochVielLernen | Auf diesen Beitrag antworten » | ||
graphentheorie - pfade 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.. |
||||
06.01.2013, 23:52 | Mystic | Auf diesen Beitrag antworten » | ||
RE: graphentheorie - pfade Hm, und was wäre, wenn du die beiden Pfade einfach aneinander hängst? Natürlich müsste man im Falle dass dadurch Knoten mehrfach auftreten, das anschließend noch "in Ordnung bringen"... |
||||
07.01.2013, 11:12 | 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... |
||||
07.01.2013, 11:32 | Math1986 | Auf diesen Beitrag antworten » | ||
RE: graphentheorie - pfade
|
||||
07.01.2013, 19:06 | 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. |
||||
07.01.2013, 20:28 | 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. |
||||
Anzeige | ||||
|
||||
07.01.2013, 20:50 | mussNochVielLernen | Auf diesen Beitrag antworten » | ||
Haben Sie vielen Dank! |
||||
07.01.2013, 20:52 | RavenOnJ | Auf diesen Beitrag antworten » | ||
hier ist das Duzen üblich, aber bitte sehr. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |