Spanning Trees

Let G = (VE) be a connected graph in which each edge (uv$ \in$E has an associated cost C(uv).

 
Spanning Tree for G is a subgraph of G that it is a free tree connecting all vertices in V. The cost of a spanning tree is the sum of costs on its edges.
 
spanning1
 
 
Minimum Spanning Tree
An MST of G is a spanning tree of G having a minimum cost.
 
spanning2
Rate this post

Leave a Reply