包含给定节点集的最小连接子图
我有一个未加权的连通图。我想找到一个连接的子图，该子图肯定包含一组特定的节点，并且尽可能少地包含一些额外的内容。如何做到这一点？
以防万一，我将使用更精确的语言来重申这个问题。令G（V，E）是一个无权，无向的连通图。令N为V的子集。找到G（V，E）的最小连通子图G’（V’，E’）的最佳方法是什么，使N为V’的子集？
近似值很好。
回答：
我想不出一种能找到最佳解决方案的高效算法，但是假设您的输入图很密集，那么下面的方法可能会很好地起作用：
将输入图转换
G(V, E)为加权图G'(N, D)，其中N是您要覆盖的顶点的子集，并且D是原始图中相应顶点之间的距离（路径长度）。这会将所有不需要的顶点“折叠”到边中。计算的最小生成树
G'。通过以下过程“扩展”最小生成树：对于
d最小生成树中的每个边缘，采用图中的相应路径，G并将路径上的所有顶点（包括端点）添加到结果集V'，并将路径中的所有边缘添加到结果集。结果集E'。
该算法很容易跳闸，给出次优的解决方案。示例情况：等边三角形，其中在角，边的中点和三角形的中间有顶点，并且沿边且从角到三角形的中间有边。为了覆盖角，选择三角形的单个中点就足够了，但是此算法可以选择边。尽管如此，如果图形密集，它应该可以正常工作。
以上是 包含给定节点集的最小连接子图 的全部内容， 来源链接： utcz.com/qa/429865.html
