Verständnisfrage zu path

Moderator: Effiziente Graphenalgorithmen

aloifolia
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 22. Sep 2011 11:37

Verständnisfrage zu path

Beitrag von aloifolia »

Soeben erst mit den Vorlesungsaufzeichnungen und den Folien begonnen, bin ich recht schnell über eine Stelle gestolpert, die ich nicht ganz verstehe und wo Wikipedia aufgrund teilweise abweichender Definitionen auch nicht sehr hilfreich ist.

Ich frage mich, ob die Reihenfolge der Knoten und Kanten in den Mengenlisten der Pfaddefinition relevant sind. Mathematisch gesehen dürfte das ja eigentlich nicht der Fall sein, aber die Bedingung \(e_i = (v_i, v_{i+1})\) lässt darauf schließen. Nächste Frage: Impliziert ein Pfad auch edge disjointness?

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

Re: Verständnisfrage zu path

Beitrag von Prof. Karsten Weihe »

aloifolia hat geschrieben: Ich frage mich, ob die Reihenfolge der Knoten und Kanten in den Mengenlisten der Pfaddefinition relevant sind.
Für manche Fragen schon, für andere nicht. Bspw für die Definition der Länge eines Pfades ist die Reihenfolge sicher nicht relevant, da dies die Summe der Längen der Kanten ist und die Addition kommutativ ist.

aloifolia hat geschrieben: Nächste Frage: Impliziert ein Pfad auch edge disjointness?
Können Sie formulieren, warum sich diese Frage für Sie nicht aus den Folien beantworten lässt?

KW

aloifolia
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 22. Sep 2011 11:37

Re: Verständnisfrage zu path

Beitrag von aloifolia »

Prof. Karsten Weihe hat geschrieben:
aloifolia hat geschrieben: Ich frage mich, ob die Reihenfolge der Knoten und Kanten in den Mengenlisten der Pfaddefinition relevant sind.
Für manche Fragen schon, für andere nicht. Bspw für die Definition der Länge eines Pfades ist die Reihenfolge sicher nicht relevant, da dies die Summe der Längen der Kanten ist und die Addition kommutativ ist.
Ok, mich verwirrt dann nur, dass wir Mengen verwenden, wo es ja erstmal keine bestimmte Elementreihenfolge gibt.
Prof. Karsten Weihe hat geschrieben:
aloifolia hat geschrieben: Nächste Frage: Impliziert ein Pfad auch edge disjointness?
Können Sie formulieren, warum sich diese Frage für Sie nicht aus den Folien beantworten lässt?
KW
Nun, generell folgt das ja aus der Darstellung als Menge. Ich finde es nur mathematisch verwirrend, dass die Reihenfolge Elemente für die Bedingung relevant ist.

Antworten

Zurück zu „Effiziente Graphenalgorithmen“