(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

[LanX²]

Hi

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

Du meinst, dass es kein *eideutiges* Optimum gibt.

*Ob* es eine Paarung gibt sollte dir der Hochzeitssatz sagen. Ein Optimum ist dannn ja immer gegeben, alleine das Optimum muss nicht *eindeutig* sein.

mehr kann ich dir nicht helfen!

Vielleicht höchstens das du ja das problem auf ungerichtete Graphen reduzieren kannst, schließlich sind die Kanten von B nach A nach deienr Bescreibung irrelevant.

Tschua
  Rolf

[Hopsel]

Hi LanX²!

Hui! =) Dass doch noch einer antwortet...

Es kann aber auch durchaus vorkommen, dass es keine optimale Paarung gibt.
Du meinst, dass es kein *eideutiges* Optimum gibt.

Eigentlich meine ich, dass es vorkommen kann, dass keine Paarung aller Elemente möglich ist. Also kein "Perfect Match".

*Ob* es eine Paarung gibt sollte dir der Hochzeitssatz sagen. Ein Optimum ist dannn ja immer gegeben, alleine das Optimum muss nicht *eindeutig* sein.

Also theoretisch ist eine Paarung immer möglich. Allerdings werden an die Paarung weitere Bedingungen geknüpft, die ich wohl nicht im Stande war zu erläutern.

mehr kann ich dir nicht helfen!

Schon das kleinste Feedback baut auf. =)

Vielleicht höchstens das du ja das problem auf ungerichtete Graphen reduzieren kannst, schließlich sind die Kanten von B nach A nach deienr Bescreibung irrelevant.

Ich versuche mich an einer besseren Erklärung. Diesmal ein schöneres Beispiel. Leider immer noch ziemlich komplex.
Ich habe einen bipartiten Graphen gegeben mit folgender Adjazenzmatrix:
  │A  B  C  D  E  0  1  2  3  4
──┼────────────────────────────
A │               3  1  4  5  2
B │               1  2  3  4  5
C │               5  1  2  4  3
D │               1  3  2  4  5
E │               4  3  2  5  1
0 │2  4  5  3  1
1 │4  3  5  1  2
2 │1  3  4  2  5
3 │4  2  1  3  5
4 │5  2  3  1  4
Die freien Stellen sind nicht existente Kanten.

Ich suche jetzt ein Paarung, so dass für alle Paare gilt:
[latex]a_1,a_2 \in {A,B,C,D,E}, b_1,b_2 \in {0,1,2,3,4}[/latex]
Eine Paarung latex[/latex] und latex[/latex] ist nun genau dann erlaubt, wenn:
([latex]weight(a_1,b_2) \ge weight(a_1,b_1)[/latex] oder [latex]weight(b_1,a_2) \ge weight(b_1,a_1)[/latex])
und
([latex]weight(a_2,b_1) \ge weight(a_2,b_2)[/latex] oder [latex]weight(b_2,a_1) \ge weight(b_2,a_2)[/latex])

In Worten:
Ein Element a1 braucht zu seinem Partner b1 mindestens ein so kleines Gewicht wie zu allen anderen potentiellen Partnern b2, die zu diesem Element a1 ein geringeres Gewicht als zu ihren Partner a2 haben.

Oder noch anders:
Eine Paarung ist dann erlaubt, wenn zwei nicht im selben Paar liegende Partner sich nicht gegenseitig näher wären.

Beispiel von oben:
(A,3) und (E,2) wären keine güligen Paare, da sie sich gegenseitig ausschließen, da weight(A,3) > weight(A,2) und weight(2,E) > weight(2,A).
[Die Gewichte werden aus der Matrix mit weight(Zeile x Spalte) gelesen.]

Ich habe gehofft, es gäbe schon einen Algorithmus, der dieses Problem angeht.

MfG H☼psel

[LanX²]

Hi

Sorry, aber das ist mir zu konfus!

Das allgemeine Problem  ist äquivalent dazu n Männer und Frauen (Knotenmenge A und B) miteinander zu verheiraten, wobei die Kanten ausdrücken, wer mit wem könnte.

Deswegen spricht die deutsche Mathematik bei Bipartiten Graphen auch vom "Heiratssatz" um die existenz einer vollständigen Lösung zu beschreiben.

Optimierst du nun zusätzlich über gerichete und gewichtete Kanten, dann ist das in unserem Bild vergleichbar mit Brautpreis in der einen und Mitgift in der anderen Richtung.

Da du aber nur in eine Richtung optimieren willst, reicht es auf einen ungerichteten Graphen zu vereinfachen. Alles andere macht keinen Sinn.

