Graph Theory

DIGRAPHS DIRECTED GRAPHS or DIGRAPHS for short, are used to model situations in which there is a partial ordering between objects. A DIGRAPH is a pair G = (V, E) where V is a finite set of vertices and E is a relation on V. The elements of E are called arcs and they are depicted as directed edges linking related ordered pairs of vertices. In a simple digraph there are no loops or multiple edges. Hence, there is at most one arc uv from vertex u to vertex v, and at most one arc vu from vertex v to vertex u. If uv is an arc, u is called an ANTECEDENT of v. For example,

a b

c d

is a simple digraph with vertex set V = {a, b, c, d} and arc set E = {ab, bd, cb, db, dc}. The adjacency matrix is:

F T F F F F F T F T F F F T T F

a b c d

a b c d

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

[a, c and d are all antecedents of b] A CYCLE in a digraph is a sequence of vertices v0, v1, . . . , vk such that vi−1vi is an arc for i = 1 to k, the first and last vertices are the same and no other vertices (or arcs) are repeated. If there are no such cycles, G is called an ACYCLIC digraph. Acyclic digraphs are useful as models of situations in which given tasks need to be implemented in a certain order. In task-scheduling problems the corresponding acyclic digraph is known as a PERT chart.

DIGRAPHS 133

EXAMPLE 11.1 As part of a Biosciences degree programme a student wishes to include the eight modules listed in the table below. Draw a PERT chart to illustrate the given prerequisite structure.

prerequisite modules Advanced Biotechnology B Biotechnology C Cell Biology H DNA Structures C Enzyme Activity D, G Food Science E Genetic Engineering C Human Biology none

Solution

■

Suppose the student wants to find an order in which to take the modules which is consistent with the given prerequisites. This can be achieved by using the following TOPOLOGICAL SORT ALGORITHM. The vertices of the digraph are labelled 1, 2, . . . , n such that when uv is an arc and u has label i and v has label j, then i < j. This is called a CONSISTENT LABELLING

DIGRAPHS 134

THE TOPOLOGICAL SORT ALGORITHM {The algorithm produces a consistent labelling of an acyclic digraph G = (V, E). Initially, A(v) contains the antecedents of each vertex v.} begin for v ∈ V do

calculate A(v); label := 0; while unlabelled vertices v remain for which A(v) = Ø do begin

label := label + 1; u := a vertex with A(u) = Ø; assign label to u; for each unlabelled vertex v∈V do A(v) := A(v) – {u}; end end The algorithm successively assigns labels to vertices. A vertex receives the smallest available label whenever it has no unlabelled antecedents. EXAMPLE 11.2 Find a consistent labelling for the digraph in Example 11.1. Solution Before entering the while loop for the first time we calculate the antecedent sets. A(A) = {B} A(E) = {D, G} A(B) = {C} A(F) = {E} A(C) = {H} A(G) = {C} A(D) = {C} A(H) = Ø Now we enter the while loop for the first time and assign label 1 to vertex ____ and delete all references to that vertex to obtain A(A) = {B} A(E) = {D, G} A(B) = {C} A(F) = {E} A(C) = Ø A(G) = {C} A(D) = {C}

DIGRAPHS 135

On the second pass through the while loop we assign label 2 to vertex ___ and delete all references to that vertex to obtain A(A) = {B} A(E) = {D, G} A(B) = Ø A(F) = {E} A(D) = Ø A(G) = Ø This gives some choice as to the next vertex to be labelled. Each choice leads to a different consistent labelling. As shown on pp. 152-3 of Haggarty, one possible consistent labelling is H, C, B, A, D, G, E, F.

■ Directed graphs can be used to represent such things as airline routes between various cities in the world, or communication paths between computers in a computer network. In such networks it is important to know the consequences of the temporary removal of any link (arc or vertex), on the overall network. For example, if aircraft cannot land for refuelling in some city due to adverse weather conditions, it may be impossible to reroute to reach other cities. Similarly, if one or more paths in a computer network fail, some computer users may no longer be able to access certain servers. We therefore address the problem of determining the existence of paths between any two vertices in a directed graph. Let G = (V, E) be a digraph with n vertices and M be its adjacency matrix. An entry of T in the matrix M indicates the existence of an arc in G; an arc is a path of length 1. The logical Boolean product of M with itself is M 2. Each T entry in M 2 indicates the existence of a path of length 2. Paths of length 3 are recorded as T entries in the matrix M 3 = M.M.M and so on. Finally, the REACHABILITY MATRIX

