![next](http://lcm.csa.iisc.ernet.in/dsa/next_motif.gif)
![up](http://lcm.csa.iisc.ernet.in/dsa/up_motif.gif)
Next:8.3.1
MST PropertyUp:8.
Undirected GraphsPrevious:8.2.1
Breadth-first search of undirected graph
8.3 Minimum-Cost Spanning Trees
Let G = (V, E) be a connected graph
in which each edge (u, v)
E
has an associated cost C(u, v).
-
A 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.
-
An MST of G is a spanning tree of G having a minimum
cost.
-
See Figure 8.4 for several examples.
Figure 8.4: Spanning trees in a connected graph
![\begin{figure}\centerline{\psfig{figure=figures/Fspan.ps,width=5in}}\end{figure}](img416.gif) |
eEL,CSA_Dept,IISc,Bangalore