Übung 9.3 M-augmentierende Pfade

Moderator: Effiziente Graphenalgorithmen

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Übung 9.3 M-augmentierende Pfade

Beitrag von zimpfer »

Da die Spezifikationen auf den Folien ein paar Details nicht nennen hab ich mal gesucht und folgenden Foliensatz gefunden:
http://www.math.uni-magdeburg.de/~kaibe ... andout.pdf

Dort wird ein M-augmentierende Pfad unter anderem mit Länge mindestens 3 und paarweise verschiedenen Knoten spezifiziert.

Gilt das auch für uns?

edit:
Muss auch bewiesen werden, dass die Anzahl der Pfade exponentiell wächst auf meinen Graphen?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 9.3 M-augmentierende Pfade

Beitrag von Stille »

Moin,

die Länge von mindestens 3 Kanten ergibt sich trivialerweise aus den Eigenschaften "alternierend" und "exponierte Endknoten".

In der Aufgabe sollen Sie erläutern, dass die Anzahl augmentierender Pfade exponentiell in Abhängigkeit von n wachsen kann. Das kann man beweisen, ein Beispiel oder eine Konstruktionsvorschrift mit passender Erläuterung reicht hier jedoch aus.

Viele Grüße,

Wolfgang Stille
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“