Spanning Tree

A Spanning Tree is a subgraph of an undirected graph G that includes all of the vertices of G that is a tree graph.

• See: Minimum Spanning Tree, Tree (Graph Theory), Connected Graph, #Spanning Forests.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Spanning_tree Retrieved:2015-12-13.
  • In the mathematical field of graph theory, a 'spanning tree T of an undirected graph G is a subgraph that includes all of the vertices of G that is a tree. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (but see Spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself).

---