minimum spanning trees.:

Minimum Spanning Tree: A spanning tree is a subgraph of G (where G is undirected connected graph), is a tree, and contains all the vertices of G. A minimum spanning tree is a spanning tree, but has weights associated with the edges, and the total weight of the tree (the sum of the weights of its edges) is at a minimum. A minimum spanning tree should satisfy the following conditions.

· It should be a sub-graph of the main graph (say ‘G’)

· It should have all the vertices of ‘G’

· The number of edges should be n-1, and there should not be any cycle.

· The total weight of the tree should be least.

For, example consider the following graphs

There are two different algorithms to find out minimum spanning tree:

1. Kruskal algorithm

2. Prim algorithm.

Kruskal's Algorithm: Take a graph with 'n' vertices, keep adding the shortest (least weight) edge, while avoiding the creation of cycles, until (n - 1) edges have been added. The order, in which the edges are chosen, does not matter if two or more edges may have the same cost. Different minimum spanning trees may result, but they will all have the same total weight, which will always be the minimum weight.

Prim's Algorithm: It starts at any vertex in a graph (vertex A, for example), and finds the least weight vertex (vertex B, for example) connected to the start vertex. Now, from either 'A' or 'B', it will find the next least weighted vertex connection, without creating a cycle (vertex C, for example). Now, from either 'A', 'B', or 'C', it will find the next least weighted vertex connection, without creating a cycle, and so on it goes. Eventually, all the vertices will be connected, without any cycles, which results minimum spanning trees.