斯坦纳树暂记

本文主要是介绍斯坦纳树暂记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考虑著名的Steiner Tree问题：

问题描述

$$\begin{gathered} 设G（V,E,W）是一个无向带权连通图 \\ (V是顶点的集合，E是边的集合，W是边上权重的集合，顶点v_i,v_j\in V，由v_i,v_j构成的边记为e_{ij}或者e_{ji},边上的权重记为w_{ij}或者w_{ji},且w_{ij}=w_{ji},w_{ij}>0)。 \end{gathered}$$
设 R 是 V 的一个子集，即 R ⊆ V ，在 G 中求一颗生成树 T ，使得 T 包含 R 中所有顶点，且生成树 T 的权重最小 （生成树 T 的权重是指构成 T 的所有边权重之和），即 m i n { ∑ e i j ∈ T w i j } 权重最小的生成树 T 称为 G 关于 R 的 S t e i n e r T r e e . 设R是V的一个子集，即R⊆V，在G中求一颗生成树T，使得T包含R中所有顶点，且生成树T的权重最小\\ （生成树T的权重是指构成T的所有边权重之和），即 min\{\sum_{e_{ij}\in T} w_{ij}\}\\ 权重最小的生成树T称为G关于R的Steiner Tree. 设R是V的一个子集，即R⊆V，在G中求一颗生成树T，使得T包含R中所有顶点，且生成树T的权重最小（生成树T的权重是指构成T的所有边权重之和），即min{eij​∈T∑​wij​}权重最小的生成树T称为G关于R的SteinerTree.

NPC证明

$$方法：bytransforminganotherknownNP-completeproblemtoit$$
show that a problem Π is NP-complete:

1. show than Π is in NP;\
2. select a known NP-complete problem Π0;
3. construct a transformation f from Π0 to Π;
4. prove that f is a polynomial transformation.

Steiner Tree is in NP

假设存在正确解T，我们可以在多项式时间内验证：
T是一棵树，是联通的且不存在环
T包含顶点集合R的所有元素
树的边数不超过k

XKC问题 集合覆盖问题(选择最少的集合，覆盖所有的元素)

添加链接描述
XKC中k的意思是每个小集合只有三个元素

最小生成树是在给定的点集和边中寻求最短网络使所有点连通
而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小

参考

拓展

• Steiner Minimum Tree Problem,SMTP
• 最小斯坦纳树

这篇关于斯坦纳树暂记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---