Impressum/Datenschutz
Bipartites Matching

Die Funktionen zur Ermittlung bipartiter Zuordnungen nutzen vier Algorithmen:

Algorithmus   Arbeitsweise
Ungarische Methode primal-duale Optimierung
Netzwerkfluß Maximalfluß bei minimalen Kosten in korrespondierendem 0-1 Netzwerk
WorstAlternativeNext heuristisch
Greedy wähle die erste passende Kante

Implementiert ist folgende Funktion:

Funktion   Kurzbeschreibung
MinimumWeightBipartite-
 PerfectMatching
perfektes Matching in einem bipartiten Graphen mit minimalen Kosten bzw. minimalem Gewicht

In der gegenüberliegenden Spalte ist ein Beispiel zu der Funktion.

Graph in Matrixform

{21., {{1, 3}, {2, 1}, {3, 5}, {4, 2}, {5, 4}}}

Plot bipartites Matching

Impressum/Datenschutz • Seite geprüft am 28. Nov. 2005