Geology Reference
In-Depth Information
Fig. A2.2
An arc linking two nodes in a data structure
of different type and length. The important thing
is that in any case a logical relationship exists
between the elements of the set, which must
be implemented for consistent computation and
data retrieval. As an example, a set of tectonic
elements, faults, and site locations could be char-
acterized by hierarchical relations between the
set items, according to a kinematic model. A
data structure
¢
on
D
can be defined as a binary
function on
D
2
:
¢
W
x
i
;x
j
2
D
2
Fig. A2.3
An example of directed graph of order 5 and
size 7
!
¢
ij
2f
0;1
g
(A2.2)
nodes are drawn without arrows and represent
pairs
of arcs. These lines are called
edges
.Data
structures represented by
asymmetric
adjacency
matrices are called
directed graphs
or
digraphs
(Fig.
A2.3
). In general, the number
n
of vertices
in a graph
G
D
(
D
,¢) is called
order
of
G
, while
the number
m
of arcs or edges is referred to as the
size
of
G
. Two nodes are
adjacent
when they are
joined by an edge or an arc. The
neighborhood
I
(
x
) of a node
x
is the set of nodes adjacent to
x
,
and the number of elements in
I
(
x
) is called the
degree
of
x
.A
path
between two vertices
x
and
y
is a sequence of nodes (
x
,
x
0
,
x
00
, :::,
y
), such that
x
0
is adjacent to
x
,
x
00
is adjacent to
x
0
,etc.Iftwo
nodes are joined by an arc directed from
x
to
y
,we
say that
x dominates y
,or
x
!
y
. Therefore, the
existence of a path between
x
and
y
can be written
as:
x
!
x
0
!
x
00!
:::
!
y
. Now let us consider
the matrix
A
2
, whose elements are given by:
This function simply establish the existence
of a qualitative
logical
relation between two el-
ements
x
i
and
x
j
when ¢
ij
D
1. When a data
structure is defined on a set
D
, the elements of
D
are referred to as the
nodes
or the
vertices
of the
structure, while the fact that ¢
ij
D
1 is rendered
graphically drawing an
arc
between nodes
x
i
and
x
j
(Fig.
A2.2
).
Mathematically, the pair (
D
,¢)issaidtobea
graph
, and the binary function ¢ is represented
through a square binary matrix of order
n
,which
is called
adjacency matrix
. For example, the
function ¢ associated with the graph of Fig.
A2.3
is
represented
by
the
following
adjacency
matrix:
2
4
3
5
00100
01001
01000
10100
00010
X
n
A
D
A
ij
D
A
ik
A
kj
(A2.3)
kD1
Clearly, for each value of the dummy index
k
,theterm
A
ik
A
kj
contributes to the sum if and
only if
x
i
!
x
k
and
x
k
!
x
j
, thereby there exists
the path (
x
i
,
x
k
,
x
j
). Therefore, the element
A
ij
rep-
resents the number of paths of length two joining
nodes
x
i
and
x
j
. We can extend this concept to
When
A
is a symmetric matrix, so that
A
ij
D
A
ji
for each pair of indices
i
and
j
,then
the existence of an arc from a node
x
i
to a node
x
j
implies the existence of a reversed arc from node
x
j
to node
x
i
. In this instance, the lines linking
