(GRAPHENTHEORIE) Perfect Matching der Knoten eines Graphen

[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