Question

Consider the cities B,C,D,E,F,G
The costs of the possible roads between cities are given below:

c(B,F) = 11
c(B,G) = 10
c(C,G) = 8
c(D,E) = 12
c(D,F) = 13
c(E,F) = 9
c(E,G ) = 7

What is the minimum cost to build a road system that connects all the cities?

Answer 1

To solve this problem we will use Kruskal's Algorithm (Graph Theory)

We will convert the problem of finding the minimum cost to build a road system that connects all the cities into graph theory and then using Kruskal's Algorithm we will find minimum spanning tree.

1) Spanning Subgraph:

A spanning subgraph of a graph G is H if vertex set of H is same as vertex set of G and edge set of H is subset of edge set of G.

i. e. and

2) Spanning Tree:

A spanning tree of G is a spanning subgraph of a connected graph G.

3) Minimum Spanning tree:

A weighted spanning tree with minimum weight is called minimum weighted spanning tree.

4) Kruskal's Algorithm:

Step 1: Choose e₁ in graph G such that weight of an edge is as small as possible. where e₁ is not a loop.

Step 2: If edges e₁, e₂, . . . e_i have been choosen then choose edge e_i+1 such that

a) G<e₁, e₂, . . . e_i+1> is acyclic.

b) weight of e_i+1 is the smallest where ei+1 is not a loop.

Step 3: If G has p vertices stop after p-1 edges have been choosen otherwise go to step 2

Thus here we will consider cities as vertices and road between two cities means edge between those two vertices and cost means the weight of that edge.

Thus following is the corresponding graph.

For this graph we will find the minimum weighted spanning tree by applying Kruskal's Algorithm as follows.

In the V step we haven't choosen edge BF though its weight is minimum(11) because it will create a cycle BFEGB in the graph.

Graph in the step V] is the final presentation of all the cities connected by roads.

and weight of the graph = weight of edges in the graph(step V)

= 7 + 8 + 9 + 10 + 12

= 46

Thus 46 is the minimum cost to build a road system that connects all the cities.