Biology Reference
In-Depth Information
Chapter 1
Introduction
Abstract
Bayesian networks and their applications to real-world problems lie at the
intersection of several fields such as probability and graph theory. In this chapter a
brief introduction to the terminology and the basic properties of graphs, with partic-
ular attention to directed graphs, is provided. As with other Use R!-series topics, a
brief introduction to the
R
environment and basic
R
programming is also provided.
Some background in probability theory and programming is assumed. However, the
necessary references are included under the respective sections for a more complete
treatment.
1.1 A Brief Introduction to Graph Theory
1.1.1 Graphs, Nodes, and Arcs
=(
,
)
Agraph
G
consists of a nonempty set
V
of
nodes
or
vertices
and a finite
(but possibly empty) set
A
of pairs of vertices called
arcs
,
links
,or
edges
.
Each arc
a
V
A
can be defined either as an ordered or an unordered pair of
nodes, which are said to be
connected
by and
incident
on the arc and to be
adjacent
to each other. Since they are adjacent,
u
and
v
are also said to be
neighbors
.If
=(
u
,
v
)
)
is an ordered pair,
u
is said to be the
tail
of the arc and
v
the
head
; then the arc is
said to be
directed
from
u
to
v
and is usually represented with an arrowhead in
v
(
u
(
u
,
v
v
). It is also said that the arc
leaves
or is
outgoing
for
u
and that it
enters
or
is
incoming
for
v
.If
→
is unordered,
u
and
v
aresimplysaidtobeincidenton
the arc without any further distinction. In this case, they are commonly referred to
as
undirected arcs
or
edges
, denoted with
e
(
u
,
v
)
∈
E
and represented with a simple line
(
u
v
).
The characterization of arcs as directed or undirected induces an equivalent char-
acterization of the graphs themselves, which are said to be
directed graphs
(de-
noted with
G
−
=(
V
,
A
)
) if all arcs are directed,
undirected graphs
(denoted with
Search WWH ::
Custom Search