0
$\begingroup$

(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?

  • 0
    (3) Is this homework? (4) Where did you get stuck? (5) What's a Steiner tree?2012-02-09
  • 0
    I 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