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$

1 Answer 1

2
$\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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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