M* = M or M 2 or . . . or M n records the existence of paths of some length between vertices. [The logical or of two matrices (with the same number of rows and the same number of columns) is defined to be the result of forming the logical or of corresponding entries.]

DIGRAPHS 136

DIGRAPHS 137

EXAMPLE 11.3 Calculate the reachability matrix of the following digraph:

a b

c d

Solution

F T F F F F T T

F F F F F F T F

M =

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

2

F T F F F T F F F F T T F F T T

= F F F F F F F F F F T F F F T F

M =

⎡ ⎤ ⎡ ⎤ ⎡ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎥ ⎢⎣ ⎦ ⎣ ⎦ ⎣

⎤ ⎥ ⎥ ⎥ ⎥⎦

Further calculation gives

3

F F T F F F F F

F F F F F F F F

M =

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

4

F F F F F F F F

F F F F F F F F

M =

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

Therefore,

* M =

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦

■

There are more efficient algorithms for computing M* such as WARSHALL’S algorithm. See pp. 155-157 of Haggarty for further details.

We now consider the problem of finding a shortest path between any two vertices in a weighted digraph. This has obvious applications to transport networks and communications networks. Consider the following WEIGHTED DIGRAPH for which we seek the shortest path from vertex A to each of the other vertices.

B 1 C

2 5

A 4 F

3 1

D 2 E

We shall use DIJKSTRA’S ALGORITHM, one of many shortest path algorithms. For each vertex v in the digraph, we assign the label d[v] to represent the distance from A to v. Initially d[v] is the weight of the edge (A, v), if such an edge exists, or ∞ otherwise. We traverse the vertices of the digraph and improve the computed value of d[v] as we go. At each step of the algorithm a vertex u is marked once we are sure that we have found the best route to it. For the remaining unmarked vertices v, the label d[v] is replaced by the minimum of its current value and the distance to v via the last marked vertex u. The algorithm terminates once all vertices have received their final label and all possible vertices have been marked. For each step described below, we generate a row in a table which records the vertex to be marked, the current values of d[v] and the remaining unmarked vertices. Step 0 Since we are to start at A, we use the first row of ω for the initial values of d[v]. Since A is closest to A we mark A.

Step

Vertex to be marked

Distance to vertex

A B C D E F

Unmarked vertices

0 A 0 2 ∞ 3 ∞ ∞ B,C,D,E,F

Step 1

DIGRAPHS 138

Mark B, since B is the closest unmarked vertex to A, and calculate distances to unmarked vertices via B. If a shorter distance is found use this. In this instance, A→ B→C is 3 and A→B→E is 6, whereas previously d[C] and d[E] were ∞.

Step

Vertex to be marked

Distance to vertex

A B C D E F

Unmarked vertices

0 A 0 2 ∞ 3 ∞ ∞ B,C,D,E,F 1 B 0 2 3 3 6 ∞ C, D, E, F

Step 2 Of the remaining unmarked vertices D and C are closest to A. We arbitrarily pick D to mark first. Because the path A→D→E has length 5, the current value of d[E] can be updated to 5.

Step

Vertex to be marked

Distance to vertex

A B C D E F

Unmarked vertices

0 A 0 2 ∞ 3 ∞ ∞ B,C,D,E,F 1 B 0 2 3 3 6 ∞ C, D, E, F 2 D 0 2 3 3 5 ∞ C, E, F

Step 3 Now C is still closest to A, so we mark it and recompute distances. The vertex F can be accessed for the first time by the path A→B→C→F, and so d[F] = 8.

Step

Vertex to be marked

Distance to vertex

A B C D E F

Unmarked vertices

