Gewichtsmaximale Matchings

Ein (bipartiter) Graph $G = (V,E, c)$ heißt gewichtet, wenn es eine Gewichtsfunktion $c: E \rightarrow \mathbb{R}_{+}$ gibt, die jeder Kante aus $E$ ein Gewicht zuordnet.

Gegeben ist ein (bipartiter) gewichteter Graph $G = (V,E, c)$, dann heißt $M$ in $G$ ein gewichtsmaximales Matching, gdw. für alle Matchings $M'$ in G gilt: $c(M) \geq c(M')$, wobei $c(M) = \sum_{e \in M} c(e)$.