包含给定节点集的最小连通子图 [英] minimum connected subgraph containing a given set of nodes

问题描述

我有一个未加权的连通图.我想找到一个连接的子图，它肯定包含一组特定的节点，并且尽可能少的额外.这怎么可能实现?

为了以防万一，我会用更精确的语言重申这个问题.令 G(V,E) 是一个未加权、无向、连通图.设 N 是 V 的某个子集.找到 G(V,E) 的最小连通子图 G'(V',E') 使得 N 是 V' 的子集的最佳方法是什么?

近似值很好.

解决方案

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

>

1. 将您的输入图G(V, E) 转换为加权图G'(N, D)，其中N 是要覆盖的顶点子集，D 是原始图中相应顶点之间的距离(路径长度).这会将您不需要的所有顶点折叠"为边.

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

3. 通过以下过程展开"最小生成树:对于最小生成树中的每条边d，取图G中的相应路径，并将路径上的所有顶点(包括端点)添加到结果集 V' 和路径中的所有边到结果集 E'.

这个算法很容易被绊倒以给出次优解决方案.示例案例:等边三角形，其中顶点位于三角形的角、边的中点和三角形的中间，以及沿边和从角到三角形中间的边.为了覆盖角，选择三角形的单个中点就足够了，但是这个算法可能会选择边.尽管如此，如果图形是密集的，它应该可以正常工作.

I have an unweighted, connected graph. I want to find a connected subgraph that definitely includes a certain set of nodes, and as few extras as possible. How could this be accomplished?

Just in case, I'll restate the question using more precise language. Let G(V,E) be an unweighted, undirected, connected graph. Let N be some subset of V. What's the best way to find the smallest connected subgraph G'(V',E') of G(V,E) such that N is a subset of V'?

Approximations are fine.

解决方案

I can't think of an efficient algorithm to find the optimal solution, but assuming that your input graph is dense, the following might work well enough:

1. Convert your input graph G(V, E) to a weighted graph G'(N, D), where N is the subset of vertices you want to cover and D is distances (path lengths) between corresponding vertices in the original graph. This will "collapse" all vertices you don't need into edges.

2. Compute the minimum spanning tree for G'.

3. "Expand" the minimum spanning tree by the following procedure: for every edge d in the minimum spanning tree, take the corresponding path in graph G and add all vertices (including endpoints) on the path to the result set V' and all edges in the path to the result set E'.

This algorithm is easy to trip up to give suboptimal solutions. Example case: equilateral triangle where there are vertices at the corners, in midpoints of sides and in the middle of the triangle, and edges along the sides and from the corners to the middle of the triangle. To cover the corners it's enough to pick the single middle point of the triangle, but this algorithm might choose the sides. Nonetheless, if the graph is dense, it should work OK.

这篇关于包含给定节点集的最小连通子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！