10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
421
(a) If the graph is represented as a directed graph, how many arcs are there?
(b) What are the neighborhood proﬁles for nodes A and B?
(c) What is the diameter of the graph?
(d) How many pairs are in the transitive closure? Hint: Do not forget that
there are paths of length greater than zero from a node to itself in this
graph.
(e) If we compute the transitive closure by recursive doubling, how many
rounds are needed?
Exercise 10.8.2: The smart transitive closure algorithm breaks paths of any
length into head and tail of speciﬁc lengths. What are the head and tail lengths
for paths of length 7, 8, and 9?
! Exercise 10.8.3: Fill in the values of the table in Fig. 10.25 for the versions of
the algorithms for reachability, linear TC and recursive doubling if the seminaive
trick is not used.
! Exercise 10.8.4: In Section 10.8.9 we observed that the sum of the out-degrees
of the nodes in a directed graph equals the number of arcs in the graph. There
is a similar relationship for an undirected graph, between the degrees of its
nodes and its number of edges. Find and prove this relationship.
Exercise 10.8.5:
Consider the running example of a social network, last
shown in Fig. 10.24. Suppose we use one hash function h which maps each
node (capital letter) to its ASCII code. Note that the ASCII code for A is
01000001, and the codes for B, C, . . . are sequential, 01000010, 01000011, . . . .
(a) Using this hash function, compute the values of R for each node and
radius 1. What are the estimates of the sizes of each neighborhood? How
do the estimates compare with reality?
(b) Next, compute the values of R for each node and radius 2. Again compute
the estimates of neighborhood sizes and compare with reality.
(c) The diameter of the graph is 3. Compute the value of R and the size
estimate for the set of reachable nodes for each of the nodes of the graph.
(d) Another hash function g is one plus the ASCII code for a letter. Repeat
(a) through (c) for hash function g. Take the estimate of the size of a
neighborhood to be the average of the estimates given by h and g. How
close are these estimates?
