The first recorded evidence of the use of graphs dates back to 1736 when Euler used them to solve the now classical Koenigsberg bridge problem. In the town of Koenigsberg (in Eastern Prussia) the river Pregal flows around the island Kneiphof and then divides into two. There are, therefore, four land areas bordering this river (figure 6.1). These land areas are interconnected by means of seven bridges *a*-g*. The land areas themselves are labeled *A*-D*. The Koenigsberg bridge problem is to determine whether starting at some land area it is possible to walk across all the bridges exactly once returning to the starting land area. One possible walk would be to start from land area *B*; walk across bridge *a* to island *A*; take bridge *e* to area *D*; bridge *g* to *C*; bridge *d* to *A*; bridge *b* to *B* and bridge *f* to *D*. This walk does not go across all bridges exactly once, nor does it return to the starting land area *B*. Euler answered the Koenigsberg bridge problem in the negative: The people of Koenigsberg will not be able to walk across each bridge exactly once and return to the starting point. He solved the problem by representing the land areas as vertices and the bridges as edges in a graph (actually a multigraph) as in figure 6.1(b). His solution is elegant and applies to all graphs. Defining the *degree* of a vertex to be the number of edges incident to it, Euler showed that there is a walk starting at any vertex, going through each edge exactly once and terminating at the start vertex iff the degree of each, vertex is even. A walk which does this is called *Eulerian*. There is no Eulerian walk for the Koenigsberg bridge problem as all four vertices are of odd degree.

A graph, *G*, consists of two sets *V* and *E*. *V* is a finite non-empty set of *vertices. E* is a set of pairs of vertices, these pairs are called *edges*. *V*(*G*) and *E*(*G*) will represent the sets of vertices and edges of graph *G*. We will also write *G* = (*V,E*) to represent a graph. In an *undirected graph *the pair of vertices representing any edge is unordered . Thus, the pairs (*v*_{1}, *v*_{2}) and (*v*_{2}, *v*_{1}) represent the same edge. In a *directed* *graph* each edge is represented by a directed pair (*v*_{1}, *v*_{2}). *v*_{1} is the *tail *and *v*_{2} the *head* of the edge. Therefore <*v*_{2}, *v*_{1}>_{} and <*v*_{1}, *v*_{2}>_{} represent two different edges. Figure 6.2 shows three graphs *G*_{1}, *G*_{2} and *G*_{3}.

The graphs *G*_{1} and *G*_{2} are undirected. *G*_{3} is a directed graph.

*V *(*G*_{1}) = {1,2,3,4}; *E*(*G*_{1}) = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

*V *(*G*_{2}) = {1,2,3,4,5,6,7}; *E*(*G*_{2}) = {(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)}

*V *(*G*_{3}) = {1,2,3}; *E*(*G*_{3}) = {<1,2>, <2,1>, <2,3>}.

While several representations for graphs are possible, we shall study only the three most commonly used: adjacency matrices, adjacency lists and adjacency multilists. Once again, the choice of a particular representation will depend upon the application one has in mind and the functions one expects to perform on the graph.

