首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >生成树,它将连接到多个边的顶点数目最小化?

问生成树,它将连接到多个边的顶点数目最小化?
EN

Stack Overflow用户
提问于 2015-07-25 03:37:38
回答 3查看 1K关注 0票数 25

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

例如,给定一个4x4网格图,我们想要找到一个像左边的生成树(它有7个顶点连接到多个边),而不是在右边的生成树(它有12):

​

​

编辑:如果我们只考虑平面图(甚至只是网格图),这个问题会更简单吗?

EN

回答 3

Stack Overflow用户

发布于 2015-08-01 13:59:05

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

不幸的是,这两个问题都是NP-硬的,而且在对平面图的限制下,它们仍然是NP-硬的.我不太熟悉关于连通支配集的文献,但我猜想有三个角度。

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

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

很难在不知道实例是什么的情况下,甚至不对它们进行实验的情况下,为您提供最佳的课程建议。我可能会选择2号门,但我不知道一个好的配方会是什么样子。好消息是,大多数算法复杂性都被抽象到您将要使用的求解器库中。这是一个未知质量的配方。

对于所有顶点v,如果x_v是非叶的,则v是1,如果v是叶的话,则是0。占主导地位的部分很容易。

代码语言:javascript
复制
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,这两个顶点都在解决方案中被选中但没有连接,计算不包括选定顶点的分隔符之间的s和t之间的最小顶点分隔符U,输入一个约束。

代码语言:javascript
复制
(1 - x_s) + (1 - x_t) + sum_{v in U} x_v >= 1

然后再试一次

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

代码语言:javascript
复制
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}
票数 4
EN

Stack Overflow用户

发布于 2015-07-25 18:20:10

就我所知没有。

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

这是一个丑陋的概念,但在实现上可能会更糟。

票数 0
EN

Stack Overflow用户

发布于 2015-07-28 20:04:42

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

代码语言:javascript
复制
x-o-x x
  |   |
x-o-x o
  |   |
o-o-o-o
| | | |
x x x x

当尺寸变得更大时,你必须在上面的模式上展开。

对于10x10,将有59个叶节点

代码语言:javascript
复制
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
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/31622650

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档