2

是否有任何有效的算法可以在具有偶数个顶点的完整加权图中找到具有以下属性的边集。

  • 对于满足其他标准的任何集合，该集合具有最小、最大的边权重
  • 每个顶点都连接到集合中的一条边

所有权重均为正

d我想不出比蛮力更好的方法，但我不认为它是 NP 难的。

4

2 回答 2

2

在多项式时间内解决此问题的一种方法如下：

  1. 在 O(E log E) 时间内对边缘权重进行排序
  2. 对于每条边，在 ~O(E) 时间内为其分配一个伪权重 E' = 2^{position in the ordering}
  3. 在 O(V^3) 时间内找到伪权重之间的最小权重完美匹配（取决于您选择的算法，它可能更慢或更快）

这最大限度地减少了完美匹配包含的最大边缘，这正是您在 O(V^3) 时间内寻找的东西。

下面给出了如何做第 3 部分的资源
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/ sp10/cs598csc/Lectures/Lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

示例 C++ 源代码可在http://ciju.wordpress.com/2008/08/10/min-cost-perfect-matching/ 获得

于 2010-10-31T14:51:15.460 回答
0

试试这个（我只是想到了这个，所以我既没有证据证明它会给出最佳答案，也没有证据表明它是否会在每种情况下产生解决方案）：

  1. 搜索最重的顶点 V(A, B)
  2. 从图中删除顶点 V
  3. 如果 A 仅连接到单个其他顶点 T(A, C) 则删除连接到 C 的所有其他边，对这些边也重复步骤 3
  4. 如果 B 仅连接到单个其他顶点 S(B, D)，则删除连接到 D 的所有其他边，对这些边也重复步骤 4
  5. 从步骤 #1 重复
于 2010-10-31T14:38:33.577 回答