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
AdIM”. It will be discussed in Chap. 5 .
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 )
=
(cf. the first example from Sect. 2.1 ) .
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