(1) Given a connected graph G of p vertices. Is it possible to find randomly a tree T of G then assume the end vertices of T to be a set S having Steiner tree T. (2) Given a set S of k-vertices, is it possible to construct a graph G of p vertices(p>k) containing S such that G contains a Steiner tree T of S. Is the above problems are equivalent to the Steiner tree problem?
Graph Theory and Minimum Spanning Trees
0
$\begingroup$
graph-theory
-
0(3) Is this homework? (4) Where did you get stuck? (5) What's a Steiner tree? – 2012-02-09
-
0I faced the problem during my work in graph theory. The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. – 2012-02-09