Let G = (*V*,*E*) be a graph with *n *vertices, *n * 1. The adjacency matrix of *G *is a 2-dimensional n n array, say *A*, with the property that *A*(*i*,*j*) = 1 iff the edge (v* _{i}*,v

In this representation the *n *rows of the adjacency matrix are represented as *n* linked lists. There is one list for each vertex in *G*. The nodes in list *i* represent the vertices that are adjacent from vertex *i*. Each node has at least two fields: VERTEX and LINK. The VERTEX fields contain the indices of the vertices adjacent to vertex *i*. The adjacency lists for *G*_{1}, *G*_{3} and *G*_{4} are shown in figure 6.8. Each list has a headnode. The headnodes are sequential providing easy random access to the adjacency list for any particular vertex. In the case of an undirected graph with *n* vertices and *e *edges, this representation requires *n* head nodes and 2*e* list nodes. Each list node has 2 fields. In terms of the number of bits of storage needed, this count should be multiplied by log *n* for the head nodes and log *n* + log *e* for the list nodes as it takes *O*(log *m*) bits to represent a number of value *m*. Often one can sequentially pack the nodes on the adjacency lists and eliminate the link fields.

The degree of any vertex in an undirected graph may be determined by just counting the number of nodes in its adjacency list. The total number of edges in *G* may, therefore, be determined in time *O*(*n* + *e*). In the case of a digraph the number of list nodes is only *e*. The out-degree of any vertex may be determined by counting the number of nodes on its adjacency list. The total number of edges in *G* can, therefore, be determined in *O*(*n* + *e*). Determining the in-degree of a vertex is a little more complex. In case there is a need to repeatedly access all vertices adjacent to another vertex then it may be worth the effort to keep another set of lists in addition to the adjacency lists. This set of lists, called *inverse adjacency lists*, will contain one list for each vertex. Each list will contain a node for each vertex adjacent to the vertex it represents (figure 6.9). Alternatively, one could adopt a

In the adjacency list representation of an undirected graph each edge (*v _{i}*,

Sometimes the edges of a graph have weights assigned to them. These weights may represent the distance from one vertex to another or the

The lists are: vertex 1: N1 N2 N3

vertex 2: N1 N4 N5

vertex 3: N2 N4 N6

vertex 4: N3 N5 N6

Given the root node of a binary tree, one of the most common things one wishes to do is to traverse the tree and visit the nodes in some order. In the chapter on trees, we defined three ways (preorder, inorder, and postorder) for doing this. An analogous problem arises in the case of graphs. Given an undirected graph *G* = (*V,E*) and a vertex *v* in *V*(*G*) we are interested in visiting all vertices in *G* that are reachable from *v *(i.e., all vertices connected to *v*). We shall look at two ways of doing this: Depth First Search and Breadth First Search.

Depth first search of an undirected graph proceeds as follows. The start vertex *v* is visited. Next an unvisited vertex *w* adjacent to *v* is selected and a depth first search from *w* initiated. When a vertex *u* is reached such that all its adjacent vertices have been visited, we back up to the last vertex visited which has an unvisited vertex *w* adjacent to it and initiate a depth first seaerch from *w*. The search terminates when no unvisited vertex can be reached from any of the visited one. This procedure is best described recursively as in

procedureDFS(v)

//Given an undirected graphG =(V,E)with nvertices and an array

VlSlTED(n) initially set to zero, this algorithm visits all vertices

reachable fromv. GandVISITEDare global.//

VISITED(v) 1

foreach vertex wadjacent tovdo

ifVISlTED(w) = 0then callDFS(w)

end

endDFS

Starting at vertex *v *and marking it as visited, breadth first search differs from depth first search in that all unvisited vertices adjacent to *v* are visited next. Then unvisited vertices adjacent to these vertices are visited and so on. A breadth first search beginning at vertex *v*_{1} of the graph in figure 6.13(a) would first visit *v*_{1} and then *v*_{2} and* v*_{3}. Next vertices *v*_{4}, *v*_{5}, *v*_{6} and *v*_{7} will be visited and finally *v*_{8}. Algorithm BFS gives the details.

procedureBFS(v)

//A breadth first search ofGis carried out beginning at vertexv.

All vertices visited are marked asVISlTED(i)= 1. The graphG

and arrayVISITEDare global andVISITEDis initialized to zero.//

VISITED(v) 1

initializeQto be empty//Qis a queue//

loop

forall vertices w adjacent to vdo

ifVISITED(w) = 0 //addwto queue//

then[callADDQ(w,Q); VISITED(w)1]

//markwasVISITED//

end

ifQis emptythen return

callDELETEQ(v,Q)

forever

endBFS

If *G* is an undirected graph, then one can determine whether or not it is connected by simply making a call to either DFS or BFS and then determining if there is any unvisited vertex. The time to do this is *O*(*n*^{2}) if adjacency matrices are used and O(*e*) if adjacency lists are used. A more interesting problem is to determine all the connected components of a graph. These may be obtained by making repeated calls to either DFS(*v*) or BFS(*v*), with *v *a vertex not yet visited. This leads to algorithm COMP which determines all the connected components of *G*. The algorithm uses DFS. BFS may be used instead if desired.The computing time is not affected.

procedureCOMP(G,n)

//determine the connected components ofG.Ghasn1 vertices.

VISITEDis now a local array.//

fori1tondo

VISITED(i)0 //initialize all vertices as unvisited//

end

fori1 tondo

ifVISITED(i) = 0then[callDFS(i); //find a component//

output all newly visited vertices together

with all edges incident to them]

end

endCOMP

By the definition of a connected component, there is a path between every pair of vertices in the component and there is no path in *G* from vertex *v* to *w* if *v* and *w* are in two different components. Hence, if *A *is the adjacency matrix of an undirected graph (i.e., *A* is symmetric) then its transitive closure A^{+} may be determined in *O*(*n ^{2}*) time by first determining the connected components.

When the graph *G* is connected, a depth first or breadth first search starting at any vertex, visits all the vertices in *G*. In this case the edges of *G* are partitioned into two sets *T* (for tree edges) and *B* (for back edges), where *T* is the set of edges used or traversed during the search and *B* the set of remaining edges. The set *T* may be determined by inserting the statement *T ** T* {(*v,w*)} in the **then** clauses of DFS and BFS. The edges in *T *form a tree which includes all the vertices of *G*. Any tree consisting solely of edges in *G* and including all vertices in *G* is called a *spanning tree.* Figure 6.14 shows a graph and some of its spanning trees. When either DFS or BFS are used the edges of *T* form a spanning tree. The spanning tree resulting from a call to DFS is known as a *depth first spanning tree*. When BFS is used, the resulting spanning tree is called a *breadth first spanning tree.*

Spanning trees find application in obtaining an independent set of circuit equations for an electrical network. First, a spanning tree for the network is obtained. Then the edges in *B* (i.e., edges not in the spanning tree) are introduced one at a time. The introduction of each such edge results in a cycle. Kirchoff's second law is used on this cycle to obtain a circuit equation. The cycles obtained in this way are independent (i.e., none of these cycles can be obtained by taking a linear combination of the remaining cycles) as each contains an edge from *B* which is not contained in any other cycle. Hence, the circuit equations so obtained are also independent. In fact, it may be shown that the cycles obtained by introducing the edges of *B* one at a time into the resulting spanning tree form a cycle basis and so all other cycles in the graph can be constructed by taking a linear combination of the cycles in the basis (see Harary in the references for further details).

One approach to determining a minimum cost spanning tree of a graph has been given by Kruskal. In this approach a minimum cost spanning tree, *T*, is built edge by edge. Edges are considered for inclusion in *T* in nondecreasing order of their costs. An edge is included in *T* if it does not form a cycle with the edges already in *T*. Since *G* is connected and has *n* > 0 vertices, exactly *n* - 1 edges will be selected for inclusion in *T*. As an example, consider the graph of figure 6.16(a). The edges of this graph are considered for inclusion in the minimum cost spanning tree in the order (2,3), (2,4), (4,3), (2,6), (4,6), (1,2), (4,5), (1,5) and (5,6). This corresponds to the cost sequence 5, 6, 10, 11, 14, 16, 18, 19 and 33. The first two edges (2,3) and (2,4) are included in *T*. The next edge to be considered is (4,3). This edge, however, connects two vertices already connected in *T* and so it is rejected. The edge (2,6) is selected while (4,6) is rejected as the vertices 4 and 6 are already connected in *T* and the inclusion of (4,6) would result in a cycle. Finally, edges (1,2) and (4,5) are included. At this point, *T* has *n* - 1 edges and is a tree spanning *n* vertices. The spanning tree obtained (figure 6.16(b)) has cost 56. It is somewhat surprising that this straightforward approach should always result in a minimum spanning tree. We shall soon prove that this is indeed the case. First, let us look into the details of the algorithm. For clarity, the Kruskal algorithm is written out more formally in figure 6.18. Initially, *E* is the set of all edges in *G*. The only functions we wish to perform on this set are: (i) determining an edge with minimum cost (line 3), and (ii) deleting that edge (line 4). Both these functions can be performed efficiently if the edges in *E* are maintained as a sorted sequential list. In Chapter 7 we shall see how to sort these edges into nondecreasing order in time *O*(*e *log *e*), where *e *is the number of edges in *E*. Actually, it is not essential to sort all the edges so long as the next edge for line 3 can be determined easily. It will be seen that the heap of Heapsort (section 7.6) is ideal for this and permits the next edge to be determined and deleted in *O*(log *e*) time. The construction of the heap itself takes *O*(*e*) time.

1T

2whileT contains less than n - 1 edgesandE not emptydo

3choose an edge(v,w)from E of lowest cost;

4delete(v,w)from E;

5if(v,w)does not create a cycle in T

6thenadd(v,w)to T

7elsediscard(v,w)

8end

9ifT contains fewer than n -1edgesthen print('no spanning tree')

**Definition**: A *spanning forest *of a graph G = (*V*,*E*) is a collection of vertex disjoint trees *T _{i} = *(

**Lemma 6.1:** Let *T _{i} = *(

**Theorem 6.1:** The algorithm described in figure 6.18 generates a minimum spanning tree.

Graphs may be used to represent the highway structure of a state or country with vertices representing cities and edges representing sections of highway. The edges may then be assigned weights which might be either the distance between the two cities connected by the edge or the average time to drive along that section of highway. A motorist wishing to drive from city *A* to city *B* would be interested in answers to the following questions:

(i) Is there a path from *A* to *B*?

(ii) If there is more than one path from *A* to *B*, which is the shortest path?

procedureSHORTEST-PATH (v,COST,DIST,n)

//DIST(j), 1 jnis set to the length of the shortest path

from vertexvto vertexjin a digraphGwithnvertices.DIST(v)

is set to zero. G is represented by its cost adjacency matrix,

COST(n,n)//

declareS(1:n)

1fori1tondo//initialize setSto empty//

2S(i)0;DIST(i)COST(v,i)

3end

4S(v)1;DIST(v)0;num2 //put vertexvin set

S//

5whilenum < ndo //determinen- 1 paths from vertexv//

6choose u: DIST(u)= min {DIST(w)}

S(w)=0

7S(u)1;numnum+ 1 //put vertexuin setS//

8forall w with S(w)= 0do//update distances//

9DIST(w)min {DIST(w),DIST(u) + COST(u,w)}

10end

11end

12endSHORTEST-PATH

**Example 6.1:** Consider the 8 vertex digraph of figure 6.20(a) with cost adjacency matrix as in 6.20(b). The values of DIST and the vertices selected at each iteration of the **while** loop of line 5 for finding all the shortest paths from Boston are shown in table 6.21. Note that the algorithm terminates when only seven of the eight vertices are in *S*. By the definition of DIST, the distance of the last vertex, in this case

Vertex LA SF D C B NY M NO

Iteration S Selected DIST(1) (2) (3) (4) (5) (6) (7) (8)

Initial -- + + + 1500 0 250 + +

1 5 6 + + + 1250 0 250 1150 1650

2 5,6 7 + + + 1250 0 250 1150 1650

3 5,6,7 4 + + 2450 1250 0 250 1150 1650

4 5,6,7,4 8 3350 + 2450 1250 0 250 1150 1650

5 5,6,7,4,8 3 3350 3250 2450 1250 0 250 1150 1650

6 5,6,7,4,8,3 2 3350 3250 2450 1250 0 250 1150 1650

5,6,7,4,8,3,2

*A ^{k}*(

**Example 6.2:** Figure 6.22 shows a digraph together with its matrix *A*^{0}. For this graph *A*^{2}(1,3) min {*A*^{1}(1,3)*, A*^{1}(1,2) *+ A*^{1}(2,3)} = 2. Instead we see that *A*^{2}(1,3) = - as the length of the path

procedureALL_COSTS(COST,A,n)

//COST(n,n) is the cost adjacency matrix of a graph with n

vertices; A(i,j) is the cost of the shortest path between vertices

v_{i},v_{j}. COST(i,i) = 0, 1 i n//

1fori 1tondo

2forj 1tondo

3 A (i,j) COST (i,j) //copy COST into A//

4end

5end

6fork 1tondo//for a path with highest vertex index k//

7fori 1tondo//for all possible pairs of vertices//

8forj 1tondo

9 A (i,j) min {A (i,j),A(i,k) + A(k,j)}

10end

11end

12end

13endALL_COSTS

**Example 6.3: **: Using the graph of figure 6.23(a) we obtain the cost matrix of figure 6.23(b). The initial *A* matrix, *A ^{o} *plus its value after 3 iterations

A^{0..}1 2 3A^{1 }1 2 3

----------------------------

1 0 4 11 1 0 4 11

2 6 0 2 2 6 0 2

3 3_{}0 3 3 7 0

A1 2 3 A^{2 }1 2 3^{3 }

----------------------------

1 0 4 6 1 0 4 6

2 6 0 2 2 5 0 2

3 3 7 0 3 3 7 0

A problem related to the all pairs shortest path problem is that of determining for every pair of vertices *i,j* in *G* the existence of a path from *i* to *j*. Two cases are of interest, one when all path lengths (i.e., the number of edges on the path) are required to be positive and the other when path lengths are to be nonnegative. If *A* is the adjacency matrix of *G*, then the matrix *A*^{+} having the property *A*^{+}* *(*i,j*) = 1 if there is a path of length > 0 from *i* to *j* and 0 otherwise is called the *transitive closure* matrix of *G*. The matrix *A*^{*} with the property *A*^{*}* *(*i,j*) = 1 if there is a path of length 0 from *i* to *j* and 0 otherwise is the *reflexive transitive closure* matrix of *G*.

All but the simplest of projects can be subdivided into several subprojects called activities. The successful completion of these activities will result in the completion of the entire project. A student working towards a degree in Computer Science will have to complete several courses successfully. The project in this case is to complete the major, and the activities are the individual courses that have to be taken. Figure 6.26 lists the courses needed for a computer science major at a hypothetical university. Some of these courses may be taken independently of others while other courses have prerequisites and can be taken only if all their prerequisites have already been taken. The data structures course cannot be started until certain programming and math courses have been completed. Thus, prerequisites define precedence relations between the courses. The relationships defined may be more clearly represented using a directed graph in which the vertices represent courses and the directed edges represent prerequisites. This graph has an edge <*i,j*> iff course *i* is a prerequisite for course *j*.

Figure 6.26(b) is the AOV-network corresponding to the courses of figure 6.26(a). C3, C4 and C10 are the immediate predecessors of C7. C2, C3 and C4 are the immediate successors of C1. C12 is a succesor of C4 but not an immediate successor. The precedence relation defined by the set of edges on the set of vertices is readily seen to be transitive. (Recall that a relation is transitive iff it is the case that for all triples *i,j,k, i * j and j * k ** i k.*) In order for an AOV-network to represent a feasible project, the precedence relation should also be irreflexive.

Course Number Course Name Prerequisites

Cl Introduction to Programming None

C2 umerical Analysis Cl, C14

C3 ata Structures Cl, C14

C4 ssembly Language Cl, C13

C5 utomata Theory C15

C6 rtificial Intelligence C3

C7 omputer Graphics C3, C4, C10

C8 achine Arithmetic C4

C9 nalysis of Algorithms C3

C10 Higher Level Languages C3, C4

Cll Compiler Writing C10

C12 Operating Systems Cl l

C13 Analytic Geometry and Calculus I None

C14 Analytic Geometry and Calculus II C13

C15 Linear Algebra C14

**Definition:** A relation is *irreflexive* on a set *S* if for no element *x* in *S *it is the case that *x*x*. A precedence relation which is both transitive and irreflexive is a *partial order*.*

If the precedence relation is not irreflexive, then there is an activity which is a predecessor of itself and so must be completed before it can be started. This is clearly impossible. When there are no inconsistencies of this type, the project is feasible. Given an AOV network one of our concerns would be to determine whether or not the precedence relation defined by its edges is irreflexive. This is identical to determining whether or not the network contains any directed cycles. A directed graph with no directed cycles is an *acyclic* graph. Our algorithm to test an AOV-network for feasibility will also generate a linear ordering, v* _{i1}*, v

input the AOV-network. Let n be the number of vertices.

1fori1tondo//output the vertices//

2ifevery vertex has a predecessor

then[the network has a cycle and is infeasible.stop]

3pick a vertex v which has no predecessors

4output v

5delete v and all edges leading out of v from the network

6end

procedureTOPOLOGICAL__ORDER (COUNT, VERTEX, LINK, n)

//the n vertices of an AOV-network are listed in topological order.

The network is represented as a set of adjacency lists with

COUNT(i) = the in-degree of vertex i//

1top0 //initialize stack//

2fori 1tondo//create a linked stack of vertices with

no predecessors//

3ifCOUNT(i) = 0then[COUNT(i)top;topi]

4end

5fori 1tondo//print the vertices in topological order//

6iftop= 0then[network has a cycle');stop]

7 jtop;topCOUNT(top);j) //unstack a vertex//

8ptrLINK(j)

9whileptr0do

//decrease the count of successor vertices of j//

10kVERTEX(ptr) //kis a successor of j//

11COUNT(k)COUNT(k) - 1 //decrease count//

12ifCOUNT(k) = 0 //add vertex k to stack//

13then[COUNT(k)top;topk]

14ptrLINK(ptr)

15end

16end

17endTOPOLOGICAL_ORDER

An activity network closely related to the AOV-network is the activity on edge or AOE network. The tasks to be performed on a project are represented by directed edges. Vertices in the network represent events. Events signal the completion of certain activities. Activities represented by edges leaving a vertex cannot be started until the event at that vertex has occurred. An event occurs only when all activities entering it have been completed. Figure 6.30(a) is an AOE network for a hypothetical project with 11 tasks or activities *a*_{1}, ...,*a*_{11}. There are 9 events *v*_{1}, *v*_{2}, ..., *v*_{9}. The events *v*_{l} and *v*_{9} may be interpreted as ''start project'' and ''finish project'' respectively. Figure 6.30(b) gives interpretations for some of the 9 events. The number associated with each activity is the time needed to perform that activity. Thus, activity *a*_{1} requires 6 days while *a*_{11} requires 4 days. Usually, these times are only estimates. Activities *a*_{1}, *a*_{2} and *a*_{3} may be carried out concurrently after the start of the project. *a*_{4}, *a*_{5} and a_{6} cannot be started until events *v*_{2}, *v*_{3} and v_{4}, respectively, occur. *a*_{7} and *a*_{8} can be carried out concurrently after the occurrence of event *v*_{5} (i.e., after *a*_{4} and *a*_{5} have been completed). In case additional ordering constraints are to be put on the activities, dummy activities whose time is zero may be introduced. Thus, if we desire that activities *a*_{7} and *a*_{8} not start until both events *v*_{5} and *v*_{6} have occurred, a dummy activity *a*_{12 }represented by an edge <*v*_{6},_{ }*v*_{5}> may be introduced. Activity networks of the AOE type have proved very useful in the performance evaluation of several types of projects. This evaluation includes determining such facts about the project as: what is the least amount of time in which the project may be completed (assuming there are no cycles in the network); which activities should be speeded up in order to reduce completion time; etc. Several sophisticated techniques such as PERT (performance evaluation and review technique), CPM (critical path method), RAMPS (resource allocation and multi-project scheduling) have been developed to evaluate network models of projects. CPM was originally developed in connection with maintenance and construction projects. Figure 6.31 shows a network used by the Perinia Corporation of Boston in 1961 to model the construction of a floor in a multistory building. PERT was originally designed for use in the development of the Polaris Missile system.

event interpretation

----- --------------

v_{1 }start of project

v_{2 }completion of activitya_{1}

v_{5 }completion of activitiesa_{4}anda_{5}

v_{8 }completion of activitiesa_{8}anda_{9}

v_{9 }completion of project

*l*(*i*)* = le*(*l*) - duration of activity *a _{i}*

*ee*(*k*) *max *{*ee*(*k*), *ee*(*j*) + DUR (ptr)}

ee(1) (2) (3) (4) (5) (6) (7) (8) (9) stack

initial 0 0 0 0 0 0 0 0 01

outputv_{1 }0 6 4 5 0 0 0 0 0 4

3

2

outputv_{4}0 6 4 5 0 7 0 0 0 6

3

2

outputv_{6}0 6 4 5 0 7 0 11 0 3

2

outputv_{3 }0 6 4 5 5 7 0 11 0 2

outputv_{2 }0 6 4 5 7 7 0 11 0 5

outputv_{5 }0 6 4 5 7 7 16 14 0 8

7

outputv_{8}0 6 4 5 7 7 16 14 16 7

outputv_{7 }0 6 4 5 7 7 16 14 18 9

outputv_{9}

le(1) (2) (3) (4) (5) (6) (7) (8) (9) stack

initial 18 18 18 18 18 18 18 18 18 9

outputv_{9}18 18 18 18 18 18 16 14 18 8

7

outputv_{8 }18 18 18 18 7 10 16 14 18 6

7

outputv_{6 }18 18 18 18 7 10 16 14 18 4

7

outputv_{4 }3 18 18 8 7 10 16 14 18 7

outputv_{7 }3 18 18 8 7 10 16 14 18 5

outputv_{5 }3 6 6 8 7 10 16 14 18 3

2

outputv_{3 }2 6 6 8 7 10 16 14 18 2

outputv_{2}0 6 6 8 7 10 16 14 18 1

le(9) =ee(9) = 18

le(7) = min {le(9) - 2} = 16

le(8) = min {le(9) - 4} = 14

le(5) = min {le(7) - 9,le(8)- 7} = 7

le(2) = min {le(5) - 1} = 6

le(3) = min {le(5) - 1} = 6

le(6) = min {le(8) - 4} = 10

le(4) = min {le(6) - 2} = 8

le(l) = min {le(2) - 6,le(3) - 4,le(4) - 5} = 0

activity e l l - e

a_{1 }0 0 0

a_{2 }0 2 2

a_{3 }0 3 3

a_{4 }6 6 0

a_{5 }4 6 2

a_{6 }5 8 3

a_{7 }7 7 0

a_{8 }7 7 0

a_{9 }7 10 3

a_{10 }16 16 0

a_{11 }14 14 0

(1): It contains the edges (*r*(1), *r*(2)), ..., (*r(k* - 1), *r*(*k*))but not (*r*(0), *r*(1))

(2): It contains the edges (*r*(2), *r*(3)), ..., (*r*(*k* - 1), *r*(*k*)) but not (*r*(*1*)*, r*(2))

(*k*): It does not contain the edge (*r*(*k* - 1), *r*(*k*)).

(*r*(*j*), *r*(*j +* 1)), ...,(*r*(*k* - 1), *r*(*k*)) but not (*r*(*j -* 1), *r*(*j*)).

A very informal version of the algorithm appears as the procedure M_SHORTEST.

procedureM_SHORTEST(M)

//Given a digraphGwith positive edge weights this procedure outputs

theMshortest paths fromv_{1}tov._{n}Qcontains tuples of the

form (p,C) wherepis a shortest path inGsatisfying constraints

C. These constraints either require certain edges to be included

or excluded from the path//

1Q{(shortest v_{1}tov_{n}path, )}

2fori 1toMdo//generateMshortest paths//

3let(p,C)be the tuple in Q such that path p is of minimal length.

//p is thei'th shortest path//

4path p;delete pathpfromQ

5determine the shortest paths in Gunder the constraintsCand

the additional constraints imposed by the partitioning described

in the text

6add these shortest paths together with their constraints to Q

7end

8endM_SHORTEST

Shortest

Path Cost Included Edges Excluded Edges New Path

------ ---- -------------- -------------- --------

v_{1}v_{3}v_{5}v_{6 }8 none none

none (v_{5}v_{6}) v_{1}v_{3}v_{4}v_{6}= 9

(v_{5}v_{6}) (v_{3}v_{5}) v_{1}v_{2}v_{5}v_{6}= 12

(v_{3}v_{5})(v_{5}v_{6}) (v_{1}v_{3}) v_{1}v_{2}v_{3}v_{5}v_{6}= 14

v_{1}v_{3}v_{4}v_{6 }9 none (v_{5}v_{6})

none (v_{4}v_{6})(v_{5}v_{6})

(v_{4}v_{6}) (v_{3}v_{4})(v_{5}v_{6}) v_{1}v_{2}v_{4}v_{6}= 13

(v_{3}v_{4})(v_{4}v_{6}) (v_{1}v_{3})(v_{5}v_{6}) v_{1}v_{2}v_{3}v_{4}v_{6}= 15

v_{1}v_{2}v_{5}v_{6 }12 (v_{5}v_{6}) (v_{3}v_{5})

(v_{5}v_{6}) (v_{2}v_{5})(v_{3}v_{5}) v_{1}v_{3}v_{4}v_{5}v_{6}= 16

(v_{2}v_{5})(v_{5}v_{6}) (v_{1}v_{2})(v_{3}v_{5})

v_{1}v_{2}v_{4}v_{6 }13 (v_{4}v_{6}) (v_{3}v_{4})(v_{5}v_{6})

(v_{4}v_{6}) (v_{2}v_{4})(v_{3}v_{4})(v_{5}v_{6})

(v_{2}v_{4})(v_{4}v_{6}) " (v_{1}v_{2})(v_{3}v_{4})(v_{5}v_{6})

v_{1}v_{2}v_{3}v_{5}v_{6 }14 (v_{3}v_{5})(v_{5}v_{6}) (v_{1}v_{3})

(v_{3}v_{5})(v_{5}v_{6}) (v_{2}v_{3})(v_{1}v_{3})

(v_{2}v_{3})(v_{3}v_{5})(v_{5}v_{6}) (v_{1}v_{2})(v_{5}v_{6})

v_{1}v_{2}v_{3}v_{4}v_{6 }15 (v_{3}v_{4})(v_{4}v_{6}) (v_{1}v_{3})(v_{5}v_{6})

(v_{3}v_{4})(v_{4}v_{6}) (v_{2}v_{3})(v_{1}v_{3})(v_{5}v_{6})

(v_{2}v_{3})(v_{3}v_{5})(v_{5}v_{6}) (v_{1}v_{2})(v_{1}v_{3})(v_{5}v_{6})

v_{1}v_{3}v_{4}v_{5}v_{6}16 (v_{5}v_{6}) (v_{2}v_{5})(v_{3}v_{5})

(v_{5}v_{6}) (v_{4}v_{5})(v_{2}v_{5})(v_{3}v_{5})

(v_{4}v_{5})(v_{5}v_{6}) (v_{3}v_{4})(v_{2}v_{5})(v_{3}v_{5}) v_{1}v_{2}v_{4}v_{5}v_{6}= 20

(v_{3}v_{4})(v_{4}v_{5})(v_{5}v_{6}) (v_{1}v_{3})0(v_{2}v_{5})(v_{3}v_{5}) v_{1}v_{2}v_{3}v_{4}v_{5}v_{6}= 22

Good general references for this chapter are:

*Graph Theory* by F. Harary, Addison-Wesley, Reading, Massachusetts, 1972.

*The theory of graphs and its applications* by C. Berge, John Wiley, 1962.

Further algorithms on graphs may be found in:

*Combinatorial Optimization* by E. Lawler, Holt, Reinhart and Winston, 1976.

*Flows in Networks* by L. Ford and D. Fulkerson, Princeton University Press, 1962.

*Integer Programming and Network Flows* by T. C. Hu, Addison-Wesley, Reading, Massachusetts, 1970.

For more on activity networks and critical path analysis see:

*Project Management with CPM and PERT* by Moder and C. Phillips, Van Nostran Reinhold Co., 1970.

1. Does the multigraph below have an Eulerian walk? If so, find one.

2. For the digraph at the top of page 329 obtain:

i) the in degree and out degree of each vertex;

iii) its adjacency list representation;

iv) its adjacency multilist representation;

v) its strongly connected components

**4.** Draw the complete undirected graphs on one, two, three, four and five vertices. Prove that the number of edges in a *n* vertex complete graph is *n*(*n* - 1)/2.

**5.** Is the directed graph below strongly connected? List all the simple paths.

**6.** Show how the graph above would look if represented by its adjacency matrix, adjacency lists, adjacency multilist.

**7.** For an undirected graph *G* with *n* vertices and *e* edges show that where *d _{i}* = degree of vertex

**8.*** *(a)* *Let *G* be a connected undirected graph on *n* vertices. Show that *G* must have at least *n* - 1 edges and that all connected undirected graphs with *n* - 1 edges are trees.

**9.** For an undirected graph *G* with *n* vertices prove that the following are equivalent:

(b) *G* is connected, but if any edge is removed the resulting graph is not connected;

(c) For any distinct vertices *u * V*(*G*) and *v * V*(*G*) there is exactly one simple path from *u* to *v*;

(d) *G* contains no cycles and has *n* - 1 edges;

(e) *G* is connected and has *n* - 1 edges.

**10.** A *bipartite graph G = *(*V,E*) is an undirected graph whose vertices can be partitioned into two disjoint sets *V*_{1} and *V*_{2} = V - *V*_{1} with the properties (i) no two vertices in *V*_{1} are adjacent in *G* and (ii) no two vertices in *V*_{2} are adjacent in *G*. The graph *G*_{4} of figure 6.5 is bipartite. A possible partitioning of *V* is: *V*_{1} = {1,4.5,7} and *V*_{2} = {2,3,6,8}. Write an algorithm to determine whether a graph *G* is bipartite. In case *G* is bipartite your algorithm should obtain a partitioning of the vertices into two disjoint sets *V*_{1} and *V*_{2} satisfying properties (i) and (ii) above. Show that if *G* is represented by its adjacency lists, then this algorithm can be made to work in time *O*(*n + e*) where *n = *V and *e* = E.

**11.** Show that every tree is a bipartite graph.

**12.** Prove that a graph *G* is bipartite iff it contains no cycles of odd length.

**13.** The following algorithm was obtained by Stephen Bernard to find an Eulerian circuit in an undirected graph in case there was such a circuit.

procedureEULER(v)

1path{}

2for allvertices w adjacent to vandedge(v,w)not yet useddo

3mark edge(v,w)as used

4path{(v,w)}EULER(w)path

5end

6return(path)

7endEULER

c) At termination, what has to be done to determine whether or not *G* has an Euler circuit?

