bipartite Graphen im Zusammenhang mit LP

Neue Frage »

leo Auf diesen Beitrag antworten »
bipartite Graphen im Zusammenhang mit LP
Hilfe, Hilfe,

ich verstehe es einfach nicht!

Die Aufgabe lautet:

Für einen kantengewichteten bipartiten Graphen mit mit m mal n Kanten soll ein Matching von maximalen Gesamtkantengewicht bestimmt werden. Formulieren Sie dieses Problem als LP Aufgabe (die hier ganzzalige Basislösungen liefert) und dualisieren Sie diese, wobei Cij das Gewicht der Kante ij bezeichnen möge.

a) Bestimmen Sie ein Matching mit maximalen Gesamtkantengewicht für den bibartiten Graphen der Fig. 2.4 (folgt zum Schluß), wobei die eingetragenen Zahlen als Kantengewichte zu nehmen sind. Was ändert sich, wenn alle fehlenden Kanten mit Gewicht 1 hinzukommen?

b) Geben Sie jeweils ein Zertifikat für die Optimalität der Beiden Lösungen in (b) durch Angabe geeigneter dualer Lösungen an.

Also ich weis was ein bipartiter Graph ist. Und Matching verstehe ich im Grundsatz auch. Doch fallen mir keine sinnvollen Nebenbedingungen für das LP ein, von der Dualisierung ganz abgesehen.

zu a) Welcher Algorithmus bietet sich da an?

zu b) Was ist i.d. Zusammenhang ein Zertifikat? Eine Beurteilung?

Vielleicht könnt Ihr mir helfen? Ich möchte ja keine Lösung gepostet bekommen, aber mit Euer Hilfe...

Ich bin zum ersten mal in diesem oder irgendeinem Mathe Forum, also bitte ich um Nachsicht, falls ich nicht genau genug rüberbringen kann, was ich möchte. Ich gebe mir aber Mühe und erwarte nicht das Ihr mir die Lösung auf dem Präsentierteller serviert.

Danke

Lennard

P.S.

Fig 2.4

http://www.baeckerbecker.com/leo/pics/Fig.gif
Ben Sisko Auf diesen Beitrag antworten »
RE: bipartite Graphen im Zusammenhang mit LP
Zitat:
Original von leo
Also ich weis was ein bipartiter Graph ist. Und Matching verstehe ich im Grundsatz auch. Doch fallen mir keine sinnvollen Nebenbedingungen für das LP ein, von der Dualisierung ganz abgesehen.


In den Nebenbedingungen musst du jetzt genau diese Eigenschaften (Matching, bipartiter Graph) ausdrücken. Zielfunktion ist doch klar, oder?
Na, und wenn du schonmal ein LP angegeben hast, welcher Algo bietet sich dann wohl an?

"Zertifikat" verstehe ich so, dass du eine duale Lösung angeben sollst, sodass duale und primale Lösung denselben Zielfunktionswert haben (somit zertifiziert diese duale Lösung, dass die primale optimal ist).

Gruß vom Ben
Gast Auf diesen Beitrag antworten »

Schlag den Algorithmus doch einfach im Buch "Combinatorial Optimization" von Steiglitz nach, er nennt sich "Ungarische Methode". Viel Spass

Matthias
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »