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

我有一个未加权的连通图。我想找到一个连接的子图,该子图肯定包含一组特定的节点,并且尽可能少地包含一些额外的内容。如何做到这一点?

以防万一,我将使用更精确的语言来重申这个问题。令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'

该算法很容易跳闸,给出次优的解决方案。示例情况:等边三角形,其中在角,边的中点和三角形的中间有顶点,并且沿边且从角到三角形的中间有边。为了覆盖角,选择三角形的单个中点就足够了,但是此算法可以选择边。尽管如此,如果图形密集,它应该可以正常工作。

以上是 包含给定节点集的最小连接子图 的全部内容, 来源链接: utcz.com/qa/429865.html

回到顶部