**14.** Apply depth first and breadth first search to the complete graph on four vertices. List the vertices in the order they would be visited.

**15.** Show how to modify algorithm DFS as it is used in COMP to produce a list of all newly visited vertices.

**16.** Prove that when algorithm DFS is applied to a connected graph the edges of *T* form a tree.

**17.** Prove that when algorithm BFS is applied to a connected graph the edges of *T* form a tree.

**18.** Show that *A*^{+}* = A* *x* A* where matrix multiplication of the two matrices is defined as . *V* is the logical *or* operation and ^ is the logical *and* operation.

**19.** Obtain the matrices *A ^{+}* and

**20.** Another way to represent a graph is by its incidence matrix, INC. There is one row for each vertex and one column for each edge. Then INC (*i,j*) = 1 if edge *j* is incident to vertex *i*. The incidence matrix for the graph of figure 6.13(a) is:

**22.** Show that if *T* is a spanning tree for the undirected graph *G*, then the addition of an edge *e, e* *E*(*T*) and *e* *E*(*G*), to *T* creates a unique cycle .

**23.** By considering the complete graph with *n* vertices, show that the number of spanning trees is at least 2^{n-1} - 1

**24.** The *radius* of a tree is the maximum distance from the root to a leaf. Given a connected, undirected graph write an algorithm for finding a spanning tree of minimum radius. (Hint: use breadth first search.) Prove that your algorithm is correct.

