In der Graphentheorie verwenden wir den ungarischen Algorithmus zur Berechnung der minimalen Kantenabdeckung eines gewichteten zweiteiligen Graphen (eine Menge von Kanten, die auf alle Ecken auftrifft, die mit dem minimalen Gesamtgewicht.)
Ich finde, dass es in der neuen Version 8 von Mathematica ein ganz neues Paket von Funktionen für die Graphentheorie gibt (beginnen Sie mit Graph [].) Aber ich habe keine Funktion gefunden, die diese Aufgabe erledigt. Ich finde eine Funktion namens FindEdgeCover [], die nur eine Kantenabdeckung finden kann, nicht die minimale.
Ich habe ein paar Experimente gemacht und, obwohl nicht dokumentiert, scheint FindEdgeCover[]
das zu haben, was Sie wollen.
Betrachten Sie zum Beispiel:
%Vor%Aber
%Vor%natürlich keine Garantie ...
Bearbeiten
Hier haben Sie einen Code zum Experimentieren mit verschiedenen gewichteten Adjazenzmatrizen
%Vor%
Hinweis: Der Code ist überhaupt nicht gut, aber ich konnte keinen Weg finden, EdgeLabels -> “EdgeWeight”
zu verwenden. Ich habe this question
gepostet, um zu sehen, ob jemand es tun kann.
Tags und Links wolfram-mathematica graph