如何使用Mathematica 8查找加权二分图的最小边覆盖？

Question

在图论中，我们使用匈牙利算法来计算加权二分图的最小边覆盖（一组与每个顶点相交的边，其总权重最小）。

我发现在Mathematica的新版本8中，有一个全新的图论函数包（以Graph[]开头）。但是我没有找到任何可以完成这项工作的函数。我发现一个名为FindEdgeCover[]的函数只能找到一个边覆盖，而不能找到最小的边覆盖。

- xzhu

---

你确定这个函数不能满足你的需求吗？根据文档，FindEdgeCover[g] 可以找到图 g 的最小边覆盖。所以它不是已经找到了所需的最小边覆盖吗？否则会有多个答案，包括非最小边覆盖。 - Verbeia

不，我所说的最小值是指集合中边权重的总和最小，而不是边的数量。 - xzhu

啊，所以是未加权版本，实际上。可能还没有构建必要的函数。 - Verbeia

@trVoldemort - 感谢你提出这个问题...我刚好在看匈牙利算法，但对图论知识了解甚少。虽然我可以理解基于矩阵的算法解释，但是理解与图形的对应关系仍然让我感到沮丧。 - telefunkenvf14

Answer 1

我进行了几个实验，虽然没有记录，但似乎 FindEdgeCover[] 可以满足您的需求。

例如，请考虑以下情况：

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

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

但是

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

当然，没有保修... 编辑 这里有一些代码可以使用不同的加权邻接矩阵进行实验。

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

注：这段代码一点也不好，但我无法找到使用“EdgeLabels -> “EdgeWeight””的方式。我发布了这个问题，看看有没有人能够做到。

- Dr. belisarius