7.2 Minimum-Cost spanning trees
Let G=(V,E) be an undirected connected graph. A sub-graph t = (V,E1) of G is a spanning tree of G if and only if t is a tree.
Above figure shows the complete graph on four nodes together with three of its spanning tree.
Spanning
trees have many applications. For example, they can be used to obtain
an independent set of circuit equations for an electric network. First,
a spanning tree for the electric http://www.vyomworld.com/gate/cs/ada/7.2.asp# - Another
application of spanning trees arises from the property that a spanning
tree is a minimal sub-graph G’ of G such that V(G’) = V(G) and G’ is
connected. A minimal sub-graph with n vertices must have at least n-1
edges and all connected graphs with n-1 edges are trees. If the nodes
of G represent cities and the edges represent possible communication
links connecting two cities, then the minimum number of links needed to
connect the n cities is n-1. the spanning trees of G represent all
feasible choice.
In
practical situations, the edges have weights assigned to them. Thse
weights may represent the cost of construction, the length of the link,
and so on. Given such a weighted graph, one would then wish to select
cities to have minimum total cost or minimum total length. In either
case the links selected have to form a tree. If this is not so, then
the selection of links contains a cycle. Removal of any one of the
links on this cycle results in a link selection of less const
connecting all cities. We are therefore interested in finding a
spanning tree of G. with minimum cost since the identification of a
minimum-cost spanning tree involves the selection of a subset of the
edges, this problem fits the subset paradigm.
7.2.1 Prim’s Algorithm
A
greedy method to obtain a minimum-cost spanning tree builds this tree
edge by edge. The next edge to include is chosen according to some
optimization criterion. The simplest such criterion is to choose an
edge that results in a minimum increase in the sum of the costs of the
edges so far included. There are two possible ways to interpret this
criterion. In the first, the set of edges so far selected form a tree.
Thus, if A is the set of edges selected so far, then A forms a tree.
The next edge(u,v) to be included in A is a minimum-cost edge not in A
with the property that A U {(u,v)} is also a tree. The corresponding
algorithm is known as prim’s algorithm.
For
Prim’s algorithm draw n isolated vertices and label them v1, v2,
v3,…vn. Tabulate the given weights of the edges of g in an n by n
table. Set the non existent edges as very large. Start from vertex v1
and connect it to its nearest neighbor (i.e., to the vertex, which has
the smallest entry in row1 of table) say Vk. Now consider v1 and vk as
one subgraph and connect this subgraph to its closest neighbor. Let
this new vertex be vi. Next regard the tree with v1 vk and vi as one
subgraph and continue the process until all n vertices have been
connected by n-1 edges.
Consider the graph shown in http://www.vyomworld.com/gate/cs/ada/7.2.asp# -
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
V1 |
- |
10 |
16 |
11 |
10 |
17 |
V2 |
10 |
- |
9.5 |
Inf |
Inf |
19.5 |
V3 |
16 |
9.5 |
- |
7 |
Inf |
12 |
V4 |
11 |
Inf |
7 |
- |
8 |
7 |
V5 |
10 |
Inf |
Inf |
8 |
- |
9 |
V6 |
17 |
19.5 |
12 |
7 |
9 |
- |
Start
with v1 and pick the smallest entry in row1, which is either (v1,v2) or
(v1,v5). Let us pick (v1, v5). The closest neighbor of the subgraph
(v1,v5) is v4 as it is the smallest in the rows v1 and v5. The three
remaining edges selected following the above procedure turn out to be
(v4,v6) (v4,v3) and (v3, v2) in that sequence. The resulting shortest
spanning tree is shown in fig 7.4. The weight of this tree is 41.5.
7.2.3 Kruskal’s Algorithm:
There
is a second possible interpretation of the optimization criteria
mentioned earlier in which the edges of the graph are considered in
non-decreasing order of cost. This interpretation is that the set t of
edges so far selected for the spanning tree be such that it is possible
to complete t into a http://www.vyomworld.com/gate/cs/ada/7.2.asp# - The
Kruskal algorithm can be illustrated as folows, list out all edges of
graph G in order of non-decreasing weight. Next select a smallest edge
that makes no circuit with previously selected edges. Continue this
process until (n-1) edges have been selected and these edges will
constitute the desired shortest spanning tree.
For fig 7.3 kruskal solution is as follows,
V1 to v2 =10
V1 to v3 = 16
V1 to v4 = 11
V1 to v5 = 10
V1 to v6 = 17
V2 to v3 = 9.5
V2 to v6 = 19.5
V3 to v4 = 7
V3 to v6 =12
V4 to v5 = 8
V4 to v6 = 7
V5 to v6 = 9
The above path in ascending order is
V3 to v4 = 7
V4 to v6 = 7
V4 to v5 = 8
V5 to v6 = 9
V2 to v3 = 9.5
V1 to v5 = 10
V1 to v2 =10
V1 to v4 = 11
V3 to v6 =12
V1 to v3 = 16
V1 to v6 = 17
V2 to v6 = 19.5
Select
the minimum, i.e., v3 to v4 connect them, now select v4 to v6 and then
v4 to v5, now if we select v5 to v6 then it forms a circuit so drop it
and go for the next. Connect v2 and v3 and finally connect v1 and v5.
Thus, we have a minimum spanning tree, which is similar to the figure
7.4.
click here for more details:
http://www.vyomworld.com/gate/cs/ada/7.2.asp - http://www.vyomworld.com/gate/cs/ada/7.2.asp
|