Tree: A minimally connected network is called a tree. If there are n nodes in a network, it will be a tree if the number of edges = n-1.

**Minimum spanning tree
algorithm**

**Problem :
**Given a
connected network with weights assigned to the** **edges, it is required to find out a tree whose nodes are the same
as those of the network.

The weight assigned to an edge may be regarded as
the distance between the two nodes with which the edge is incident.

**Algorithm**

The problem can be solved with
the help of the following algorithm.

The procedure consists of
selection of a node at each step.

**Step 1**

First select any node in the
network. This can be done arbitrarily.

We will start with this node.

**Step 2**

Connect the selected node to the
nearest node.

**Step 3**

Consider the nodes that are now connected. Consider
the remaining nodes. If there is no node remaining, then stop. On the other
hand, if some nodes remain, among them find out which one is nearest to the
nodes that are already connected. Select this node and go to Step 2.

Thus the method involves the repeated application
of Steps 2 and 3. Since the number of nodes in the given network is finite, the
process will end after a finite number of steps. The algorithm will terminate
with step 3.

**How to
break ties**

While applying the above algorithm, if some nodes
remain in step 3 and if there is a tie in the nearest node, then the tie can be
broken arbitrarily.

As a consequence of tie, we may end up with more
than one optimal solution.
Tags : Operations Management - Network Problems

Last 30 days 117 views