Information Technology Reference
In-Depth Information
abcde f
a
000100
b
000100
c
000100
d
000011
e
000000
f
000000
C
=
.
Shortly, we denote this matrix by “Adjacency IM” (AdIM).
Obviously, the columns indexed by
a
f
contain
only zeros and do not give any information. So, we can transform the AdIM to the
form
,
b
,
c
and the rows, indexed by
e
,
de f
a
100
b
100
c
100
d
011
D
=
,
in which the isolated vertices are omitted. This new
(
0
,
1
)
-IM can be called “reduced
An important question is whether this modification is a correct one. Really, we
see that the connections between the immediate neighbouring vertices of the graph
are seen, but we must check the basic property of the standard adjacency matrix
X
,
that the elements of the multiplication
X
2
X
represent the connections
between the vertices through one step (see e.g., [31]). Using the operation
=
X
(
×
,
+
)
(
max
,
min
)
(see (1.3), p. 3, we obtain for the
(
0
,
1
)
-IM
D
de f
a
100
b
100
c
100
d
011
de f
a
100
b
100
c
100
d
011
de f
a
011
b
011
c
011
d
000
D
(
max
,
min
)
D
=
(
max
,
min
)
=
Now, we illustrate the results of the applications of different operations over
(
0
,
1
)
-IMs, that represent some oriented graphs. Let us have the graph
E
Search WWH ::
Custom Search