Solutions - Bayesian Networks in R: With Applications in Systems Biology - page 122

Solutions

Exercises of Chap. 1

1.1 Consider a directed acyclic graph with n nodes.

(a) Show that at least one node must not have any incoming arc, i.e., the graph
must contain at least one root node.
(b) Show that such a graph can have at most

1
2 n

( n − 1 ) arcs.

1 arcs.
(d) Describe an algorithm to determine the topological ordering of the graph.

(c) Show that a path can span at most n −

(a) Let G be a directed graph in which each node has at least one outgoing

arc. This is equivalent to saying that each node has at least one incoming arc;
therefore, G does not have any root node. Choose a vertex v 1

=( V , A )

∈ V .Since v 1

has an outgoing arc, there is a vertex v 2 such that v 1 → v 2 . Proceeding in this

v n spanning all the nodes in G .But v n also
has an outgoing arc; therefore, the graph is not acyclic.
(b) Choose a vertex v 1

manner, we obtain a path v 1 → ...→

∈ −

V . v 1 can have at most n 1 outgoing arcs. Consider now

a second node v 2 = v 1

would create a cycle and is therefore disregarded. By induction, we have that

v 1 . v 2 can have at most n − 2 outgoing arcs; the arc v 2 →

n
2

n ( n − 1 )

| A | ( n − 1 )+( n − 2 )+ ... +( 1 )= = .

2

(c) Suppose, by contradiction, that there exists a path spanning n arcs. A path can
(by definition) pass at most once through each node, and the path is spanning
n 1 nodes. Therefore, the path is passing twice through at least one node,

implying that the path is in fact a cycle. This contradicts the assumption that the
graph is acyclic.
(d) Two simple ways of determining the topological ordering of a directed acyclic
graph are the breadth-first search and the depth-first search algorithms, de-
scribed in Bang-Jensen and Gutin ( 2009 )and Russell and Norvig ( 2009 ).

+