Episode 16 - Maximale Matchings

In vielen praktischen Anwendungen ist es notwendig
1:1-Zuordnungen zwischen Menschen oder Objekten zu finden, die in
irendeinerweise kompatibel zueinander sind. Ein medizinisches
Beispiel sind Überkreuz-Nierenspenden, bei denen
Spender/Empfänger-Paare  passend ausgewählt werden müssen um
kompatible Organspender zu finden. Solche Probleme lassen sich
als Matchingproblem in ungerichteten Graphen modellieren und
können mithilfe von Edmonds' Blossom-Shrink-Algorithmus gelöst
werden.