首页 文章

生成树最小化连接到多个边的顶点数？

提问于
浏览 次
25

是否有算法可以找到无向图的生成树，从而最大限度地减少连接到多个边的顶点数？

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

4 x 4 grid graph

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

algorithm tree graph-theory spanning-tree

3 回答

  • 4

    对于4x4我只需要7个顶点连接到多个边缘，这将给我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

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

    回复于
  • 0

    从来没听说过 .

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

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

    回复于
  • 0

    正如Evgeny在评论中指出的那样，这被称为maximum leaf spanning tree problem . 我已经链接到关于非常密切相关的连接支配集问题的维基百科文章，这是找到一组最小顶点的问题，（i）诱导连通子图（ii）满足对于所有其他顶点v的命题，集合中的一些顶点与v相邻 . 通过观察，给定一个生成树，我们可以通过丢弃叶子（具有恰好一个连接的顶点）构造一个连通的支配集合，并且给出了两个问题 . 一个连通的支配集，我们可以提取诱导子图的生成树并将其他顶点作为叶子附加 .

    不幸的是，这两个问题都是NP难的，并且它们在平面图的限制下仍然保持NP难度 . 我不熟悉有关连接支配集的文献，但我的猜测是有三个角度 .

    • 可证明"fast"指数时精确算法/近似算法 .

    • 精确算法不能证明是快速的（例如整数编程），但在实践中很好 .

    • 启发式 .

    ＃1可能看起来像一个奇怪的分组，但平面图文献中常见的是精确算法被用作近似算法中的子程序，通常是由于Brenda Baker称为移位的技术 . 平面图的一个属性是名为treewidth的参数由O（sqrt（n））而不是n限定，并且存在动态程序，其运行时间指数是小得多的树宽度的函数 . （例如，在网格上，您可以逐行运行DP . 树分解机制将此概括为任意平面图 . ）

    在不知道实例的情况下甚至可能没有试验它们的情况下，很难就最佳课程提供建议 . 我可能会去＃2门，但我不确定一个好的配方会是什么样子 . 好消息是，大多数算法复杂性都被抽象到您将使用的求解器库中 . 这是一种质量未知的配方 .

    对于所有顶点 v ，如果 v 是非叶子，则 x_v 为 1 ，如果 v 是叶子，则 0 . 主导的设定部分很容易 .

    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}

    在这里，我使用 ~ 表示"is adjacent to" . 实施连接约束比较棘手 . 我能想到的最简单的方法是按原样求解整数程序，然后查找两个顶点 s 和 t ，这两个顶点在解决方案中都被选中但未连接，在不包括的分隔符之间计算 s 和 t 之间的最小顶点分隔符 U 选定的顶点，输入约束

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

    然后再试一次 .

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

    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}
    回复于

相关问题