0 A 0 2 ∞ 3 ∞ ∞ B,C,D,E,F 1 B 0 2 3 3 6 ∞ C, D, E, F 2 D 0 2 3 3 5 ∞ C, E, F 3 C 0 2 3 3 5 8 E, F

Step 4/Step 5 We mark E next, which reduces the distance to F from 8 to 6. Finally mark F.

Step

Vertex to be marked

Distance to vertex

A B C D E F

Unmarked vertices

0 A 0 2 ∞ 3 ∞ ∞ B,C,D,E,F 1 B 0 2 3 3 6 ∞ C, D, E, F 2 D 0 2 3 3 5 ∞ C, E, F 3 C 0 2 3 3 5 8 E, F 4 E 0 2 3 3 5 6 F 5 F 0 2 3 3 5 6

The shortest distances from A to all vertices are recorded in the final line of the table above: so d[A] = 0, d[B] = 2, d[C] = 3, d[D] = 3, d[E] = 5 and d[F] = 6.

DIGRAPHS 139

With care the shortest paths can be recovered from this table by examining when each vertex first receives its final label. For example, the shortest path from A to F is A→D→E→F. For completeness we now give the full algorithm which not only computes the shortest distances from the start vertex but also records the shortest path involved. DIJKSTRA’S ALGORITHM {Let (V, E) be a weighted digraph and A be a vertex. The algorithm finds the shortest path PATHTO(v) from A to any vertex v and the overall distance d[v]. For vertices u and v, ω(u, v) is the ‘weight’ of the arc uv.} begin for each v∈V do begin d[v] := ω(A, v); PATHTO(v) := A; end Mark vertex A; while unmarked vertices remain that have finite distance from A do begin u := unmarked vertex whose distance from A is minimal; Mark vertex u; for each unmarked vertex v with uv∈E do begin d' := d[u] + ω(u, v) if d' < d[v] then begin d[v] := d'; PATHTO(v):= PATHTO(u), v; end end end end

DIGRAPHS 140

Communication Networks Computer networks can be modelled by digraphs in which the vertices (or nodes) represent computing devices, and the arcs are communication links. Each arc is assigned a weight which represents the capacity of the link for communication purposes. For example, the following represents a simple 7-node network

1 2 3

4 5 6

7

5

5

5

3

3

3

3

3

2

2

2

2

2

4

4

4

4

1

Once a network has been installed the problem arises as to how messages can be routed between non-adjacent nodes. A static routing procedure uses information about link capacities to determine a set of fixed routes between nodes. An algorithm such as Dijkstra’s is used to find the optimal paths through the network. This approach is vulnerable to failure in links or network nodes, and delays can occur when the capacity of a link is exceeded. A dynamic routing procedure continually updates link capacities in the light of changing demands. A protocol, or set of rules, is devised to enable individual nodes to decide when and where to transmit new information. Each node maintains its own set of routing tables and so routing calculations are distributed throughout the network. For the network above, each node runs Dijkstra’s algorithm to determine the best paths to other nodes and stores this information in a tree whose root is the ‘home node’.

DIGRAPHS 141

For example, for node 1 we obtain the following tree:

1

2

5

6 7

3

4

5

3

2

1

4 5

To forward messages each node maintains a table that indicates the neighbour to which to pass a message for each destination. For node 1 this table is as follows:

Destination 2 3 4 5 6 7 Next node 2 2 4 4 4 4

EXAMPLE 11.4 Use Dijkstra’s algorithm to find the shortest paths from node 2 to all the other nodes in the network above. Hence, draw the tree of shortest paths and construct the routing table for node 2. Solution

Step

Marked vertex

Distance to vertex 1 2 3 4 5 6 7

Unmarked vertices

0 2 4 0 3 3 ∞ ∞ ∞ 1,3,4,5,6,7 1 2 3 4 5 6

DIGRAPHS 142

The tree of shortest paths and the corresponding routing table are as follows:

Destination 1 3 4 5 6 7 Next node

■

DIGRAPHS 143

EXERCISES 11 - DIGRAPHS 11.1 Draw the digraph with vertices {1, 2, 3, 4, 5, 6} whose adjacency matrix is:

