Information Technology Reference
In-Depth Information
,where
N
is a
set
n
odes, (or
vertices
), and
E
is a set of
e
dges (or
arcs
), such that, for any
e
A simple (unoriented)
graph
G
isspecifiedbyapair
G
=(
N
,
E
)
E
,
an unordered pair of nodes of
N
is specified that are
c
onnected trough
e
(the graph
is
oriented
if the pairs of nodes associated to edges are ordered pairs, it is a
multi-
graph
if different edges connect a same pair of notes). Rooted trees can naturally be
expressed as graphs where an edge is set between every node and its father.
Basic terminology and example of trees and graphs are given in Chap. 1 (here
we recall that ”parent, child, sibling” are also used instead of ”father, son, brother”,
or ”mother, daughter, sister”;
f
∈
(
y
)=
x
means that
x
is father of
y
,and
y
is son of
x
,
andwhenalso
f
x
that
x
and
y
are brothers). In particular, a
path
of a graph
is a sequence of nodes where two successive nodes are connected by an edge of the
graph. A
cycle
is a path where the last node is connected with the first node. A graph
is
connected
if there is a path between any pair of nodes in the graph. Moreover, it
can be shown that the previous characterization of rooted tree is equivalent to that of
acyclic (without cycles) and connected graph with one particular node, chosen as its
root (if no root is chosen, the structure is an
unrooted tree
). Definitions by induction
of trees and graphs can be found in Sect. 5.5.
Rooted trees and graphs can be easily represented by means of diagrams, where a
node is a point (or a closed region of space) and an edge is a curve connecting points
(regions). In terms of diagrams, a rooted tree has a root point, which branches with
other son points which possibly branch again. The terminal nodes which do not
continue this process are the
leaves
of the tree. Tags can be added to nodes and
edges of trees and graphs, which represent specific kinds of information relevant to
particular cases of application.
(
z
)=
7.8.1
Types of Trees
The study of trees started with the research of Arthur Cayley who developed an
enumeration method in 1875 for calculating the number of isomers of branched
alkanes
.
There are many subtle aspects which identify different notions of trees. Usually,
in the case of trees the attribute “labeled” without further specification means that
nodes are distinguishable elements, while “unlabeled” means that nodes are not dis-
tinguishable for themselves, but only for their positions in the tree. In other words,
the individual identity of each node is not relevant in the definition of the tree (how-
ever this terminology is not uniform, because very often labels are used as tags,
allowing different nodes to have the same label/tag). When specific values are as-
signed to nodes (and edges) of a tree, for avoiding any confusion with the attributes
labeled and unlabeled, we say that the tree is
d
ecorated.(unfortunately this notation
is not uniform in the literature).
The tree given in Fig. 7.11 is a decorated tree (by numbers and operations).
If among the sons of a node an order is assumed, then the tree is called an
ordered
tree
. Genealogical trees are ordered (this was an important issue in royal families,
for deciding the crown rights).
