Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

(Martin Jones) #1

CHAP. 9] DIRECTED GRAPHS 227


However, when there are many, many flights, such a representation does not easily answer the following
natural questions:
(i) Is there a direct flight from cityXto cityY?
(ii) Can one fly from cityXto cityY?
(iii) What is the most direct route (minimum number of stops) from cityXto cityY?
Show how the answer, say, to (ii) may be more readily available if the data is stored in memory using the
linked representation of the graph as in Fig. 9-26(b).
One way to answer (ii) is to use a breadth-first or depth-first search algorithm to decide whether cityYis reachable
from cityX. Such algorithms require the adjacency lists, which can easily be obtained from the linked representation
of a graph, but not from the above representation which uses only three fields.

MISCELLANEOUS PROBLEMS


9.15. LetA=





0201
0011
2110
0011




⎦be the adjacency matrix of a multigraphG. Draw a picture ofG.

SinceAisa4×4 matrix,Ghas four vertices,v 1 ,v 2 ,v 3 ,v 4. For each entryaijinA, drawaijarcs (directed edges)
from vertexvito vertexvjto obtain the graph in Fig. 9-27(a).

Fig. 9-27
9.16. LetSbe the cycle-free graph in Fig. 9-27(b). Find all possible topological sorts ofS.
There are four possible topological sorts ofS. Specifically, each sortTmust begin with eitheraorb, must end with
eorf, andcanddmust be the third and fourth elements, respectively. The four sorts follow:
T 1 =[a, b, c, d, e, f],T 2 =[b, a, c, d, e, f]
T 3 =[a, b, c, d, f, e],T 4 =[b, a, c, d, f, e]

9.17. Prove Proposition 9.4: LetAbe the adjacency matrix of a graphG. ThenaK[i,j], theij-entry in the matrix
AK, gives the number of paths of lengthKfromvitovj.
The proof is by induction onK. A path of length 1 fromvitovjis precisely an edge(vi,vj). By definition of the
adjacency matrixA,a 1 [i, j]=aijgives the number of edges fromvitovj. Hence the proposition is true forK=1.
SupposeK>1. (AssumeGhasmnodes.) SinceAK=AK−^1 A,

aK[i, j]=

∑m

s= 1

aK− 1 [i, s]a 1 [s, j]

By induction,aK− 1 [i,s] gives the number of paths of lengthK−1 fromvitovsanda 1 [s,j] gives the number of
paths of length 1 fromvstovj. ThusaK− 1 [i,s]a 1 [s,j] gives the number of paths of lengthKfromvitovjwhere
vsis the next-to-last vertex. Thus all paths of lengthKfromvitovjcan be obtained by summing up the product
aK− 1 [i,s]a 1 [s,j] for alls.Accordingly,aK[i,j] is the number of paths of lengthKfromvitovj.Thus the proposition
is proved.
Free download pdf