Minimum Spanning Trees

A spanning tree is a set of edges that connect all nodes of a graph but does not have any superfluous edges. The problem of finding a spanning tree (usually of minimum cost) is common in communication networks where it is important that every node can communicate with all other nodes (not necessarily directly). It also occurs in distribution networks (e.g., supply houses of a block with water through a connected network of pipes, electricity networks).