T F F T F F T F T F F T F T T F T F T F F T T T F F F T F T F T T T T F

L

N

M M M M M M M

O

Q

P P P P P P P

Suppose that each arc has weight 1. Find by inspection (if they exist) (a) the shortest path(s) from 1 to 2, (b) the shortest path(s) from 3 to 6, (c) a cycle of length five. 11.2 Apply the Topological Sort algorithm to the digraph whose adjacency matrix

is: a b c d e f

a b c d e f

F F F T F F T F F F F T F T F F T F F F F F F T F F F T F T F F F F F F

L

N

M M M M M M M

O

Q

P P P P P P P

Rewrite the matrix with the rows and columns ordered by the new labels. What

pattern can you see in the new version? What would happen if you applied the Topological Sort algorithm to the

digraph in Exercise 11.1?

DIGRAPHS 144

11.3 Given the following task chart, find a total ordering in which the tasks can be performed sequentially.

Task Prerequisite Tasks

A Chop onions I B Wash lettuce K C Make dressing K D Do stir fry J E Toss salad B, C F Cut up chicken None G Grate ginger I H Chop bok choy I I Marinate chicken F J Heat wok A, G, H, K

K Prepare rice None 11.4 A digraph G has adjacency matrix

M =

F T F F F F T F F F F T T F F F

L

N

M M M M

O

Q

P P P P

Calculate M 2, M 3and M 4. Hence, find the reachability matrix M*. 11.5. Use Dijkstra’s algorithm to find the shortest distance to each vertex (a) from vertex A , (b) from vertex C.

B 4 E

3 12 2 6

A 11 D 8 F 10 5

C

11.6 This question concerns the 7-node network given on page 220.

(a) If the delay from node 2 to node 4 decreases from 3 to 1, determine a shortest path tree and routing table for node 2.

(b) What happens to the shortest path tree and routing table for node 2 if the

links between nodes 5 and 6 are removed?

DIGRAPHS 145

SOLUTIONS TO EXERCISES 11 – DIGRAPHS 11.1 (a) The shortest path from 1 to 2 is 1, 4, 6, 2. (b) The shortest paths from 3 to 6 are 3, 5, 6 or 3, 2, 6 (c) For example, the cycle 1, 4, 6, 3, 2, 1 is a cycle of length five. 11.2 (a) The initial antecedent sets are A(a) = {b}, A(b) = {c}, A(c) = Ø, A(d) = {a, e}, A(e) = {c}

and A(f) = {b, d, e}. So label c(1) and remove c and associated edges. Then A(a) = {b}, A(b) = Ø, A(d) = {a, e}, A(e) = Ø and A(f) = {b, d, e}. So, for instance, label b(2) and remove b and associated edges. Then A(a) = Ø, A(d) = {a, e}, A(e) = Ø and A(f) = {d, e}. So, for instance, label a(3) and remove a and associated edges. Then A(d) = {e}, A(e) = Ø and A(f) = {d, e}. So label e(4) and remove e and associated edges. Then A(d) = Ø and A(f) = {d}. So label d(5) and remove d and associated edges. Finally, A(f) = Ø. So label f(6). This gives the consistent labelling, c(1), b(2), a(3), e(4), d(5) and f(6). (b) The new adjacency matrix is

c b a e d f c b a e d f

F T F T F F F F T F F T F F F F T F F F F F T T F F F F F T F F F F F F

L

N

M M M M M M M

O

Q

P P P P P P P

The use of the ordering of vertices in a consistent labelling allows us to store just the upper

triangular portion of the adjacency matrix of the digraph. The graph in Exercise 11.1 is such that none of the antecedent sets is empty - hence the

graph contains cycles and so there is no consistent labelling of its vertices. 11.3 The PERT chart is as follows:

A B C D

E F

G H

I J K

DIGRAPHS 146

The initial antecedent sets are A(A) = {I}, A(B) = {K}, A(C) = {K}, A(D) = {J}, A(E) = {B, C}, A(F) = Ø, A(G) = {I}, A(H) = {I}, A(I) = {F}, A(J) = {A, G, H, K} and A(K) = Ø. So label F as 1, K as 2 and remove F, K and associated arcs.