**25.** The *diameter* of a tree is the maximum distance between any two vertices. Given a connected, undirected graph write all algorithm for finding a spanning tree of minimum diameter. Prove the correctness of your algorithm.

**26.** Write out Kruskal's minimum spanning tree algorithm (figure 6.18) as a complete SPARKS program. You may use as subroutines the algorithms UNION and FIND of Chapter 5. Use algorithm SORT to sort the edges into nondecreasing order by weight.

**27.** Using the idea of algorithm SHORTEST_PATH, give an algorithm for finding a minimum spanning tree whose worst case time is *O*(*n*^{2}).

**28.** Use algorithm SHORTEST_PATH to obtain in nondecreasing order the lengths of the shortest paths from vertex 1 to all remaining vertices in the digraph:

**29.** Rewrite algorithm SHORTEST_PATH under the following assumptions:

What can you say about the computing time of your new algorithm relative to that of SHORTEST_PATH?

**30.** Modify algorithm SHORTEST_PATH so that it obtains the shortest paths in addition to the lengths of these paths. What is the computing time of your algorithm?

**31.** Using the directed graph below, explain why SHORTEST_PATH will not work properly. What is the shortest path between vertices *v*_{1}, and *v*_{7}?

**32.** Modify algorithm ALL_COSTS so that it obtains a shortest path for all pairs of vertices *i,j*. What is the computing time of your new algorithm?

