(GRAPHENTHEORIE) Perfect Matching der Knoten eines Graphen

[Hopsel]

Hi alle!

Unter euch sind sicher einige, die sich mit der Graphentheorie auskennen.
Ich suche einen Perfect-Matching-Algorithmus für einen Graphen, der folgende Eigenschaften hat:

• bipartit (die Klassen A und B sind vorhanden)
• jeder Knoten aus A ist mit jedem Knoten aus B verbunden und umgekehrt
• innerhalb der Klassen A und B gibt es keine Kanten
• gerichtete Kanten
• gewichtete Kanten

Aufgabenstellung ist, für jeden Knoten der Klasse A einen Partner aus Klasse B zu finden, sodass für alle (ungerichteten Paar-)Kanten latex[/latex] gilt:
[latex]\forall (a,b): weight(a,b) \le weight(c,d)[/latex] mit [latex]a,c \in A[/latex] und [latex]b,d \in B[/latex]

Ich hoffe, ich habe das richtig beschrieben. Und wenn nicht, dann wenigstens so, dass es jemand versteht.

Ich habe folgende Algorithmen gefunden, die aber mMn nicht alle geforderten Graphkriterien (insbesondere gerichtete und gewichtete Kanten) erfüllen:
Algorithmus von Hopcroft und Karp
Algorithmus von Ford und Fulkerson (maximaler Fluss)
Blossom Algorithmus (PDF)

Noch als Anmerkung: Der Blossom Alogrithmus berechnet "Minimum-Weight Perfect Matchings". Ich vermute, er ist genau das, was ich suche, allerdings weiß ich nicht, ob der auch für gerichtete Graphen angewendet werden kann.

Hat jemand einen Idee oder vielleicht sogar den entscheidenden Hinweis?

Vielleicht sollte ich noch ein Beispiel bringen.
[latex]A = {a_1,a_2}[/latex]
[latex]B = {b_1,b_2}[/latex]
[latex]weight(a_1,b_1) = 0[/latex]
[latex]weight(a_1,b_2) = 1[/latex]
[latex]weight(a_2,b_1) = 1[/latex]
[latex]weight(a_2,b_2) = 0[/latex]
[latex]weight(b_1,a_1) = 0[/latex]
[latex]weight(b_1,a_2) = 1[/latex]
[latex]weight(b_2,a_1) = 1[/latex]
[latex]weight(b_2,a_2) = 0[/latex]
Bildlich:
                  0
     ─────────────────────────>
  a1                            b1
 │ ↑ <───────────────────────── │ ↑
 │ │             0              │ │
 │ │                            │ │
1│ │1                          1│ │1
 │ │                            │ │
 │ │              0             │ │
 ↓ │ ─────────────────────────> ↓ │
  b2                            a2
     <─────────────────────────
                  0

Die optimale Paarung wäre hier (a1,b2) und (a2,b1).
Es kann aber auch durchaus vorkommen, dass es keine optimale Paarung gibt.

MfG H☼psel