How to find a weighted dihedral minimal edge diagram using Mathematica 8?

Question

In graph theory, we use the Hungarian algorithm to calculate the weighted dihedral minimum edge of the edges (a set of edges incident to all vertices, a unit with a minimum total weight).

I find that the new version of Mathematica 8 has a whole new package of functions for graph theory (start with Graph [].) But I have not found any function that does this work. I find a function called FindEdgeCover [] that can only find the cover, not the minimum.

Answer 1

I did some experimentation and, although not documented, it seems that FindEdgeCover[] does what you want.

Consider, for example:

  h[list_] := CompleteGraph[4, EdgeWeight -> list] FindEdgeCover[h@Range@6] (* -> {1->2,1->3,1->4} *) 

But

  FindEdgeCover[h@Reverse@Range@6] (* -> {1->2,3->4} *) 

of course, no guarantees ...

Edit

Here you have the code for experimenting using various weighted adjacency matrices

 adj = {{\[Infinity], 1, 1, 1, 1}, {1, \[Infinity], 2, 2, 2}, {1, 2, \[Infinity], 2, 2}, {1, 2, 2, \[Infinity], 2}, {1, 2, 2, 2, \[Infinity]}} g = WeightedAdjacencyGraph[adj]; g = WeightedAdjacencyGraph[adj, VertexShapeFunction -> "Name", EdgeLabels -> MapThread[ Rule, {EdgeList@g, AbsoluteOptions[g, EdgeWeight] /. {_ -> x_} -> x}], GraphHighlight -> FindEdgeCover[g]] 

NB: the code is not very good, but I could not find a way to use EdgeLabels -> "EdgeWeight" . I posted this question to find out if anyone can do this.