Wie finde ich die minimale Kantenabdeckung eines gewichteten zweiteiligen Graphen mit Mathematica 8?

8

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.

    
trVoldemort 11.09.2011, 02:23
quelle

1 Antwort

6

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.

    
Dr. belisarius 11.09.2011 06:03
quelle

Tags und Links