5
$\begingroup$

In graph theory, we use the Hungarian Algorithm to compute a weighted bipartite graph's minimum edge cover (a set of edges that is incident to every vertices, the one with the minimum total weight.)

I find that in new version 8 of Mathematica, there is a whole new package of functions for Graph Theory, (begin with Graph[].) But I've not found any function that do this job. I do find a function called FindEdgeCover[] that can only find a edge cover, not the minimum one.

$\endgroup$

migrated from math.stackexchange.com Aug 17 '12 at 16:48

This question came from our site for people studying math at any level and professionals in related fields.

1
$\begingroup$

But it seems to work anyway:

g = CompleteGraph[5, EdgeWeight -> Range@10, EdgeLabels -> "Name"];
g1 = CompleteGraph[5];
HighlightGraph[#, FindEdgeCover[#], ImagePadding -> 10] & /@ {g, g1}

Mathematica graphics

Verification:

WeightedAdjacencyMatrix[g] // MatrixForm

Mathematica graphics

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.