Spanning tree

From Algorithmist
Jump to: navigation, search

Let G=(V,E) be a connected graph. A Spanning Tree of graph G is a subgraph of G with vertex set V and which is itself a Tree. i.e:- simple connected acyclic graph. OR Given a undirected, unweighted, connected graph G, Spanning tree of G is the subgraph that covers all the vertices without forming a loop. If the graph is not connected, it forms a spanning forest.

See Also[edit]