Ramex: A Sequence Mining Algorithm Using Poly-trees - New Contributions in Information Systems and Technologies - page 135

2.3 Graphs, Trees and Poly-trees Concepts

Given a connected undirect
connects all the vertexes. A
weight that is lower than o
problem is easily solved
Kruskal and Prim are well-k
chosen without worrying a
cycles. In Prim's algorithm
An oriented tree is a dir
the exception of the root, w
A poly-tree is a relaxed
pair of nodes, where the in
tree was coined by [18] an
Bayesian Networks.
A tree, with a node in
greater than one and a direc
nodes are shown in Figure 1

ted graph, a spanning tree of the graph is a sub-graph t
A minimum weight spanning tree is the spanning tree wit
or equal to the weight of every other spanning tree. T
using a greedy algorithm. The algorithms proposed
known examples [9]. In Kruskal's algorithm, the edges
about the connections to previous edges, but avoiding
the tree grows from an arbitrary root.
rect acyclic graph with a node in-degree equal to one, w
where the in-degree is equal to zero.
d oriented tree, with one (and only one) path between
n-degree of a node can be greater than one. The term po
nd the poly-tree algorithm is well-known for inference

that
th a
This
by
are
the

with

any
oly-
e in

-degree equal to one, a poly-tree, with a node in-deg
ct acyclic graph, with two or more paths between a pai
1.

gree
r of

Fig. 1. (a) tree, (b) poly-tree and (c) direct acyclic graph