6.2: Networks

A network is a connection of vertices through edges. The internet is an example of a network with computers as the vertices and the connections between these computers as edges.

Definition: Spanning Subgraph

A spanning subgraph is a graph that joins all of the vertices of a more complex graph, but does not create a circuit

Example \(\PageIndex{1}\): Spanning Subgraph

Figure \(\PageIndex{1}\): Map of Connecting Towns

This is a graph showing how six cities are linked by roads. This graph has many spanning subgraphs but two examples are shown below.

Figure \(\PageIndex{2}\): Spanning Subgraph 1

This graph spans all of the cities (vertices) of the original graph, but does not contain any circuits.

Figure \(\PageIndex{3}\): Spanning Subgraph 2

This graph spans all of the cities (vertices) of the original graph, but does not contain any circuits.

Definition: Tree

A tree is a graph that is connected and has no circuits. Therefore, a spanning subgraph is a tree and the examples of spanning subgraphs in Example \(\PageIndex{1}\) above are also trees.

Properties of Trees

1. If a graph is a tree, there is one and only one path joining any two vertices. Conversely, if there is one and only one path joining any two vertices of a graph, the graph must be a tree.
2. In a tree, every edge is a bridge. Conversely, if every edge of a connected graph is a bridge, then the graph must be a tree.
3. A tree with N vertices must have N-1 edges.
4. A connected graph with N vertices and N-1 edges must be a tree.

Example \(\PageIndex{2}\): Tree Properties

Consider the spanning subgraph highlighted in green shown in Figure \(\PageIndex{2}\).

1. Tree Property 1

Look at the vertices Appleville and Heavytown. Since the graph is a tree, there is only one path joining these two cities. Also, since there is only one path between any two cities on the whole graph, then the graph must be a tree.

2. Tree Property 2

Since the graph is a tree, notice that every edge of the graph is a bridge, which is an edge such that if it were removed the graph would become disconnected.

3. Tree Property 3

Since the graph is a tree and it has six vertices, it must have N – 1 or six – 1 = five edges.

4. Tree Property 4

Since the graph is connected and has six vertices and five edges, it must be a tree.

Example \(\PageIndex{3}\): More Examples of Trees

All of the graphs shown below are trees and they all satisfy the tree properties.

Figure \(\PageIndex{4}\): More Examples of Trees

Definition: Minimum Spanning Tree

A minimum spanning tree is the tree that spans all of the vertices in a problem with the least cost (or time, or distance).

Example \(\PageIndex{4}\): Minimum Spanning Tree

Figure \(\PageIndex{5}\): Weighted Graph 1

The above is a weighted graph where the numbers on each edge represent the cost of each edge. We want to find the minimum spanning tree of this graph so that we can find a network that will reach all vertices for the least total cost.

Figure \(\PageIndex{6}\): Minimum Spanning Tree for Weighted Graph 1

This is the minimum spanning tree for the graph with a total cost of 51.

Kruskal’s Algorithm

Since some graphs are much more complicated than the previous example, we can use Kruskal’s Algorithm to always be able to find the minimum spanning tree for any graph.

1. Find the cheapest link in the graph. If there is more than one, pick one at random. Mark it in red.
2. Find the next cheapest link in the graph. If there is more than one, pick one at random. Mark it in red.
3. Continue doing this as long as the next cheapest link does not create a red circuit.
4. You are done when the red edges span every vertex of the graph without any circuits. The red edges are the MST (minimum spanning tree).

Example \(\PageIndex{5}\): Using Kruskal’s Algorithm

Figure \(\PageIndex{7}\): Weighted Graph 2

Suppose that it is desired to install a new fiber optic cable network between the six cities (A, B, C, D, E, and F) shown above for the least total cost. Also, suppose that the fiber optic cable can only be installed along the roadways shown above. The weighted graph above shows the cost (in millions of dollars) of installing the fiber optic cable along each roadway. We want to find the minimum spanning tree for this graph using Kruskal’s Algorithm.

Step 1: Find the cheapest link of the whole graph and mark it in red. The cheapest link is between B and C with a cost of four million dollars.

Figure \(\PageIndex{8}\): Kruskal’s Algorithm Step 1

Step 2: Find the next cheapest link of the whole graph and mark it in red. The next cheapest link is between A and C with a cost of six million dollars.

Figure \(\PageIndex{9}\): Kruskal’s Algorithm Step 2

Step 3: Find the next cheapest link of the whole graph and mark it in red as long as it does not create a red circuit. The next cheapest link is between C and E with a cost of seven million dollars.

Figure \(\PageIndex{10}\): Kruskal’s Algorithm Step 3

Step 4: Find the next cheapest link of the whole graph and mark it in red as long as it does not create a red circuit. The next cheapest link is between B and D with a cost of eight million dollars.

Figure \(\PageIndex{11}\): Kruskal’s Algorithm Step 4

Step 5: Find the next cheapest link of the whole graph and mark it in red as long as it does not create a red circuit. The next cheapest link is between A and B with a cost of nine million dollars, but that would create a red circuit so we cannot use it. Therefore, the next cheapest link after that is between E and F with a cost of 12 million dollars, which we are able to use. We cannot use the link between C and D which also has a cost of 12 million dollars because it would create a red circuit.

Figure \(\PageIndex{12}\): Kruskal’s Algorithm Step 5

This was the last step and we now have the minimum spanning tree for the weighted graph with a total cost of $37,000,000.