Database Reference
In-Depth Information
join (
i
). For each of the three joins, how many times does it produce any square that
it produces at all?
!
EXERCISE
10.7.4 Show that the number of sequences of integers 1 ≤
i
≤
Hint
:
show that these sequences can be placed in a 1-to-1 correspondence with the binary strings
of length
b
+ 2 having exactly three 1's.
10.8 Neighborhood Properties of Graphs
There are several important properties of graphs that relate to the number of nodes one can
reach from a given node along a short path. In this section we look at algorithms for solving
problems about paths and neighborhoods for very large graphs. In some cases, exact solu-
tions are not feasible for graphs with millions of nodes. We therefore look at approximation
algorithms as well as exact algorithms.
10.8.1
Directed Graphs and Neighborhoods
In this section we shall use a directed graph as a model of a network. A
directed graph
has
a set of nodes and a set of
arcs
; the latter is a pair of nodes written
u
→
v
. We call
u
the
source
and
v
the
target
of the arc. The arc is said to be
from u to v
.
Many kinds of graphs can be modeled by directed graphs. The Web is a major example,
where the arc
u
→
v
is a link from page
u
to page
v
. Or, the arc
u
→
v
could mean that
telephone subscriber
u
has called subscriber
v
in the past month. For another example, the
arc could mean that individual
u
is following individual
v
on Twitter. In yet another graph,
the arc could mean that research paper
u
references paper
v
.
Moreover, all undirected graphs can be represented by directed graphs. Instead of the
undirected edge (
u, v
), use two arcs
u
→
v
and
v
→
u
. Thus, the material of this section also
applies to graphs that are inherently undirected, such as a friends graph in a social network.
A
path
in a directed graph is a sequence of nodes
v
0
, v
1
, . . . , v
k
such that there are arcs
v
1
→
v
i
+1
for all
i
= 0
,
1
, . . . , k
− 1. The
length
of this path is
k
, the number of arcs along the
path. Note that there are
k
+ 1 nodes in a path of length
k
, and a node by itself is considered
a path of length 0.
The
neighborhood of radius d
for a node
v
is the set of nodes
u
for which there is a path
of length at most
d
from
v
to
u
. We denote this neighborhood by
N
(
v, d
). For example,
N
(
v,
0) is always {
v
}, and
N
(
v,
1) is
v
plus the set of nodes to which there is an arc from
v
. More
generally, if
V
is a set of nodes, then
N
(
V, d
) is the set of nodes
u
for which there is a path
of length
d
or less from at least one node in the set
V
.
