Verständnisfrage zu "generalized paths"

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Verständnisfrage zu "generalized paths"

Beitrag von tmuecksch »

Hallo,

heute habe ich mich dem Wiki-Eintrag "Paths" (Url: http://wiki.algo.informatik.tu-darmstad ... .php/Paths) gewidmet.
Unter der ersten Überschrift "Basic definitions" wird über "generalisierte Pfade" (eig. "generalized paths") gesprochen. Hierbei werden "forward arcs" und "backward arcs" definiert. Allein aus der Bennung ergab sich mir nicht so recht was man sich darunter vorzustellen hat. Also habe ich die Definitionen 1-4 etwas aufgedröselt und verbildlicht. Doch das Ergebnis verwirrt mich noch mehr.

Bild

EDIT: Ok, mir ist aufgefallen, wenn man die Zeichnung etwas glücklicher wählt, ist es deutlich verständlicher was ein backward und was ein forward arc sein soll:

Bild

Es stellt sich also die Frage:
Wie kann es solche Pfad-Bestandteile wie in Punkt 2 oder 3 Beschrieben überhaupt geben? Ein Pfad beschreibt doch einen Weg von a nach b. Oder ist die Definition von Pfaden so offen, dass auch solche "Missbildungen" erlaubt sind?

Vielen Dank im Voraus
Zuletzt geändert von tmuecksch am 18. Aug 2013 14:56, insgesamt 2-mal geändert.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Verständnisfrage zu "generalized paths"

Beitrag von tmuecksch »

[EDIT]

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Verständnisfrage zu "generalized paths"

Beitrag von JannikV »

Hallo,

wie du richtig erkannt hast, beschreibt ein Pfad einen Weg von a nach b. Dieser Pfad muss aber nicht besonders kurz, effizient oder schön sein. Der kann etwa auch so aussehen:

a -> x -> y -> a -> y -> x -> b

Also von a nach x, von da nach y, von y zurück nach a, direkt wieder zurück nach y, weiter zurück nach x und schlussendlich zu b. Auch wenn man direkt a -> x -> b hätte gehen können. Aber niemand hat gesagt, dass hier ein kürzester Weg gesucht werden soll.

VG

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Verständnisfrage zu "generalized paths"

Beitrag von tmuecksch »

Danke für die Antwort, aber ich verstehe immer noch nicht ganz...

Also so wie ich das jetzt aufgefasst habe könnte es also auch solche Pfade geben:

x --> y <-- z --> a --> b

Dann wäre doch y eine Sackgasse? Man käme doch nie zum Knoten "z", welcher wiederum zwei ausgehende Kanten hat, was ja auch so seine Probleme birgt. Ich hatte Pfade als etwas strikt lineares verstanden... Also quasi als eine Wegbeschreibung von x nach b im Graphen G.
Das wäre ja dann in diesem Beispiel nicht gegeben.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Verständnisfrage zu "generalized paths"

Beitrag von JannikV »

Du könntest von y aber noch andere Kanten abgehen lassen, z.B. nach x und nach z, dann kann man da beliebig hin und her gehen.

Ob das was du da gezeichnet hast per Definition ein Pfad ist, da bin ich mir nicht ganz sicher..

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Verständnisfrage zu "generalized paths"

Beitrag von tmuecksch »

JannikV hat geschrieben:Du könntest von y aber noch andere Kanten abgehen lassen, z.B. nach x und nach z, dann kann man da beliebig hin und her gehen.
Wieso das? In einem Graphen ist mir das klar. Aber ein Pfad auf einem Graphen beschreibt doch einen festgelegten Weg durch diesen Graphen, oder? Um das zu konkretisieren: Da ein Pfad eine geordnete Sequenz von gerichteten Katen ist (bzw. Knoten-Tupeln die solche beschreiben), habe ich das so aufgefasst, dass v1 der Startknoten ist und wk der Zielknoten und man dann den so definierten Pfad von links nach rechts liest (sonst würde man die Sequenz ja nicht geordnet heißen) und so einen Weg durch den Graphen geht, der strikt festgelegt ist und keine Entscheidungsfreiheit lässt. Dass man möglicherweise einen bestimmten Knoten mehrmals besucht sei nicht ausgeschlossen.

Wie kann es also in einer derart definierten Sequenz rückwärtig verlaufende Kanten oder gar mehrere ausgehende Kanten haben?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Verständnisfrage zu "generalized paths"

Beitrag von JannikV »

Ok, das Wort beliebig war von mir nicht glücklich gewählt. Der Pfad soll durchaus fest sein. Aber der Pfad kann ja festlegen dass man zunächst 10 mal zwischen x und y hin und her läuft und dann weiter richtung z geht..

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Verständnisfrage zu "generalized paths"

Beitrag von tmuecksch »

JannikV hat geschrieben:Ok, das Wort beliebig war von mir nicht glücklich gewählt. Der Pfad soll durchaus fest sein.
Dann ergibt sich mir aber immer noch nicht der Verwendungszweck von rückwärtigen Pfeilen.
JannikV hat geschrieben:Aber der Pfad kann ja festlegen dass man zunächst 10 mal zwischen x und y hin und her läuft und dann weiter richtung z geht..
Das würde aber dann doch so aussehen:
x -> y -> x -> y -> z


und nicht so:
x <- y -> z


(Um es noch einmal zu verdeutlichen; ich hänge mich an der Definition 2.1 - 2.4 von Paths im Wiki unter Basic definitions auf).

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: Verständnisfrage zu "generalized paths"

Beitrag von AlexPi11 »

Ich hab mal mitgelesen und mir fällt dazu folgendes auf.
Nach Wiki-Definition betrachtet man sich ja nur zwei aufeinanderfolgende Pfeile. Da wäre das erste Problem: Was wenn man nur einen Pfeil hat (Pfadlänge = 1)? Da könnte man anhand der Definition schon mal nicht sagen, ob das vorwärts oder rückwärts sein soll.
Das nächste ist, dass ein Vorwärtspfeil im späteren Verlauf auch ein Rückwärtspfeil sein kann und umgekehrt. z.B. Wenn man bei tmuecksch's Zeichnung zu 2.2 von \(w_{1} = w_{2}\) noch einen dritten Pfeil zu einen neuen Zielknoten ziehen würde, wäre der Rückwärtspfeil nun ein Vorwärtspfeil, da \(v_{2} \rightarrow w_{1} = w_{2} = v_{3} \rightarrow w_{3}\) dem Fall 2.1 entspricht.
Beim dem einfacheren Fall A \(\rightarrow\) B \(\rightarrow\) A wären beide Pfeile sogar "zeitgleich" vorwärts und rückwärts gerichtet.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Verständnisfrage zu "generalized paths"

Beitrag von JannikV »

Ja, ich sehe was für ein problem ihr seht.. Inzwischen bin ich auch ziemlich verwirrt.
Am besten mal bei Prof. Weihe nachfragen wie er sich das bei der Erstellung der Wiki-Seite gedacht hat.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Verständnisfrage zu "generalized paths"

Beitrag von Prof. Karsten Weihe »

tmuecksch hat geschrieben: Wie kann es solche Pfad-Bestandteile wie in Punkt 2 oder 3 Beschrieben überhaupt geben? Ein Pfad beschreibt doch einen Weg von a nach b. Oder ist die Definition von Pfaden so offen, dass auch solche "Missbildungen" erlaubt sind?
Nein, die Definition von Pfaden ist nicht so offen, aber die Definition von verallgemeinerten Pfaden ist so offen. 8)

Wir sind in der GdI II nicht zu Flussalgorithmen gekommen. Dort sind verallgemeinerte Pfade sehr wichtig. Nur um eine Idee zu geben: Zusätzlichen Fluss der Stärke X von A nach B in einem Graphen kann man über einen solchen verallgemeinerten (dort "augmentierend" genannten) Pfad schicken, indem der Flusswert auf allen Vorwärtskanten um X erhöht und auf allen Rückwärtskanten um X vermindert wird. Wenn man keine Rückwärtskanten in die Betrachtung einbezieht, verfehlt man in der Regel den maximalen Fluss.

Klarer geworden?

KW

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Verständnisfrage zu "generalized paths"

Beitrag von tmuecksch »

Prof. Karsten Weihe hat geschrieben: Klarer geworden?
Auf jeden Fall! Vielen Dank für die Mühe.

Antworten

Zurück zu „Archiv“