考虑一个加权图 G=(V,E,w)。我们得到一组顶点 V_i 的子集。
斯坦纳森林是一个森林,对于每个顶点子集 V_i 将这个子集中的所有顶点与一棵树连接起来。
示例:只有一个子集 V_1 = V。在这种情况下,Steiner 森林是整个图的生成树。
示例:图 P4(具有 4 个顶点的路径)和两个子集:V_1 = {v1, v4} 和 V_2 = {v2, v3}。此示例的 Steiner 树是整个图。
理论够了。很难找到这样一个重量最小的森林(NP-complete)。你知道任何更快的近似算法来找到这样一个非最优权重的森林吗?