25

是否有一种算法可以找到无向图的生成树，以最小化连接到多个边的顶点数？

例如，给定一个 4 x 4 的网格图，我们想在左边找到一棵生成树（它有 7 个顶点连接到多个边）而不是右边的生成树（有 12 个）：

4 x 4 网格图

编辑：如果我们只考虑平面图（甚至只考虑网格图），这个问题会更简单吗？

4

3 回答 3

4

正如 Evgeny 在评论中指出的那样，这被称为最大叶生成树问题。我已经链接到关于非常密切相关的连接支配集问题的维基百科文章，这是找到一个最小顶点集的问题，它 (i) 诱导一个连接子图 (ii) 满足以下命题，对于所有其他顶点 v ，集合中的某个顶点与 v 相邻。通过观察，这两个问题被证明是解等价的，通过观察，给定一棵生成树，我们可以通过丢弃叶子（只有一个连接的顶点）来构造一个连接的支配集，并且给定一个连接的支配集，我们可以提取诱导子图的生成树并将其他顶点附加为叶子。

不幸的是，这两个问题都是 NP-hard，并且在平面图的限制下它们仍然是 NP-hard。我特别不熟悉有关连通支配集的文献，但我的猜测是存在三个角度。

  1. 可证明的“快速”指数时间精确算法/近似算法。
  2. 不能证明很快（例如整数规划）但在实践中很好的精确算法。
  3. 启发式。

#1 可能看起来像一个奇怪的分组，但在平面图文献中往往发生的是，精确算法被用作近似算法中的子例程，通常通过 Brenda Baker 的一种称为移位的技术。平面图的属性之一是称为树宽的参数以 O(sqrt(n)) 而非 n 为界，并且存在运行时间指数是小得多的树宽的函数的动态程序。（例如，在网格上，您可以逐行运行 DP。树分解机制将其推广到任意平面图。）

如果不知道实例是什么样子，甚至可能没有对它们进行试验，很难就最好的课程向您提供建议。我可能会选择 2 号门，但我不确定一个好的配方是什么样的。好消息是，大部分算法复杂性都被抽象到您将使用的求解器库中。这是一个质量未知的配方。

对于所有 vertices v，假设x_vif1是非v叶子并且0ifv是叶子。主要的设置部分很容易。

minimize sum_v x_v
subject to
for all v, sum_{w such that w = v or w ~ v} x_w >= 1
for all v, x_v in {0, 1}

在这里，我~用来表示“相邻”。执行连接约束比较棘手。我能想到的最简单的方法是按原样求解整数程序，然后寻找两个顶点s，t它们都被选择但在解决方案中未连接，计算不包括所选顶点的分隔符U之间s的最小顶点分隔t符，输入约束

(1 - x_s) + (1 - x_t) + sum_{v in U} x_v >= 1

然后再试一次。

我对使用指数级变量的方法更有希望，但实现起来可能要困难得多（行和列生成）。r选择一个将被强制为非叶子的顶点（猜测或尝试所有可能性）。y_P每个简单路径P都有一个变量r作为端点。

minimize sum_v x_v
subject to
for all v, for all P having v as an interior vertex,
  x_v >= y_P
for all v, sum_{P having v as an endpoint} y_P >= 1
for all v, x_v in {0, 1}
for all P, y_P in {0, 1}
于 2015-08-01T13:59:05.340 回答
0

从来没听说过。

您可以使用广度优先搜索方法，将所有未访问的顶点添加到队列中并访问队列中的下一个顶点。同时，您将根据从连接顶点分支的可能边数将顶点及其边添加到优先级队列中。然后递归遍历PQ，每次都添加最好的边。您只需要减少包含已使用顶点的任何边。然后检查最后一个顶点是否有更高优先级的边，如果有，则回溯。

这是一个丑陋的概念，但实施起来可能会更糟。

于 2015-07-25T18:20:10.043 回答
0

对于 4x4，我只需要 7 个顶点连接到超过 1 个边，这将给我 9 个叶节点。

x-o-x x
  |   |
x-o-x o
  |   |
o-o-o-o
| | | |
x x x x

随着尺寸变大，您必须扩展上述模式。

对于 10x10，您将有 59 个叶节点

x-o-x x-o-x x-o-x x
  |     |     |   |
x-o-x x-o-x x-o-x o
  |     |     |   |
x-o-x x-o-x x-o-x o
  |     |     |   |
x-o-x x-o-x x-o-x o
  |     |     |   |
x-o-x x-o-x x-o-x o
  |     |     |   |
x-o-x x-o-x x-o-x o
  |     |     |   |
x-o-x x-o-x x-o-x o
  |     |     |   |
x-o-x x-o-x x-o-x o
  |     |     |   |
o-o-o-o-o-o-o-o-o-o
| | | | | | | | | |
x x x x x x x x x x

对于 Rows <> Cols 的网格，您必须在两个方向上尝试该模式，以查看哪个产生最佳结果。

于 2015-07-28T20:04:42.543 回答