Question

a. What is a spanning tree of a simple graph?

b. Which simple graphs have spanning trees?

c. Describe at least two different applications that require that a spanning tree of a simple graph be found.

Short answer

a. A spanning tree of a simple graph \({\bf{G}}\) is a subgraph of \({\bf{G}}\) that is a tree and that contains all vertices of \({\bf{G}}\).

b. Connected graphs

c. Answers could vary

Step-by-step solution

Definition

A tree is an undirected graph that is connected and that does not contain any simple circuits.

A graph is connected if there exists a path between every pair of vertices.

Spanning tree

A spanning tree of a simple graph \({\bf{G}}\) is a subgraph of \({\bf{G}}\) that is a tree and that contains all vertices of \({\bf{G}}\).

Connected tree

A simple graph has a spanning tree if the graph is connected, because if the graph is not connected, then it is not possible for a subgraph to become connected.

Note: If the simple graph contains simple circuits, then a spanning tree can exist (by deleting an edge from a circuit in the graph until we obtain no more simple circuits).

Communication networks

Communication networks

For example, if a communication company wants to reduce its costs on communication links of a network, then the company could be interested in a spanning tree such that everybody can be linked with all other people and such that the company can reduce its costs as much as possible (by avoiding the possibility of creating simple circuits).

Roads between cities

For example, a company that needs to make sure that all towns in its neighborhood are connected by a paved road might be interested in a spanning tree if it wants to reduce the cost of paving those roads (or if the client was to reduce the costs). The costs can then be minimized, by making sure that there are no circuits (since a circuit will lead to an extra stretch of road to be paved, while there already would have been paved roads that could be used to travel between the two towns).