Matchings und Netzwerke

Erinnern wir uns an das Job-Zuordnungsproblem. Gegeben ist eine Menge S = {P ₁,...,P _n } von Personen und eine Menge T = {J ₁,...,J _n }von Jobs. Wir setzen P _i J _i ∈ K,falls P _i für den Job J _i geeignet ist. Wir wollen nun eine Zuordnung P _i → J _ϕ(i) finden, so dass jede Person P _i einen geeigneten Job J _ϕ(i) findet. Wann ist dies möglich? Allgemein werden wir Gewichte auf den Kanten P _i J _i haben (die wir z. B. als Eignungskoeffizienten interpretieren können), und die Zuordnung soll optimal (= maximal groß) werden.