Paper – Discrete Mathematics
TREES
PART II
Hello friends, welcome back to our session on trees.
In today’s session we will continue with the discussion on trees. We will focus on the spanning trees and minimum spanning trees today.
Before going to the new topics, let us review the topics which we have covered in the last session.
Trees have a number of special properties as follows:
a) It is obvious, from the constructive process of building all possible trees step by step from the simplest tree (one vertex, no edges) that a tree with n vertices has exactly n - 1 edges.
b) When a new vertex and edge is added to a tree, no cycle is created (since the new edge joins an existing vertex to a new vertex) and the tree remains connected.
c) There is exactly one path from any vertex in a tree to any other vertex – if there were two or more paths between any two vertices then the two paths would form a cycle and the graph would not be a tree.
d) Because there is exactly one path between any two vertices then there is one (and only one) edge joining any two adjacent vertices. If this edge is removed, the graph is no longer connected (and so is not a tree). So the removal of any edge from a tree disconnects the graph.
e) Since there is a path between any two vertices, if an edge is added to the tree joining two existing vertices then a cycle is formed comprising the existing path between the two vertices together with the new edge.
All these properties can be used to define a tree.
Now let’s come to the new topic
Module - 1
1. Spanning trees
Definition 1
Let G be a simple graph. A spanning tree of G is a sub graph of G that is a tree containing every vertex of G. Large and complex graphs may have many spanning trees.
The figure shows the complete graph K5 and several possible spanning trees.
A spanning tree may be found by the building- up method or the cutting-down method. The building up algorithm is:
Select edges of the graph, one by one, in such a way that no cycles are created; repeating until all vertices are included.
And the cutting-down method is:
Choose any cycle in the graph and remove one of its edges; repeating until no cycles remain.
Example 1:
Find a spanning tree of the simple graph G shown in Figure shown.
Solution: The graph G is connected, but it is not a tree because it contains simple circuits. First, Remove the edge {a, e}. This eliminates one simple circuit, and the resulting subgraph is still connected and contains every vertex of G. Next remove the edge {e, b} to eliminate the second simple circuit. Finally, remove edge {c, g} to produce a simple graph with no simple circuits. This subgraph is a spanning tree, because it is a tree that contains every vertex of G; which is given in this figure.
Theorem 1
A simple graph is connected if and only if it has a spanning tree.
Proof
First, suppose that a simple graph G has a spanning tree t. T contains every vertex of G. Also, there is a path in T between any two of its vertices. Because T is a subgraph of G, there is a path in G between any two of its vertices. Hence, G is connected.
Conversely, suppose that G is connected. If G is not a tree, it must contain a simple circuit. Remove an edge from one of these simple circuits. The resulting subgraph has one fewer edge but still contains call the vertices of G and is connected. This subgraph is still connected because when two vertices are connected by a path containing the removed edge, they are connected by a path not containing this edge. We can construct such a path by inserting into the original path, at the point where the removed edge once was, the simple circuit with this edge removed. If this subgraph is not a tree, it has a simple circuit; so as before, remove an edge that is in a simple circuit. Repeat this process until no simple circuit remain. This is possible because there are only a finite number of edges in the graph. The process terminates when no simple circuit remains. A tree is produced because the graph stays connected as edges are removed. This tree is a spanning tree because it contains every vertex of G. This completes the proof.
Spanning trees are important in data networking.
Example 2: IP Multicasting
Spanning trees plays an important role in multicasting over Internet Protocol (IP) networks. With IP multicasting, a computer sends a single copy of data over the network, and as data reaches intermediate routes, the data are forwarded to one or more other routers so that ultimately all receiving computers in their various subnet works receive these data. For data to reach receiving computers as quickly as possible, there should be no loops in the path that data take through the network. That is, once data have reached a particular router, data should never return to this router. To avoid loops, the multicast routers use network algorithms to construct a spanning tree in the graph that has the multicast source, the routers, and the sub networks containing receiving computers as vertices, with edges representing the links between computers and/or routers. The root of this spanning tree is the multicast source. The sub networks containing receiving computers are leaves of the tree.
Definition 2
In many applications of symmetric connected relations, the (undirected) graph of the relation models a situation in which the edges as well as the vertices carry information.
A weighted graph is a graph for which each edge is labeled with a numerical value called its weight.
Module - 2
2. Minimum Spanning trees
The Figure shows a number of possible spanning trees for the graph shown.
Definition 2:
A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges.
Where do we apply the concept of minimum spanning trees?
The standard application is to a problem like phone network design. For example, you have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn't a tree you can always remove some edges and save money.
A less obvious application is that the minimum spanning tree can be used to approximately solve the travelling salesman problem which we have come across in the chapter on graphs. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.
Note that if you have a path visiting all points exactly once, it's a special kind of tree. If you have a path visiting some vertices more than once, you can always drop some edges to get a tree. So in general the Minimum Spanning Tree (MST) weight is less than the Travelling Salesman Problem (TSP) weight, because it's a minimization over a strictly larger set.
Module - 3
ALGORITHM FOR FINDING MINIMUM SPANNING TREES
Let’s see two algorithms for constructing minimum spanning trees. Both proceed by successively adding edges of smallest weight from those edges with a specified property that have not already been used. Both are greedy algorithms that produce optimal solutions.
The first algorithm that we will discuss was given by Robert Prim in 1957. To carry out Prim’s algorithm, begin by choosing an edge with smallest weight, putting it into the spanning tree. Successively add to the tree edges of minimum weight that are incident to a vertex already in the tree and not forming a simple circuit with those edges already in the tree. Stop when (n-1) edges have been added.
The choice of an edge to add at a stage of the algorithm is not determined when there is more than one edge with the same weight that satisfies the appropriate criteria. We need to order the edges to make the choices deterministic.
Theorem 2: Prim’s algorithm produces a minimum spanning tree for every connected weighted graph.
Let G be a connected weighted graph. Suppose that the successive edges chosen by Prim's algorithm are eI, e2, . . . , en-I. Let S be the tree with eI, e2, . . . , en-I as its edges, and let Sk be the tree with eI, e2, . . . , ek as its edges. Let T be a minimum spanning tree of G containing the edges eI, e2, . . . , ek, where k is the maximum integer with the property that a minimum spanning tree exists containing the first k edges chosen by Prim's algorithm. The theorem follows if we can show that S = T.
Suppose that S # T, so that k < n - 1. Consequently, T contains eI, e2, . . . , ek, but not e k+1. Consider the graph made up of T together with ek+ 1. Because this graph is connected and has n edges, too many edges to be a tree, it must contain a simple circuit. This simple circuit must contain ek+ 1 because there was no simple circuit in T. Furthermore, there must be an edge in the simple circuit that does not belong to S k+ 1 because S k+ 1 is a tree. By starting at an endpoint of ek+ 1 that is also an endpoint of one of the edges eI, e2, . . . , ek, and following the circuit until it reaches an edge not in S k+ 1 , we can find an edge e not in S k+ 1 that has an endpoint that is also an endpoint of one of the edges eI, e2, . . . , ek. By deleting e from T and adding ek+ 1, we obtain a tree T' with n - 1 edges (it is a tree because it has no simple circuits). Note that the tree T' contains eI, e2, . . . , ek ,ek+I. Furthermore, because ek+I was chosen by Prim's algorithm at the (k + 1) th step, and e was also available at that step, the weight of ek+I is less than or equal to the weight of e. From this observation it follows that T' is also a minimum spanning tree, because the sum of the weights of its edges does not exceed the sum of the weights of the edges of T. This contradicts the choice of k as the maximum integer such that a minimum spanning tree exists containing eI, e2, . . . , ek . Hence, k = n - 1, and S = T. It follows that Prim's algorithm produces a minimum spanning tree.
************
Let us consider an example now.
Example 3
To construct a minimum spanning tree for the graph in the figure using Prim’s algorithm we proceed like this. Choose vertex a to start, minimum weight edge is {a, e} (weight 2), minimum weight edge from {a,e} to new vertex is {a, c} (weight 4), minimum weight edge from {a,c,e} to new vertex is {c, b} (weight 5), minimum weight edge from {a,b,c,e} to new vertex is {e,d} (weight 7), all vertices now connected.
We can see that the total weight is 18.
Of course, the choice of the vertex ‘a’ as starting vertex is arbitrary – let’s see what happens if we start somewhere else. Choose vertex b to start, minimum weight edge is {b, c} (weight 5), minimum weight edge from {b,c} to new vertex is {c, a} or {c, e} (both weight 4), choose {c, e}, minimum weight edge from {b,c,e} to new vertex is {e, a} (weight 2), minimum weight edge from {a,b,c,e} to new vertex is {e, d} (weight 7), all vertices now connected.
The total weight in this case is also 18.
In this case we see that we get a different minimum spanning tree (if we had chosen {c, a} instead of {c,e} at stage 2, we would have got the same minimum spanning tree as previously). This is because, in this graph, there is more than one minimum spanning tree.
Let us see one more example.
Example 4
Use Prim’s algorithm to design a minimum-cost communication network connecting all the computers represented in the figure shown.
Figure : A weighted graph showing monthly lease costs for lines in a computer network
Solution
First we choose an edge with minimum weight (Chicago, Atlanta) with cost $ 700.
Now, find the edge incident at either Chicago or Atlanta which is having smallest weight i.e.; the edge (Atlanta, New York) with cost $ 800
Next We have the edge (Chicago, San Fransisco) with cost $ 1200.
Next, choose the edge (San Fransisco, Denver) with cost $900.
A minimum spanning tree is given in the Figure
Figure : A minimum spanning tree using Prims algorithm.
The total cost is $700+$800+$1200+$900 = $3600
The second algorithm we will discuss was discovered by Joseph Kruskal in 1956.
To carry out Kruskal’s algorithm, choose an edge in the graph with minimum weight. Successively add edges with minimum weight that do not form a simple circuit with those edges already chosen. Stop after n-1 edges have been selected.