THIS IS A TREE
A connected graph with no circuits.
THIS IS NOT A TREE
This graph contains a circuit.
TREE
Any graph that is connected AND has no circuits is called a Tree.
|
|
THIS IS A TREE |
THIS IS NOT A TREE |
SPANNING TREE
A tree inside of a connected graph that includes every vertex of the original graph is
called a Spanning Tree.
 |
 |
| The tree (represented by the blue edges) within the above connected graph IS a SPANNING TREE since it is a tree and it includes every vertex of the graph. | The tree (represented by the blue edges) within the above connected graph IS NOT a SPANNING TREE since it does not include every vertex of the graph. |
MINIMUM SPANNING TREE
In a weighted connected graph, a spanning tree with the least total weight is called a
Minimum Spanning Tree.