含有一组给定的节点最小连接子图 [英] minimum connected subgraph containing a given set of nodes

问题描述

我有一个加权，连接图。我想找到一个连通子是肯定包括一组特定节点，并为一些额外的可能。这怎么可能实现呢？

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?

为了保险起见，我将使用更多的precise语言重述问题。设G（V，E）是一个加权，无向，连接图。设N是V的某个子集，什么是找到最小连通子G'（V'，E'），G（V，E），使得N是V的子集'？

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'?

逼近的罚款。

推荐答案

我想不出一个高效的算法来找到最佳的解决方案，但假设你的输入图形是密集的，下面可能工作不够好：

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. 转换你的输入图形 G（V，E）来加权图 G'（N，D），其中 N 为顶你想覆盖子集和 D 的距离（路径长度）之间对应于原始图的顶点。这将崩溃的所有顶点，你不需要到边缘。

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.

计算的 G'。

展开最小生成树通过下列程序树：每边 D 的最小生成树，拿在图形中的对应路径和路径上添加所有的顶点（包括端点）到结果集 V'和路径，结果所有的边缘设置 E'。

"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屋！