gotchaMinor
Difference between spanning tree and a tree?
Viewed 0 times
differencebetweenandspanningtree
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#33959, answer score: 6
Revisions (0)
No revisions yet.