(GRAPHENTHEORIE) Perfect Matching der Knoten eines Graphen

[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