最小连接的子图包含给定的节点集

Question

我有一个未加权的连接图。我想找到一个连接的子图，肯定包括一组节点，以及尽可能少的额外内容。如何实现？

以防万一，我将使用更精确的语言来重述这个问题。令G（v，e）为未加权的，未方向的，连接的图。令n为V的某个子集。找到G（v，e）的最小连接子G'（v'，e'）的最佳方法是，n是v'的子集？

近似值很好。

Answer 1

我想不出有效的算法来找到最佳解决方案，但是假设您的输入图密集，以下内容可能足够好：

1. 转换您的输入图 G(V, E) 到加权图 G'(N, D), ， 在哪里 N 是您要覆盖的顶点的子集 D 是原始图中相应顶点之间的距离（路径长度）。这将“崩溃”您不需要的所有顶点。

2. 计算最小生成树 G'.

3. 按以下步骤“展开”最小跨树：对于每个边缘 d 在最小跨越树中，以图中的相应路径为 G 并在结果集的路径上添加所有顶点（包括端点） V' 以及结果集的路径中的所有边缘 E'.

该算法很容易绊倒以提供次优的解决方案。示例案例：等边三角形，拐角处有顶点，侧面和三角形中间，沿侧面，从拐角处到三角形的中间。为了覆盖角足以选择三角形的单个中间点，但是该算法可能会选择侧面。尽管如此，如果图形密集，它应该可以正常工作。

Answer 2

这正是众所周知的NP-HARD 斯坦纳树 问题。没有更多有关您的实例的详细信息，很难就适当的算法提供建议。

Answer 3

最简单的解决方案将是以下内容：

a）基于MST： - 最初，v的所有节点均在v'中 - 构建图G（V，e）的最小跨度树 - 称为T。
- 循环：对于不在n中的每个叶子v，从v'中删除v。
- 重复循环，直到t中的所有叶子都在n中。

b）另一个解决方案是以下 - 基于最短路径树。
- 选择n中的任何节点，称其为v，令V为树T = {V}的根。 - 从n删除V。

• 循环：1）从t中的任何节点和n中的任何节点中选择最短路径。最短路径p：{v，...，u}其中v在t中，u在n。2）p中的每个节点）p中的每个节点被添加到V'中。 3）p和n中的每个节点都从n中删除。--重复循环直至n为空。

在算法的开头：使用任何已知的有效算法计算G中的所有最短路径。

就我个人而言，我在其中一篇论文中使用了该算法，但它更适合分布式环境。令n为我们需要互连的节点集。我们希望构建图G的最小连接的主导集，并希望给出N中的节点的优先级。我们给出了每个节点UA唯一的标识符ID（U）。如果u在n中，则让W（u）= 0，否则W（1）。我们为每个节点U创建Pair（W（U），ID（U））。

• 每个节点u构建一个多电视继电器节点。也就是说，一个1跳neigbhors的M（u）集，使每个2跳邻邻邻邻邻M（u）中至少一个节点。 [最小值m（u），解决方案越好]。

• u在v'时，仅当u时：u在其所有邻居中具有最小的对（w（u），id（u））。或在m（v）中选择u，其中v是最小（w（u），id（u））的u的1个邻居。

- 当您以集中式执行此算法执行此算法时，诀窍是有效地计算2-HOP邻居。我可以从O（n^3）获得的最好的方法是通过矩阵乘法到O（n^2.37）。

- 我真的很想知道最后一个解决方案的近似值是什么。

我喜欢施泰纳树的启发式方法的参考：施泰纳树问题，黄弗兰克；理查兹·达纳（Richards Dana）1955年 - 冬季帕维尔（Winter Pawel）1952年

Answer 4

您可以尝试执行以下操作：

1. 创建一个 最小的顶点覆盖 对于所需的节点 N.

2. 将这些（可能没有连接的）子图击中成“大”节点。也就是说，对于每个子图，将其从图表中删除，然后用新节点替换。称这套节点 N'.

3. 在最小的顶点覆盖节点中 N'.

4. “解开”节点 N'.

不确定它是否在某些特定的边界内给您近似。您甚至可以欺骗算法来做出一些真正愚蠢的决定。