11. Übung Aufgabe 1

Moderator: Effiziente Graphenalgorithmen

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

11. Übung Aufgabe 1

Beitrag von David »

Hallo,

kann mir jemand kurz zusammenfassen, wie der Ansatz für Aufgabe 1 in der 11. Übung ist? Habe leider meine Aufzeichnung dazu nicht gefunden.

Mein Ansatz war damals vollst. Enumeration. Ich weiß aber noch, dass es eine deutlich bessere Lösung gab.

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: 11. Übung Aufgabe 1

Beitrag von Maeher »

Das müsste gewesen sein, nen bipartiten Graphen zu erstellen, links die Städte, rechts die Anbieter. Städte b=1 Anbieter b=-1 und die Kantengewichte aus der Matrix negieren.

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

Re: 11. Übung Aufgabe 1

Beitrag von Stille »

Genau. Man kann das Problem als Matching Problem auf einem bipartiten Graphen modellieren. Für das Flußproblem benötigt man noch zwei Knoten mehr: einen Knoten s adjazent zu allen Knoten der linken Partition, und einen Knoten t adjazent zu allen Knoten der rechten Partition. Diese Kanten haben Kapazität 1 und Kosten 0. b(s)=3, b(t)=-3. Fertig. Genausogut kann man für jeden Knoten der Bipartition b(v)=+/-1 setzen, da ja mehrere Quellen und Senken erlaubt sind.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“