Information Technology Reference
In-Depth Information
Ta b l e 5 . 1 5
The sequence of prime numbers
p
2
p
(
n
+
1
)=
min
{
j
|
j
>
p
(
n
)
and
p
(
i
)
is not a divisor of
j
for
i
≤
n
}
(
1
)=
The induction principle is a powerful tool in the analysis of discrete structures.
Tables 5.16, 5.17, and 5.18 provide inductive definitions of tree and graph over a
set
A
of labels (see Figs. 5.7 and 5.8). In particular, the definition of Table 5.17 is a
special form of inductive definition, usually referred as
recursive definition
(a tree
is defined in terms of smaller trees).
Ta b l e 5 . 1 6
The inductive definition of rooted ordered trees over the set
A
Basis step
: A single vertex is a rooted tree.
Induction step
:If
T
1
,
T
2
,...,
T
k
are disjoint rooted trees with roots
r
1
,
r
2
,...,
r
k
∈
A
,
respectively, then, starting with an element
r
∈
A
such that
r
=
r
1
,
r
=
r
2
,...,
r
=
r
k
,
and adding an edge from
r
to each of roots
r
1
,
r
2
,...,
r
k
a new tree is obtained having
r
as its root and trees
T
1
,
T
2
,...,
T
k
as its
subtrees
.
Ta b l e 5 . 1 7
The recursive definition of rooted ordered trees over the set
A
A finite non-empty set
T
⊆
A
of
nodes
is a tree if the following conditions hold:
i) there is a node
r
∈
T
called the
root
of
T
ii) the remaining nodes of
T
/{
r
}
are partitioned into
m
≥
0 sets, and each of them is a
tree over
A
, called a
subtree
of
T
.
An infinite tree is a tree having an infinite set of nodes
N
. An infinite tree is said
to be
finitary
if every node of the tree has a finite number of children. An important
result about infinite trees, based on induction, is the following proposition known as
K onig lemma
.
Proposition 5.2.
An infinite finitary rooted tree has an infinite path.
Proof.
In fact, if
r
is the root of the tree, then an infinite path
(
p
n
|
n
∈
N)
can be
defined by induction by putting
p
0
=
r
, which is the root of an infinite tree, and for
any
n
,if
p
n
has been already defined, as the root of an infinite tree, then surely it
has a child
q
which is the root of an infinite tree, therefore we define
p
n
+
1
=
∈
N
q
.
