(GRAPHENTHEORIE) Perfect Matching der Knoten eines Graphen

[Hopsel]

Hi LanX²!

Schritt 1:
für alle a in A und b in B: alle Kanten (a,b) streichen für die (a,b') existiert mit w(a,b') < w(a,b). Analog für (b,a).
Schritt 2:
Nur die unegrichteten Kanten (a,b ) stehen lassen für die sowohl (a,b) als auch (b,a) existieren.

Ich fasse die Schritte zu einem zusammen. Dabei rechne ich auf zwei Matrizen der Mächtigkeit |A|x|B| und |B|x|A|. Diese addiere ich Elementweise. Das geht, weil |A|=|B|. Mit der resultierenden Matrix C fange ich nun an und setze eine größte Schranke so fest, dass alle Kanten, deren Nähe größer als die Schranke ist, wegfallen, aber trotzdem jeder Knoten mindestens eine Kante besitzt.
Dann lasse ich den Algorithmus von Hopcroft und Karp darüber laufen, um eine größte Paarung zu bestimmen. Liegt ein Perfect Match (alle Knoten haben einen Partner) vor und genügt dieses meinen Kriterien, kann ich abbrechen.
Ansonsten muss ich wieder von vorne anfangen, setzt nun aber die Schranke höher.

Um den Algorithmus zu optimieren, werde ich auch nicht mit der Nähe, sondern wirklich mit dem Gewicht bzw. der Kapazität der Kanten arbeiten. Ich setze also eine kleinste Schranke fest.
Auf dem entstandenen Graph kann ich mit dem Algorithmus von Ford und Fulkerson die maximale und, da er, so wie ich das verstehe, die Kapazität berücksichtigt, optimale größte Paarung feststellen.

Danke für deine Hilfe und deinen Willen, dich damit auseinanderzusetzen.

MfG H☼psel