Embedded Files
Minimal Spanning Trees.
Minimal Spanning Trees.
Minimum Spanning Trees (MST).
Minimum Spanning Trees (MST).
A graph is a tree if and only if it is connected and does not have a cycle in it. A tree must have at least two vertices of degree one or at least two edges with one of their vertices not connected to another vertex. In general, if the number of vertices of a tree is n, it must have n - 1 edges. A collection of trees is called a forest.
Let us examine each of the graphs in Figure 7.20.
Graph 1 is connected and has vertices A, C, E, and F that are of degree 1. Also, it has 6 vertices and 5 edges; hence, it is a tree.
Graph 2 is not connected since vertex C is isolated or not connected to any other vertex; hence, It
is not a tree.
Graph 3 is connected, but A, B, and C form a cycle in the graph, and there are 6 vertices and & edges; hence, it is not a tree.
A subgraph of a connected graph that is a tree is a spanning tree.
A subgraph H is a spanning tree of a graph G if the following conditions are satisfied:
i. His a tree.
ii. H contains all the vertices of G.
Circuit rank is the minimum number of edges that must be removed from a graph so as to eliminate all cycles in the graph. If m is the number of edges of the graph and n is the number of vertices, and y (gamma) is the circuit rank, then y = m - (n - 1).
The number of spanning trees in a complete graph can also be determined.
Cayley's Theorem
The number of labeled spanning trees of the complete graph K, is n°2.
Let the number of spanning trees be (G). Using Cayley's theorem for the graph G in Figure 7.21 where m = 8 and n = 6, s(G = 662 = 64 = 1296 and y =8 - (6 - 1) =8-5-3.
There are 1296 spanning trees in G. Each spanning tree can be obtained by deleting or removing 3 edges as determined by y.
Example 2:
Solution:
The graph has circuit rank y = 3- (3-1) =3-2 = 1. This means one edge must
be deleted or removed from the graph to break the cycle.
The number of spanning trees from Cayley's theorem is 3^(3-2) = 3^1 = 3. This means
that there can only be 3 spanning trees.
The three spanning trees are shown in Figure 7.23. Each spanning tree is obtained by deleting or removing one edge from the complete graph K, in Figure 7.22.
The Minimum Spanning Tree (MST) is a spanning tree of a graph with the least sum of edge weights.
There are algorithms for finding a minimum spanning tree for a weighted graph. Only the Kruskal's algorithm and the Prim's algorithm will be discussed here. They are both referred to as greedy algorithms as every stage of the selection process involves the cheapest or the one with the least weight. Both algorithms can be used to find a spanning tree in a graph that includes every vertex of that graph such that the total weight of the edges in the spanning tree is minimized. The difference between the two is in the selection of the first vertex.
Kruskal's Algorithm
Start with a vertex whose edge formed with another vertex that has the least weight. Mark this edge.
Proceed to another edge with the next lowest weight but making sure that the selected edge will not form a cycle in the graph. If it does, go to the next edge with the lowest weight and mark this edge.
Continue with the process until all the vertices have been traversed.
The minimum spanning tree is determined by adding the weights of its edges.
Notes:
If a vertex leads to two (or more) edges of the same weight, choose any of the edges making sure no cycle will be formed and that the next edge will have the lowest weight.
Kruskal's algorithm was formulated in 1956 by Joseph Kruskal and first appeared in the Proceedings of the American Mathematical Society.
Prim's Algorithm
1. Select any vertex and mark it. From this vertex choose the edge connected to it with the lowest weight and mark this edge and the end vertex.
2. Choose from among the unmarked edges the one with the lowest weight. Mark this edge and the end vertex. Make sure the selected edge will not form a cycle in the graph.
3. Continue and repeat the process until all the vertices are marked.
4. The minimum spanning tree is determined by adding the weights of its edges.
Notes:
1. If a vertex connects to two (or more) edges of the same weight, randomly choose any of the edges and mark this edge and the end vertex.
2. Prim's algorithm is named after Robert C. Prim who rediscovered and republished the algorithm in 1957. It was republished also by Edger W. Dijkstra in 1959. The algorithm was originally developed in 1930 by Vojtëck Jarnik, a Czech mathematician. For these reasons, the algorithm is also referred to as Prim-Jarnik's algorithm, Prim-Dijkstra algorithm,
DJP algorithm, or Jarnik's algorithm.
Example 3
To illustrate MST using Figure 7.22, weights representing time in minutes to leave home for errands in two places will be assigned as follows: A - home, B - church, C - pharmacy.
It takes 5 minutes to go from home to the church, 7 minutes from the church to the pharmacy, and 8 minutes from the pharmacy back to home.
A -> B = 5,B -> C = 7,C -> A = 8
The objective of the problem is to leave home and do the two errands at the shortest time possible.
Solution:
1. Applying Kruskal's algorithm, choose A to B. Since weight of AB is lowest. From B, there is only one edge BC to use to get to C. So by MST, it will take 5 + 7 = 12 minutes taking the route ABC to do the errands. This is actually the second spanning tree in Figure 7.23. Observe that if you take the route ACB, it will take 8 + 7 = 15 minutes to do the errands, which is a longer time by 3 minutes. This is the second spanning tree in Figure 7.23.
2. Applying Prim's algorithm, choose vertex B. Since BA has less weight than BC, mark B and edge BA. The unmarked edges are BC and AC with BC having the lower weight, so also mark BC. The route then is ABC, the same as obtained in 1) where ABC forms the minimum spanning tree. Observe that if the random vertex chosen is C, you mark C and vertex BC since weight of BC is lower than the weight of AC. The unmarked edges then are AB and AC, with AB having the lower weight, which you will also mark. You obtain the same route ABC as the minimum spanning tree.
Page updated
Report abuse