Na und dafür hast du ja angeblich schon nen Algorithmus!

tschau
 LanX

[Hopsel]

Hi LanX²!

Optimierst du nun zusätzlich über gerichete und gewichtete Kanten, dann ist das in unserem Bild vergleichbar mit Brautpreis in der einen und Mitgift in der anderen Richtung.

Leider nicht. Ich weiß, es ist schwierig zu verstehen. Aber versuch erstmal das zu beschreiben. Ich möchte meinen, das ist fast noch schwieriger.

Beispiel:

Paar 1
————————————————————————————————
Bräutigam 1 liebt Braut 1 zu 70%
Braut 1 liebt Bräutigam 1 zu 60%

Paar 2
————————————————————————————————
Bräutigam 2 liebt Braut 2 zu 40%
Braut 2 liebt Bräutigam 2 zu 80%

Zusätzlich:
————————————————————————————————
Braut 1 liebt Bräutigam 2 zu 80%
Bräutigam 2 liebt Braut 1 zu 60%

Damit sind Paar 1 und Paar 2 in Kombination ungültig, da es einen Partner in jedem Paar gibt, der den Partner des anderen Partner mehr magt, als seinen jetzigen Partner.

Wenn Braut 1 Bräutigam 2 nur zu 50% lieben würde, wäre alles in Butter.
Bräutigam 2 wäre zwar immer noch lieber mit Braut 1 zusammen, wird von der aber abgewiesen, weil die Bräutigam 1 mehr liebt.

Jetzt klarer?

Dieses Problem hat mit einem Brute-Force-Algorithmus eine Komplexität(klasse) von n!. Ich hoffe immer noch, dass es einen Algo gibt, der mir zumindest eine mögliche Lösung, sofern sie vorhanden ist, berechnet.

MfG H☼psel

[LanX²]

Hi Hopsel,

ich hab mich bereits korrigiert, sorry ich kann dir ad hoc nicht helfen, da musst du mit nem Experten (Optimierer) reden.

Intuitiv würde ich sagen der einzige Weg wäre eine Verkürzung auf einen ungerichetetn Graphen, d.h. du ermittelst nur die zulässigen Kanten zwischen A und B die man ungestraft wählen dürfte (A mag B am meisten und B mag A am meisten), das ist linear zu der Zahl der Einträge in der matrix.

Und dann mit Standrad Algo drauf.

Tschau
 LanX

PS: Bin raus, hab zu tun!

[LanX²]

Hi

Intuitiv würde ich sagen der einzige Weg wäre eine Verkürzung auf einen ungerichetetn Graphen, d.h. du ermittelst nur die zulässigen Kanten zwischen A und B die man ungestraft wählen dürfte (A mag B am meisten und B mag A am meisten), das ist linear zu der Zahl der Einträge in der matrix.

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.

Tschau
  LanX

[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

[flowh]

Hallo Forum.

[..] eines Graphen von Hopsel, 24.12.2008, 21:16

ja ist denn schon wieder Weihnachten?

Servus,
Flo

[Hopsel]

Hi flowh!

[..] eines Graphen von Hopsel, 24.12.2008, 21:16
ja ist denn schon wieder Weihnachten?

Ich habe darum gebeten, diesen Thread noch nicht zu archivieren, damit ich die Möglichkeit habe, später noch eine Antwort zu schreiben.

Diese Antwort benötigt aber noch etwas Zeit. Ich setze mich aber sofort an die Aufgabe. =)

MfG H☼psel

[flowh]

Hallo H☼psel.

Ah, ich verstehe. Dachte schon fast an übernatürliche Kräfte...

Diese Antwort benötigt aber noch etwas Zeit. Ich setze mich aber sofort an die Aufgabe. =)

Mach dir keinen Stress, hast ja noch acht Tage Zeit. :-)

Servus,
Flo

[LanX²]

Hi

Eine Paarung latex[/latex] und latex[/latex] ist nun genau dann erlaubt, wenn:
([latex]weight(a_1,b_2) \ge weight(a_1,b_1)[/latex] oder [latex]weight(b_1,a_2) \ge weight(b_1,a_1)[/latex])
und
([latex]weight(a_2,b_1) \ge weight(a_2,b_2)[/latex] oder [latex]weight(b_2,a_1) \ge weight(b_2,a_2)[/latex])

Sorry ich muss mich korrigieren, das ist zu komplex!

Mir (*) fällt dazu ad hoc nichts ein außer Brute-Force.

Tschau
  LanX

(*) was nix zu heißen hat!