Hi,

bin zwar WiInf, versuch hier trotzdem mal mein Glück. Vielleicht kann mir ja jemand helfen?

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 im Anhang), 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 :-) ?

Danke

Lennard
[img]http://www.baeckerbecker.com/leo/pics/Fig.gif[/img]

Ein Matching nach Wikipedia.de:
Eine Paarung (englisch matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen inzidenten Knoten besitzen.
Und genau das musst du als Nebenbedingung kodieren.
Als Algorithmus für das Lösen einer LP Aufgabe bietet sich eigentlich immer Simplex an - da ich die Aufgabe noch nicht gerechnet habe, kann ich aber nicht sagen, ob der hier auch sinnvoll ist.
Edit:
Ein Zertifikat ist IMHO als Beweis zu sehen. Du musst also irgendwie zeigen, dass die gefundene Lösung wirklich optimal ist.