Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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

share|improve this question
(3) Is this homework? (4) Where did you get stuck? (5) What's a Steiner tree? – Yuval Filmus Feb 9 '12 at 14:41
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. – Herish Feb 9 '12 at 14:51

1 Answer

up vote 0 down vote

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$.

share|improve this answer
For 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. – Herish Feb 10 '12 at 12:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.