Then A(A) = {I}, A(B) = Ø, A(C) = Ø, A(D) = {J}, A(E) = {B, C}, A(G) = {I}, A(H) = {I}, A(I)

= Ø and A(J) = {A, G, H}. So label B as 3, C as 4, I as 5 and remove B, C and I and associated arcs.

Then A(A) = Ø, A(D) = {J}, A(E) = Ø, A(G) = Ø, A(H) = Ø and A(J) = {A, G, H}. So label A as 6, E as 7, G as 8, H as 9 and remove A, E, G and H and associated arcs. Then A(D) = {J} and A(J) = Ø. Finally label J as 10, remove J and associated arcs, and then

label D as 11. This gives the consistent labelling, F, K, B, C, I, A, E, G, H, J, D. 11.4

M 2 = =

F T F F F F T F F F F T T F F F

L

N

M M M M

O

Q

P P P P

F T F F F F T F F F F T T F F F

L

N

M M M M

O

Q

P P P P

F F T F F F F T T F F F F T F F

L

N

M M M M

O

Q

P P P P

M 3 = =

F T F F F F T F F F F T T F F F

L

N

M M M M

O

Q

P P P P

F F T F F F F T T F F F F T F F

L

N

M M M M

O

Q

P P P P

F F F T T F F F F T F F F F T F

L

N

M M M M

O

Q

P P P P

M 4 = =

F T F F F F T F F F F T T F F F

L

N

M M M M

O

Q

P P P P

F F F T T F F F F T F F F F T F

L

N

M M M M

O

Q

P P P P

T F F F F T F F F F T F F F F T

L

N

M M M M

O

Q

P P P P

Therefore,

M* = M or M 2 or M 3 or M 4 =

T T T T T T T T T T T T T T T T

L

N

M M M M

O

Q

P P P P

DIGRAPHS 147

DIGRAPHS 148

11.5 (a)

Step Marked ver tex

Distance to vertex A B C D E F

Unmarked vertices

0 A 0 3 10 ∞ ∞ ∞ B, C, D, E, F 1 B 0 3 10 15 ∞ ∞ C, D, E, F 2 C 0 3 10 15 ∞ ∞ D, E, F 3 D 0 3 10 15 17 23 E, F 4 E 0 3 10 15 17 23 F 5 F 0 3 10 15 17 23

1 2 shortest distances from A

44444 344444

(b)

Step Marked ver tex

Distance to vertex A B C D E F

Unmarked vertices

0 C ∞ ∞ 0 5 ∞ ∞ A, B, D, E, F 1 D ∞ ∞ 0 5 7 13 A, B, E, F 2 E ∞ 11 0 5 7 13 A, B, F 3 B ∞ 11 0 5 7 13 A, F 4 F ∞ 11 0 5 7 13 A

1 2 shortest distances from C

44444 344444

11.6 (a) Running Dijkstra’s algorithm with the delay on link 24 reset to 1 produces:

Step Marked ver tex

Distance to vertex 1 2 3 4 5 6 7

Unmarked vertices

0 2 4 0 3 1 ∞ ∞ ∞ 1,3,4,5,6,7 1 4 3 0 3 1 2 ∞ ∞ 1,3,5,6,7 2 5 3 0 3 1 2 6 7 1,3,6,7 3 1 3 0 3 1 2 6 7 3,6,7 4 3 3 0 3 1 2 6 7 6,7 5 6 3 0 3 1 2 6 7 7 6 7 3 0 3 1 2 6 7

There are several shortest path trees one of which is:

2

156

7

3 4 23

1

1

5

3

The corresponding routing table is:

Destination 1 3 4 5 6 7 Next node 4 3 4 4 3 4

(b) The link 56 is not used from node 2 and so there is no change to the tree or the routing table

calculated in Example 11.4.

DIGRAPHS 149

DIGRAPHS 150

FUNCTIONS.pdf

• EXAMPLE 7.1