Data Structures, Algorithms, & Applications in C++
Chapter 16, Exercise 15
- (a)
-
This can be proved by construction. For
any
n,
n >= 2, consider the digraph
Gn =
({1, 2, ..., n}, {(1, 2), (2, 3), (3, 4), ...,
(n-1,
n),
(n, 1)}).
Gn
is simply an n vertex directed cycle.
Gn
is readily seen to be strongly connected. Also, |E| =
n.
- (b)
-
Let
G =
(V,E) be any
n vertex strongly connected
digraph. Since G contains a directed path
from i
to j
and from j
to i for every pair of
vertices i
and j,
diin >= 1 and
diout >= 1, 1 <=
i
<= n. Hence, the sum of the in-degrees and out-degrees of all
vertices is
>= 2n. If
|E| =
e,
then the sum of the in-degrees and out-degrees is
2e (Property 17.2). So,
2e >=
2n or
e >=
n.