¿Cómo puedo encontrar una cubierta de borde mínima del gráfico bipartito ponderado usando Mathematica 8?

Question

En teoría de grafos, se utiliza el algoritmo húngaro para calcular la portada de un grafo bipartito ponderado de borde mínimo (un conjunto de aristas que incide a cada vértices, el que tiene el peso total mínimo.)

Me parece que en la nueva la versión 8 de Mathematica, hay un nuevo paquete de funciones para Graph Theory, (comience con Graph [].) Pero no he encontrado ninguna función que haga este trabajo. Encuentro una función llamada FindEdgeCover [] que solo puede encontrar una tapa de borde , no la mínima.

Answer 1

Hice algunos experimentos y, aunque no está documentado, parece que FindEdgeCover[] hace lo que quiere.

Considérese, por ejemplo:

h[list_] := CompleteGraph[4, EdgeWeight -> list] 

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

Pero

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

por supuesto ninguna garantía ...

Editar

Aquí tienes algo de código para experimentar con por usando diferentes adyacencias ponderadas ma trices

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]] 

Nota: El código es nada bueno, pero no pude encontrar una manera de utilizar EdgeLabels -> “EdgeWeight”. Publiqué this question para ver si alguien puede hacerlo.