prev up inhalt next


10.8 Perfektes Matching


Definition:


Ein Matching heißt perfekt $\iff$|M| = ${\frac{\vert V\vert}{2}}$ (d.h., jeder Knoten ist gematcht).

Sei G = (V,E) ungerichtet, bipartit, gewichtet mit c : E$\to$$
\mathbb {Z}
$ .

(z.B. c(i,j) = Glücksgefühl bei Paarung Mann i / Frau j )

Gesucht: Maximum cost matching z.B.:


Idee: Suche alternierende Wege, die die Gesamtkosten erhöhen.


Variante: Suche perfektes Matching mit minimum cost.

Problem: Zuordnungsgewicht zwischen i und j wird von i und j unterschiedlich gesehen.

Antwort: Ranking (d.h. statt absoluter Werte eine Reihenfolge 1,2,... festlegen, also eine Beliebtheitsskala bzw. Präferenzliste erstellen)


prev up inhalt next