Information Technology Reference
In-Depth Information
I
+
A
+
···
+
A
K−
1
, multiply both sides by
I
+
A
:
(
I
+
A
)
K
(
I
+
A
)
K−
1
=
I
+
A
)
×
=
I
+
A
)
×
(
I
+
A
+
···
+
A
K−
1
)
I
+(
A
+
A
)+
···
+(
A
K−
1
+
A
K−
1
)+
A
K
=
However, since
A
j
is a Boolean matrix,
A
j
+
A
j
=
A
j
for all
j
and the result follows.
The adjacency matrix
A
of the graph in Fig.
6.3
is given below along with its powers up to
the fifth power. Note that every non-zero entry appearing in
A
5
appears in at least one of the
other matrices. The reason for this fact is explained in the proof of Lemma
6.4.2
.
⎡
⎤
⎡
⎤
⎡
⎤
00101
00100
00010
01000
10000
10010
00010
01000
00100
00101
01101
01000
00100
00010
10010
⎣
⎦
⎣
⎦
⎣
⎦
A
2
=
A
3
=
A
=
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
10110
00100
00010
01000
01101
01111
00010
01000
00100
10110
A
4
=
A
5
=
LEMMA
6.4.2
If there is a path between pairs of vertices in the directed graph
G
=(
V
,
E
)
,
n
=
1
.
Proof
We suppose that the shortest path between vertices
i
and
j
in
V
has length
k
|
V
|
,thereisapathoflengthatmost
n
−
≥
n
.
Such a path has
k
+
1 vertices. Because
k
+
1
n
+
1, some vertex is repeated more than
once. (This is an example of the pigeonhole principle.) Consider the subpath defined by the
edges between the first and last instance of this repeated vertex. Since it constitutes a loop,
it can be removed to produce a shorter path between vertices
i
and
j
. This contradicts the
hypothesis that the shortest path has length
n
or more. Thus, the shortest path has length
at most
n
≥
−
1.
1, any non-zero entries in
A
k
,
k
Because the shortest path has length at most
n
−
≥
n
,are
also found in one of the matrices
A
j
,
j
1. Since the identity matrix
I
is the adjacency
matrix for the graph that has paths of length zero between two vertices, the transitive closure,
which includes such paths, is equal to:
≤
n
−
A
∗
=
I
+
A
+
A
2
+
A
3
+
+
A
n−
1
=(
I
+
A
)
n−
1
···
It also follows that
A
∗
=(
I
+
A
)
k
for all
k
≥
n
−
1, which leads to the following result.
THEOREM
6.4.1
Over the basis
Ω=
{
AND
,
OR
}
the transitive closure function,
f
(
n
)
A
∗
,hascircuit
size and depth satisfying the following bounds (that is, a circuit of this size and depth can be
Search WWH ::
Custom Search