10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
407
connected subset of the Web in the “center,” but that the Web as a whole is
not strongly connected. Rather, there are some pages that reach nowhere by
links, and some pages that cannot be reached by links.
If the graph is undirected, the deﬁnition of diameter is the same as for
directed graphs, but the path may traverse the undirected edges in either di-
rection. That is, we treat an undirected edge as a pair of arcs, one in each
direction. The notion of diameter makes sense in an undirected graph as long
as that graph is connected.
Example 10.30 : For the graph of Fig. 10.24, the diameter is 3. There are
some pairs of nodes, such as A and E, that have no path of length less than 3.
But every pair of nodes has a path from one to the other with length at most 3.
✷
We can compute the diameter of a graph by computing the sizes of its
neighborhoods of increasing radius, until at some radius we fail to add any
more nodes. That is, for each node v, ﬁnd the smallest d such that |N(v, d)| =
|N(v, d + 1)|. This d is the tight upper bound on the length of the shortest
path from v to any node it can reach. Call it d(v). For instance, we saw from
Example 10.29 that d(A) = 3 and d(B) = 2. If there is any node v such that
|N
v, d(v)

| is not the number of nodes in the entire graph, then the graph is
not strongly connected, and we cannot oﬀer any ﬁnite integer as its diameter.
However, if the graph is strongly connected, then the diameter of the graph is
maxv
d(v)

.
The reason this computation works is that one way to express N(v, d+ 1) is
the union of N(v, d) and the set of all nodes w such that for some u in N(v, d)
there is an arc u →w. That is, we start with N(v, d) and add to it the targets
of all arcs that have a source in N(v, d). If all the arcs with source in N(v, d)
are already in N(v, d), then not only is N(v, d + 1) equal to N(v, d), but all of
N(v, d + 2), N(v, d + 3), . . . will equal N(v, d). Finally, we observe that since
N(v, d) ⊆N(v, d+1) the only way |N(v, d)| can equal |N(v, d+1)| is for N(v, d)
and N(v, d + 1) to be the same set. Thus, if d is the smallest integer such that
|N(v, d)| = |N(v, d + 1)|, it follows that every node v can reach is reached by a
path of length at most d.
10.8.3
Transitive Closure and Reachability
The transitive closure of a graph is the set of pairs of nodes (u, v) such that
there is a path from u to v of length one or more. We shall sometimes write
this assertion as Path(u, v). related concept is that of reachability. We say node
u reaches node v if u = v or Path(u, v) is true.4 The problem of computing
the transitive closure is to ﬁnd all pairs of nodes u and v in a graph for which
Path(u, v) is true. The reachability problem is, given a node u in the graph,
ﬁnd all v ̸= u such that Path(u, v) is true.
4Note that both may be true, if there is a cycle involving node u.
