(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
-
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
1 Answers
1
The questions are very unclear. I'll make some interpretations and give an answer. If my interpretations are incorrect, please edit your question to clarify.
(1) Suppose $G$ is a complete graph on $p=4$ vertices at the corners of a square. If $T$ is any subtree with 3 or 4 vertices then $T$ will not be a Steiner tree for its "end vertices".
(2) Given $S$, the Steiner tree $T$ of $S$ is itself a graph containing a Steiner tree of $S$.
-
0For part 2 of the question, I want to start with a set S of k-vertices, then find a tree T which connect these vertices then construct a bigger super graph G that contains T as a Steiner tree of S. This problem may be the inverse side of the Steiner tree problem of finding a Steiner tree of a given subset of vertices of a given graph. – 2012-02-10