4
$\begingroup$

Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem relevant to computer science. My professor in my algorithms class makes the distinction between a spanning tree and a regular tree; but never says what the difference really is. The only thing I notice is that he uses the word spanning tree when he is talking about graphs.

Is a spanning tree simply when a graph takes on a tree structure? In other words, the raw data structure under the hood is a graph, but it takes on some characteristics of a tree? Or is it something else?

Improve this question
$\endgroup$
1
  • $\begingroup$ What research have you done? This is covered in standard algorithms textbooks; in particular, most algorithms textbooks that cover minimum spanning trees will define the term "spanning tree". Have you looked there? We expect you to do a significant amount of research and self-study before asking. $\endgroup$ Commented Dec 7, 2014 at 19:12

3 Answers 3

Reset to default
6
$\begingroup$

Given a graph $G$, a spanning tree is a subgraph of $G$ that (i) is a tree, and (ii) has all the vertices in $G$.

There can be many spanning trees for $G$. If you put weights on the edges, one of these spanning trees will have a minimal sum of weights. This is the minimal spanning tree.

Regular (sub)tree is just subgraph which is a tree - it doesn't have all the nodes in $G$: it satisfies property (i) above, but not necessarily property (ii).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Additionally, trees exist without relation to a graph at all. $\endgroup$ Commented Dec 7, 2014 at 10:58
  • $\begingroup$ @Raphael: Except the (boring) trivial relation that trees are (degenerate) graphs. (Just like lists are degenerate trees.) $\endgroup$ Commented Dec 7, 2014 at 11:26
  • $\begingroup$ @JörgWMittag Trees aren't at all degenerate! The only graph that's widely described as degenerate is the one that has no vertices. Raphael's point is (I think) that the question asks for comparisons of trees versus spanning trees: the phrase "spanning tree" only makes sense as a subgraph of some other graph, whereas talking about trees doesn't require you to first define some other graph. $\endgroup$ Commented Nov 22, 2017 at 12:59
1
$\begingroup$

There are several species of trees.

A spanning tree in a graph is an undirected tree connecting all the nodes in a graph. Undirected trees on their own are graphs with the property the graph is connected and does not have cycles.

Trees as often used in computer science have a root, the node usually depicted at the top. They also are considered as directed graphs, all edges pointing downwards, away from the root. This direction sometimes is left implicit in pictures.

Binary trees are a class of their own. A single child may either be "left" or "right", which differs from ordinary directed trees, as in those trees we do not distinguish left and right.

So, sometimes we distinguish trees for technical reasons. This is not always explicitly stated, and the terminology for all trees is rather similar.

Improve this answer
$\endgroup$
0
$\begingroup$

In graph theory, a substructure of a graph $G$ is said to be spanning if it includes every vertex of $G$. So a spanning subgraph is one that includes every vertex. This is equivalent to say that it was made only by deleting edges, whereas subgraphs in general are made by deleting edges and vertices. Similarly, a spanning matching would be what everybody actually calls a perfect matching.

Hence, a spanning tree of a graph $G$ is a subgraph of it that is a tree (connected and contains no cycles) and is spanning (includes every vertex of $G$).

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.