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.

Ultimate Blogger Theme By Buywptemplates

Done, but shows prim's algorithm (starting from a node) instead of kruskal's (starting from an edge)

You r the man

Hi Guys, please comment and let me know what you think about this Operations Research Open Course. Your feedback is really appreciated. If you enjoy the video, please subscribe and share. All my replies here are only related to the content in my own videos. I am afraid I won't be able to answer other questions. Thanks for your understanding.

I really appreciate that you put this course together and uploaded the videos. Thank you!