**33.** By considering the complete graph with *n* vertices show that the maximum number of paths between two vertices is (*n* - 1)!

**34.** Use algorithm ALL_COSTS to obtain the lengths of the shortest paths between all pairs of vertices in the graph of exercise 31. Does ALL_COSTS give the right answers? Why?

**35.** Does the following set of precedence relations (<) define a partial order on the elements 1 thru 5? Why?

1 < 2; < 2 <4; 2 < 3, 3 < 4; 3 < 5: 5;< 1

**36. **a) For the AOE network below obtain the early, *e*( ), and late *l*( ), start times for each activity. Use the forward-backward approach.

b) What is the earliest time the project can finish?

c) Which activities are critical?

d) Is there any single activity whose speed up would result in a reduction of the project length?

**37.** Define a critical AOE-network to be an AOE-network in which all activities are critical. Let *G* be the undirected graph obtained by removing the directions and weights from the edges of the network.

**38.** Write a set of computer programs for manipulating graphs. Such a collection should allow input and input of arbitrary graphs. determining connected components and spanning trees. The capability of attaching weights to the edges should also be provided.

**39.** Make sure you can define the following terms.

adjacent(v) connected(v)_{p}, v_{q}

adjacent-to(v) connected(G)

adjacent-from(v) connected component

degree(v) strongly connected

in-degree(v) tree

out-degree(v) network

path spanning tree

simple path

cycle

subgraph