In this video, I'll talk about how to find the minimum spanning tree in a network.
Let's see some definitions.
Two nodes are connected if the network contains at least one path between them.
A connected network is a network where every pair of nodes is connected.
A path that begins and ends at the same node is called a cycle.
For a network with n nodes, a spanning tree is a group of n ? 1 arcs that connects all
nodes of the network and contains no cycles.
Let's see some examples.
This is the first example.
Node C and node D are connected.
There is a path from C to D.
The path is C-A-B-D.
Node C and node G are not connected.
We cannot find a path from node C to node G.
There is no cycle.
For example, if we start from node C, we cannot circle back to node C.
This is not a spanning tree because the number of nodes n=7, n-1=6, and the number of arcs
is 5, which is not equal to n-1.
This is the second example.
Node C and node D are connected.
Node C and node G are also connected.
There are cycles.
For example, if we start from node C, we can come back to node C by following the path
C-A-B-D-C.
This is not a spanning tree because the number of nodes n=7, n-1=6, and the number of arcs
is 8, which is not equal to n-1.
This is the third example.
Node C and node D are connected.
Node C and node G are also connected.
In fact, all the nodes are connected.
There is no cycle.
This is a spanning tree because n=7, n-1=6, and the number of arcs is 6, which is exactly
equal to n-1.
With that in mind, now let's see what a minimum spanning tree is.
Given some nodes with the potential undirected arcs and their lengths.
We want to design the network by identifying enough arcs so there is a path between every
pair of nodes and the total length of these arcs is minimized.
The solution to this problem is a minimum spanning tree.
We can use this greedy algorithm to find the minimum spanning tree.
Step1: Select any node arbitrarily, and then connect it to the nearest node.
Step2: Identify one unconnected node that is closest to any connected node, and then
connect these two nodes.
Repeat this step until all nodes are connected.
Ties are broken arbitrarily.
Ties are a signal that there might be multiple minimum spanning trees.
Let's check this example.
There are 7 towns.
They are represented by node A through node G.
Determine under which roads telephone lines should be installed to connect all towns with
a minimum total length of lines.
The potential length accompanied with each potential line is provided in this graph.
Now, let's start from node A. Let's check its direct neighbors, B, C, and D.
The nearest node is node B.
The distance from B to A is 2.
Let's connect A and B. Now let's find one unconnected node that is
closest to A and B.
The direct neighbors are C, D, and E. The closest is node D.
The distance from D to B is 2.
Let's connect B and D. Now let's repeat this step.
Find one unconnected node that is closest to A, B, and D.
The direct neighbors are C, F, and E. The closest is node C. The distance from C
to D is 1.
Let's connect D and C. Now let's repeat this step.
Find one unconnected node that is closest to A, B, C, and D.
The direct neighbors are E and F. The closest is node F. The distance from F
to D is 3.
Let's connect D and F. Repeat this step.
Find one unconnected node that is closest to A, B, C, D, and F.
The direct neighbors are E and G.
The closest is node E. The distance from E to F is 1.
Let's connect F and E. Repeat this step.
Find one unconnected node that is closest to A, B, C, D, E, F.
The closest and only node is G.
The distance from G to E is 5.
Let's connect E and G.
This is the final solution.
It forms a minimum spanning tree.
The total length is the sum of lengths of these included arcs, which is 14.
Okay, that is how to find the minimum spanning tree in a network.
Thanks for watching.