Page 290 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows

function will be unbounded. However, in some tasks, we are able to assign finite capacity to each Notes
uncapacitated edge escaping such a situation.

14.3 Minimum Spanning Tree

A minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight
less than or equal to the weight of every other spanning tree. More generally, any undirected
graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum
spanning trees for its connected components.

One example would be a cable TV company laying cable to a new neighborhood. If it is constrained
to bury the cable only along certain paths, then there would be a graph representing which points
are connected by those paths. Some of those paths might be more expensive, because they are
longer, or require the cable to be buried deeper; these paths would be represented by edges with
larger weights.

A spanning tree for that graph would be a subset of those paths that has no cycles but still
connects to every house.
There might be several spanning trees possible. A minimum spanning tree would be one with
the lowest total cost.
Figure 14.9: Minimum Spanning Tree

0 2 1 0 1
5
1 6 1 2 1 1 2

3 3
4 3 4 3
1 1
Graph G A Minimum Spanning Tree
Tree for G
(Total cost = 6)

A graph may have many spanning trees; for instance the complete graph on four vertices has
sixteen spanning trees:
Figure 14.10: A Complete Graph with four Vertices

0 0

X

0 0

LOVELY PROFESSIONAL UNIVERSITY 285