Reference no: EM131585528

Question: Show that every graph, connected or not, has a spanning forest.

Let's move to reality for a little while (though it will still be abstracted reality). Why would we want to find a spanning tree? Suppose that we need to build an oil pipeline: it transports oil from several wells to a processing center, and it must be built parallel to existing roads so that in the event of a leak it can be reached and repaired quickly. It will be cheapest if the total length of pipeline is as short as possible. So, there is a graph in which vertices are oil wells and a processing center and in which edges are roads. In this case, distances along roads matter, as well as which roads connect which oil wells. More generally, we may have situations in which costs of transport or lengths of cable or amounts of energy used are important, in addition to adjacency. Therefore, whatever physical network we have that is represented by a graph will have labels on its edges to denote the costs or distances or energies. These are referred to as weights, and such a labeled graph is called a weighted graph. (Technically it is edge-weighted; one could, after all, weight vertices.) Figure shows a weighted graph and three of its spanning trees.