Maximum Weight Matching Probleme

Man stelle sich einen Graphen vor, der n Knoten enthält. Die Kanten sind gewichtet. Das Maximum Weight Matching Problem sucht eine Verbindung der Knoten mit jeweils einem anderen Knoten, so dass die Summe der (Kanten-)Gewichte maximal wird. Jeder Knoten darf dabei nur in eine Kante einfließen. Die Kanten [1,3] und [3,4], wenn 1,3 und 4 Knoten sind, können also nicht beide mit in die Lösung aufgenommen werden. Nur eine der Kanten kann aufgenommen werden, da der Knoten 3 sonst in 2 Kanten einfließen würde.

Jeder Knoten wird ausschließlich über eine Kante einem anderen Knoten zugewiesen.

Das Maximum Weight Matching Problem kann durch simple Greedy Algorithmen in polynomieller Zeit gelöst werden!