|
|
|
|
|
|
|
|
für einen bipartiten Graphen
, Menge von paarweise nicht inzidenten Kanten.
Job-Zuordnungsprobleme mit 
als Menge von
Personen, 
als Menge von Jobs und 
für
eine Zuordnung von 
zu 
.
Ziel: Optimale Zuordnung von Elementen S zu Elemten T unter
Berücksichtigung von Gewichten auf den Kanten.
von G, Anzahl von Kanten in einem maximal
großen Matching.
kann kleiner als 
bzw. 
sein.
gilt.
Für einen bipartiten Graphen 
ist 
, wenn für eine
Teilmenge A von S gilt 
mit 
. (
ist die Menge der Nachbarn von A.)
Für einen bipartiten Graphen 
ist
, da drei Elemente von
nur zwei Nachbarn 
als Elemente von T
besitzen.
Träger von 
, Menge der Ecken 
, wobei D
jede Kante trifft (bedeckt).
Für jeden Träger D und jedes Matching M bedeckt D jede Kante
von M, und es ist 
.
Gleichgewichtssatz:
Für einen bipartiten Graphen 
gilt
Es gibt Methoden zur allgemeinen Konstruktion eines Maximum Matchings
und von einem Minimum Träger.
|
|
|
|
|
|
|
|
