Geology Reference
In-Depth Information
which would contradict the starting hypothesis.
As a consequence, such a path cannot exist and
G
is a tree.
any other node
x
. Let us assume now that a node
x
can be found such that
x
!
r
. In this instance,
the arc from
x
to
r
would form, together with the
path from
r
to
x
, a cycle. This would contradict
the hypothesis that
G
is a rooted tree. Therefore,
r
cannot have incoming arcs. Let us consider now
a node
x
¤
r
. Clearly,
x
has at least one incoming
arc, because there exists a path joining
r
to this
node. Let us assume that
x
has more than one
input arcs, and let
z
and
y
be two nodes such that
z
!
x
and
y
!
x
. Two distinct paths exist that join
r
with
z
and
y
. Therefore, extending these paths
by the arcs
z
!
x
and
y
!
x
, we would obtain
two alternative paths that reach
x
starting from the
root. This would be in contrast with the definition
of rooted tree, thereby a node
x
¤
r
must have
a unique incoming arc. We also observe that
removal of any arc
x
!
y
would cause
y
to be un-
reachable, thereby the tree would be decomposed
in two disjoint parts. As a consequence, the root
r
is the only node devoid of incoming arcs. Now, let
G
be a directed graph containing a unique node
r
without incoming arcs and let us assume that any
other node has just one incoming arc. We want to
prove that in this case
G
is a rooted tree. To this
purpose, we first observe that at most one path
can exist joining
r
to any other node
x
, because
the presence of two alternative paths from
r
to
a node
x
implies the existence of a convergence
node that could coincide with
x
or an “upstream”
node. This node would have two input arcs, in
contrast with the starting hypothesis. Regarding
the acyclicity of
G
, it is sufficient to observe
that the root
r
cannot be included in any cycle,
while any cycle not including
r
should have at
least an input arc at some node
z
. This node
would be joined to the root through a path that
external to the cycle, and to itself through the
cyclic path. Therefore,
z
would have two incom-
ing arcs, which contrasts the starting hypothesis.
Consequently,
G
is a rooted tree.
Theorem A2.2
A graph G is a tree iff G is
connected and m
D
n
1.
Proof
Given a tree
G
of order
n
, we can prove
that
m
D
n
1 by induction. In fact, it is trivially
true that if
n
D
1then
m
D
0. Let us assume now
that the equality is proved up to some order
n
1,
and consider a tree of order
n
. If we remove
the edge joining two adjacent nodes
x
and
y
,
we obtain two disjoint subtrees
G
1
and
G
2
, each
having order
n
i
<
n
(
i
D
1,2) and size
m
i
D
n
i
1.
Therefore:
m
D
m
1
C
m
2
C
1
D
n
1
C
n
2
1
D
n
1
Conversely, let
G
be connected and
m
D
n
1.
We must prove now that
G
is acyclic. To this
purpose, let us assume that a cyclic path
c
exists
in
G
. If we remove an edge from
c
, we obtain a
graph that is still connected and of the same order
of
G
, but the size will be decreased to
n
2. This
result is clearly impossible, because a connected
graph must have at least
n
1 edges. Therefore,
G
must be acyclic, thereby it is a tree.
Let us consider now a subclass of tree struc-
tures that has great practical interest: the
rooted
trees
. These graphs are directed acyclic structures
characterized by the existence of a special node
r
,
called the
root
, from which it is possible to reach
any other vertex in the graph through unique
paths (Fig.
A2.6
). The following theorem de-
termines all the fundamental properties of these
graphs:
Theorem A2.3
A directed connected graph G is
a rooted tree iff
:(
a
)
there exists a unique un-
reachable node r in G
(
that is
,
without incoming
arcs
); (
b
)
any other node in the graph has one
input arc. Furthermore, removal of a single arc
separates G in two disjoint subtrees
.
The previous theorem has the immediate
corollary that the adjacency matrix
A
will have
a column, corresponding to the root, whose
elements are all zero. Conversely, the remaining
columns will have one element set to unity
and
n
1 elements set to zero. Therefore, the
Proof
Let
G
be a rooted tree. In this instance,
there exists a unique path joining the root
r
with
