388 Routing in Data Networks Chap.5 2 Figure 5.21 Illustration of walks,paths, 03 and cycles.The sequences (1.4,2,3), (1.4,2.1).(l.4.2,1.4.1.(2,3.2).and(2)re all walks.The sequences (1,4,2,3)and (2) are each paths;and (1.4.2.1)is a cycle. Note that (2)and (2.3,2)are not considered )4 cycles. Lemma Let G be a connected graph and let S be any nonempty strict subset of the set of nodes N.Then at least one arc (i,j)exists with iS and js. We say that G=(N,A')is a subgraph of G=(N,A)if G'is a graph,NCN. and A'C A.For example,the last three graphs in Fig.5.22 are subgraphs of the first. A tree is a connected graph that contains no cycles.A spanning tree of a graph G is a subgraph of G that is a tree and that includes all the nodes of G.For example,the subgraphs in Fig.5.22(b)and(c)are spanning trees of the graph in Fig.5.22(a).The following simple algorithm constructs a spanning tree of an arbitrary connected graph G=(W,A): 1.Let n be an arbitrary node in N.Let N={n,and let A'be the empty set 0. 2.If N=N,then stop [G=(N,A)is a spanning tree];else go to step 3. 3.Let(i,j)∈A be an arc with i∈W',j∈W-W'.Update N'andA'by W':=W'U{j} A:=AU{,} Go to step 2. 2 (a) (b) (e) (d) Figure 5.22 A graph (a)and three subgraphs (b).(c).and (d).Subgraphs (b)and (c) are spanning trees
388 2 Routing in Data Networks Chap. 5 4 Figure 5.21 Illustration of walks, paths, 3 and cycles. The sequences (1,4,2,3), (1,4,2, I). (1,4,2, 1,4,I), (2,3,2), and (2) are all walks. The sequences (1,4,2,3) and (2) are each paths; and (1,4,2, I) is a cycle. Note that (2) and (2,3,2) are not considered cycles. Lemma. Let G be a connected graph and let S be any nonempty strict subset of the set of nodes N. Then at least one arc (i, j) exists with i E Sand j If- S. We say that G' = (N', A') is a suhgraph of G = (N, A) if G' is a graph, N' c N, and A' c A. For example, the last three graphs in Fig. 5.22 are subgraphs of the first. A tree is a connected graph that contains no cycles. A spanning tree of a graph G is a subgraph of G that is a tree and that includes all the nodes of G. For example, the subgraphs in Fig. 5.22(b) and (c) are spanning trees of the graph in Fig. 5.22(a). The following simple algorithm constructs a spanning tree of an arbitrary connected graph G = (N,A): 1. Let n be an arbitrary node in N. Let N' = {n}, and let A' be the empty set 0. 2. If N' = N, then stop [G' = (N', A') is a spanning tree]; else go to step 3. 3. Let (i,j) E A be an arc with i EN', j E N N'. Update N' and A' by N' :=N' U {j} A' := A' U {(i,j)} Go to step 2. 2 (a) 3 2 (b) 3 2 (e) 3 2 \, (d) Figure 5.22 A graph (a) and three subgraphs (b), (cl. and (d). Subgraphs (b) and (c) are spanning trees
Sec.5.2 Network Algorithms and Shortest Path Routing 389 To see why the algorithm works,note that step 3 is entered only whenA is a proper subset of A,so that the earlier lemma guarantees the existence of the arc (i.j). We use induction on successive executions of step 3 to see that G=(A.A')is al- ways a tree.Initially,G=([n,0)is trivially a tree,so assume that G=(A,A') is a tree before the update of step 3.This ensures that there is a path between each pair of nodes in N using arcs of A'.After adding node j and arc (i.j).each node has a path to j simply by adding j to the path to i,and similarly j has a path to each other node.Finally,node j cannot be in any cycles since (i.j)is the only arc of G incident to j,and there are no cycles not including j by the inductive hypoth- esis.Figure 5.23 shows after each execution of step 3 for one possible choice of arcs. Observe that the algorithm starts with a subgraph of one node and zero arcs and adds one node and one arc on each execution of step 3.This means that the spanning tree,G,resulting from the algorithm always has N nodes,where N is the number of nodes in G,and N-I arcs.Since G'is a subgraph of G,the number of arcs. A.in G must satisfy A N-1;this is true for every connected graph G.Next. assume that A =N-1.This means that the algorithm uses all arcs of G in the spanning tree G,so that G=G,and G must be a tree itself.Finally,if A N. then G contains at least one arc (i.j)not in the spanning tree G'generated by the algorithm.Letting (j,....)be the path from j to i in C.it is seen that (i..j.....) is a cycle in G and G cannot be a tree.The following proposition summarizes these results: Proposition.Let G be a connected graph with N nodes and A arcs.Then: 1.G contains a spanning tree. 2.A≥N-1. 3.G is a tree if and only if A=N-1. Figure 5.24 shows why connectedness is a necessary assumption for the last part of the proposition. G G Gi G3 Figure 5.23 Algorithm for constructing a spanning trec of a given graph G
Sec. 5.2 Network Algorithms and Shortest Path Routing 389 To see why the algorithm works, note that step 3 is entered only when /v' is a proper subset of N, so that the earlier lemma guarantees the existence of the arc (i. j). We use induction on successive executions of step 3 to see that G' = (JV', A') is always a tree. Initially, 0' = ({n}, 0) is trivially a tree, so assume that G' = (N'. A') is a tree before the update of step 3. This ensures that there is a path between each pair of nodes in N' using arcs of A'. After adding node j and arc (i. j), each node has a path to j simply by adding j to the path to i, and similarly j has a path to each other node. Finally, node j cannot be in any cycles since (i. j) is the only arc of G' incident to j, and there are no cycles not including j by the inductive hypothesis. Figure 5.23 shows G' after each execution of step 3 for one possible choice of arcs. Observe that the algorithm starts with a subgraph of one node and zero arcs and adds one node and one arc on each execution of step 3. This means that the spanning tree, 0', resulting from the algorithm always has N nodes, where N is the number of nodes in 0, and N - I arcs. Since G' is a subgraph of G, the number of arcs, A, in 0 must satisfy A 2': N - I; this is true for every connected graph G. Next, assume that A = N - I. This means that the algorithm uses all arcs of G in the spanning tree 0', so that 0 = 0', and G must be a tree itself. Finally, if A 2': N, then 0 contains at least one arc (i, j) not in the spanning tree G' generated by the algorithm. Letting (j, ... , i) be the path from j to i in G', it is seen that (i. j, .... i) is a cycle in 0 and G cannot be a tree. The following proposition summarizes these results: Proposition. Let 0 be a connected graph with N nodes and A arcs. Then: 1. G contains a spanning tree. 2. A 2': N - I. 3. 0 is a tree if and only if A = N - 1. Figure 5.24 shows why connectedness is a necessary assumption for the last part of the proposition. 2 3 2 2 ,/,1\, 2 3 G G'1 G'2 G'3 Figure 5.23 Algorithm for constructing a spanning tree of a given graph G
390 Routing in Data Networks Chap.5 ○3 Figure 5.24 Graph with A N-1. which is both disconnected and contains a cycle. 5.2.2 Minimum Weight Spanning Trees It is possible to construct a spanning tree rooted at some node by sending a packet from the node to all its neighbors;the neighbors must send the packet to their neighbors,and so on,with all nodes marking the transmitter of the first packet they receive as their"father" on the tree,as described in Fig.5.8.However,such a tree has no special properties. If the communication cost or delay of different links should be taken into account in constructing a spanning tree,we may consider using a minimum weight spanning tree, which we now define. Consider a connected graph G=(A.A)with N nodes and A arcs,and a weight wii for each arc (i.j)E A.A minimum weight spanning tree (MST for short)is a spanning tree with minimum sum of arc weights.An arc weight represents the commu- nication cost of a message along the arc in either direction,and the total spanning tree weight represents the cost of broadcasting a message to all nodes along the spanning tree. Any subtree (i.e.,a subgraph that is a tree)of an MST will be called a fragment. Note that a node by itself is considered a fragment.An arc having one node in a fragment and the other node not in this fragment is called an outgoing arc from the fragment.The following proposition is of central importance for MST algorithms. Proposition 1.Given a fragment F,let a =(i.j)be a minimum weight outgoing arc from F,where the node j is not in F.Then F,extended by arc a and node j,is a fragment. Proof:Denote by M the MST of which F is a subtree.If arc a belongs to Af. we are done,so assume otherwise.Then there is a cycle formed by o and the arcs of M.Since node j does not belong to F,there must be some arc B a that belongs to the cycle and to Af,and which is outgoing from F(see Fig.5.25).Deleting B from Al and adding a results in a subgraph Al'with(N-1)arcs and no cycles which,therefore. must be a spanning tree.Since a has less or equal weight to 3.Af'must be an MST,so F extended by a and j forms a fragment. Q.E.D. Proposition I can be used as the basis for MST construction algorithms.The idea is to start with one or more disjoint fragments and enlarge or combine them by adding minimum weight outgoing arcs.One method(the Prim-Dijkstra algorithm)starts with an
390 2 Routing in Data Networks Chap. 5 4 5.2.2 Minimum Weight Spanning Trees Figure 5.24 Graph with A = N - 1, which is both disconnected and contains a cycle, It is possible to construct a spanning tree rooted at some node by sending a packet from the node to all its neighbors; the neighbors must send the packet to their neighbors, and so on, with all nodes marking the transmitter of the first packet they receive as their "father" on the tree, as described in Fig. 5.8. However, such a tree has no special properties. If the communication cost or delay of different links should be taken into account in constructing a spanning tree, we may consider using a minimum weight spanning tree, which we now define. Consider a connected graph G = (/\/, A) with N nodes and A arcs, and a weight Viij for each arc (i. j) E A. A minimum weight spanning tree (MST for short) is a spanning tree with minimum sum of arc weights. An arc weight represents the communication cost of a message along the arc in either direction, and the total spanning tree weight represents the cost of broadcasting a message to all nodes along the spanning tree. Any subtree (i.e., a subgraph that is a tree) of an MST will be called a fragment. Note that a node by itself is considered a fragment. An arc having one node in a fragment and the other node not in this fragment is called an outgoing arc from the fragment. The following proposition is of central importance for MST algorithms. Proposition 1. Given a fragment F, let Q = (i, j) be a minimum weight outgoing arc from F, where the node j is not in F. Then F, extended by arc Q and node j, is a fragment. Proof: Denote by AI the MST of which F is a subtree. If arc Q belongs to AI, we are done, so assume otherwise. Then there is a cycle formed by Q and the arcs of AI. Since node j does not belong to F, there must be some arc (3 # Q that belongs to the cycle and to AI, and which is outgoing from F (see Fig. 5.25). Deleting (3 from AI and adding Q results in a subgraph 1\1' with (N - I) arcs and no cycles which, therefore, must be a spanning tree. Since Q has less or equal weight to /3, AI' must be an MST, so F extended by Q and j forms a fragment. Q.E.D. Proposition I can be used as the basis for MST construction algorithms. The idea is to start with one or more disjoint fragments and enlarge or combine them by adding minimum weight outgoing arcs. One method (the Prim-Dijkstra algorithm) starts with an
Sec.5.2 Network Algorithms and Shortest Path Routing 391 Fragment F -一：MSTM ：Fragment F Cycle formed by M and arc a v.n 3 6 Figure 5.25 Proof of Proposition 1.The numbers next to the arcs are the arc weights. F is a fragment which is a subtree of an MST \Let o be a minimum weight outgoing arc from F not belonging to Af.Let 3 o be an are that is outgoing from F and simultancously belongs to Af and to the cycle formed by o and A/.Deleting 3 from Al and adding a in its place forms another MST 1/.When F is extended by o.it forms a fragment. arbitrarily selected single node as a fragment and enlarges the fragment by successively adding a minimum weight outgoing arc.Another method (Kruskal's algorithm)starts with each node being a single node fragment:it then successively combines two of the fragments by using the arc that has minimum weight over all arcs that when added to the current set of fragments do not form a cycle(see Fig.5.26).Both of these algorithms terminate in N-1 iterations. Kruskal's algorithm proceeds by building up simultaneously several fragments that eventually join into an MST;however.only one arc at a time is added to the current set of fragments.Proposition I suggests the possibility of adding a minimum weight outgoing arc simultaneously to each fragment in a distributed algorithmic manner.This is possible if there is a unique MST,as we now discuss. A distributed algorithm for constructing the MST in a graph with a unique MST is as follows.Start with a set of fragments (these can be the nodes by themselves,for example).Each fragment determines its minimum weight outgoing arc,adds it to itself, and informs the fragment that lies at the other end of this arc.It can be seen that as long as the arc along which two fragments join is indeed a minimum weight outgoing arc for some fragment,the algorithm maintains a set of fragments of the MST at all times. and no cycle is ever formed.Furthermore,new arcs will be added until there are no further outgoing arcs and there is only one fragment(by necessity the MST).Therefore, the algorithm cannot stop short of finding the MST.Indeed,for the algorithm to work correctly,it is not necessary that the procedure for arc addition be synchronized for all fragments.What is needed,however,is a scheme for the nodes and arcs of a fragment to determine the minimum weight outgoing arc.There are a number of possibilities along these lines,but it is of interest to construct schemes that accomplish this with low
Sec. 5.2 Network Algorithms and Shortest Path Routing Fragment F 391 Cycle formed by M and arc 0: ---- . MST M Fragment F Figure 5.25 Proof of Proposition I. The numbers next to the arcs are the arc weights. F is a fragment which is a subtree of an MST .\1. Let (} be a minimum weight outgoing arc from F not belonging to :\1. Let 3 l' (} be an arc that is outgoing from F and simultaneously belongs to AI and to the cycle formed by (} and }II. Deleting .3 from }II and adding (} in its place forms another MST .\1i When F is extended by Q. it forms a fragment. arbitrarily selected single node as a fragment and enlarges the fragment by successively adding a minimum weight outgoing arc. Another method (Kruskal's algorithm) starts with each node being a single node fragment; it then successively combines two of the fragments by using the arc that has minimum weight over all arcs that when added to the current set of fragments do not form a cycle (see Fig. 5.26). Both of these algorithms terminate in IV - I iterations. Kruskal's algorithm proceeds by building up simultaneously several fragments that eventually join into an MST; however, only one arc at a time is added to the current set of fragments. Proposition I suggests the possibility of adding a minimum weight outgoing arc simultaneously to each fragment in a distributed algorithmic manner. This is possible if there is a unique MST, as we now discuss. A distributed algorithm for constructing the MST in a graph with a unique MST is as follows. Start with a set of fragments (these can be the nodes by themselves, for example). Each fragment determines its minimum weight outgoing are, adds it to itself, and informs the fragment that lies at the other end of this arc. It can be seen that as long as the arc along which two fragments join is indeed a minimum weight outgoing arc for some fragment, the algorithm maintains a set of fragments of the MST at all times, and no cycle is ever formed. Furthermore, new arcs will be added until there are no further outgoing arcs and there is only one fragment (by necessity the MST). Therefore. the algorithm cannot stop short of finding the MST. Indeed, for the algorithm to work correctly, it is not necessary that the procedure for arc addition be synchronized for all fragments. What is needed, however, is a scheme for the nodes and arcs of a fragment to determine the minimum weight outgoing arc. There are a number of possibilities along these lines, but it is of interest to construct schemes that accomplish this with low
392 Routing in Data Networks Chap.5 9 a b o-8 O O (5) (c) Figure 5.26 Minimum weight spanning tree construction.(a)Graph with arc weights as indicated.(b)Successive iterations of the Prim-Dijkstra algorithm.The starting fragment consists of the single node marked S.The fragment is successively extended by adding a minimum weight outgoing arc.(c)Successive iterations of the Kruskal algorithm.The algorithm starts with all nodes as fragments.At each iteration,we add the arc that has minimum weight out of all arcs that are outgoing from one of the fragments. communication overhead.This subject is addressed in [GHS83],to which we refer for further details.Reference [Hum83]considers the case where the arc weights are different in each direction.A distributed MST algorithm of the type just described has been used in the PARIS network [CGK90](see Section 6.4 for a description of this network). To see what can go wrong in the case of nonunique MSTs,consider the triangular network of Fig.5.27 where all arc lengths are unity.If we start with the three nodes as fragments and allow each fragment to add to itself an arbitrary,minimum weight outgoing arc,there is the possibility that the arcs (1,2),(2,3),and (3,1)will be added simultaneously by nodes 1,2,and 3,respectively,with a cycle resulting. The following proposition points the way on how to handle the case of nonunique MSTs
392 Routing in Data Networks ,L2fSj5 (a) Chap. 5 s o (b) o o o o (I) o o o 0 (2) o o (3) o o (4) (5) (e) (6) Figure 5.26 Minimum weight spanning tree construction. (a) Graph with arc weights as indicated. (b) Successive iterations of the Prim-Dijkstra algorithm. The starting fragment consists of the single node marked S. The fragment is successively extended by adding a minimum weight outgoing arc. (c) Successive iterations of the Kruskal algorithm. The algorithm starts with all nodes as fragments. At each iteration, we add the arc that has minimum weight out of all arcs that are outgoing from one of the fragments. communication overhead. This subject is addressed in [GHS83J, to which we refer for further details. Reference [Hum83J considers the case where the arc weights are different in each direction. A distributed MST algorithm of the type just described has been used in the PARIS network [CGK90J (see Section 6.4 for a description of this network). To see what can go wrong in the case of nonunique MSTs, consider the triangular network of Fig. 5.27 where all arc lengths are unity. If we start with the three nodes as fragments and allow each fragment to add to itself an arbitrary, minimum weight outgoing arc, there is the possibility that the arcs (1,2), (2,3), and (3,1) will be added simultaneously by nodes I, 2, and 3, respectively, with a cycle resulting. The following proposition points the way on how to handle the case of nonunique MSTs