Information Technology Reference
In-Depth Information
Fig. 7.12
The bar diagram of the expression
(((
2
+
3
)
×
5
)+(
2
3
×
5
))
The diagram of Fig. 7.12 is another way of expressing the hierarchical structure of
the the expression
2
3
.
Rooted trees, expressions (built with parentheses), branched diagrams, are equiv-
alent concepts, expressing some kind of hierarchy among components.
(((
2
+
3
)
×
5
)+(
×
5
))
7.8.2
Types of Graphs
Edges of graphs can be oriented or not (oriented edges express arrows). The
degree
of a node in a graph is the number of edges connected to the node (in the oriented
case it is possible to distinguish entering and exiting edges, consequently,
in
and
out
degree). A graph is complete if every node is directly connected by an edge
to every other node. Figure 7.13 shows the graph
K
3
,
3
, investigated by Kuratowski,
consisting of six nodes where vertices can be partitioned into two disjoint sets of
three nodes, and where every node of one set is connected to every node of the other
set. Figure 7.14 shows the complete graph
K
5
on five nodes.
We call
hypergraph
is a graph where nodes are graphs. This terminology is not
standard, because usually the term refers to a generalization of a graph in which
an edge can connect any number of vertices. Here, the term is used by analogy
with
hyperset, hypersequence, and hypermultiset
(that is, structures consisting of
Fig. 7.13
Kuratowski's graph
