Biology Reference
In-Depth Information
Fig. 1.1 An undirected graph ( left ), a directed graph ( center ) and a partially directed graph ( right )
G
) if all arcs are undirected, and partially directed or mixed graphs
(denoted with G
=(
V
,
E
)
) if they contain both directed and undirected arcs.
Examples of directed , undirected ,andmixed partially directed graphs are shown
in Fig. 1.1 in that order. For the undirected graph, Fig. 1.1 :
=(
V
,
A
,
E
)
The node set is V
= {
A
,
B
,
C
,
D
,
E
}
and the edge set is E
= {
(A
B), (A
C),
(A
D), (B
D), (C
E), (D
E)
}
.
Arcs are undirected, so, i.e., A
BandB
A are equivalent and identify the
same edge.
Likewise, A is connected to B, B is connected to A, and A and B are adjacent.
For the directed graph, Fig 1.1 :
The node set is V
= {
A
,
B
,
C
,
D
,
E
}
and the graph is characterized by an arc
set A
= {
(A
B), (C
A), (D
B), (C
D), (C
E)
}
instead of an edge
set E .
Arcs are directed, so, i.e., A
BandB
A identify different arcs. For instance,
A
A . Under the additional constraint of acyclicity, it is
not possible for both arcs to be present in the graph because there can be at most
one arc between each pair of nodes.
B
A while B
A
Bisan
outgoing arc for A (the tail), an incoming arc for B (the head), and an incident
arc for both A and B.
On the other hand, the partially directed graph, Fig. 1.1 , is characterized by the
combination of an edge set E
Also, A and B are adjacent, as there is an arc (A
B) from A to B. A
= {
}
=
(A
C), (A
D), (C
D)
and an arc set A
{
.
An undirected graph can always be constructed from a directed or partially
directed one by substituting all the directed arcs with undirected ones; such a graph
is called the skeleton or the underlying undirected graph of the original graph.
(D
E), (E
B)
}
1.1.2 The Structure of a Graph
The pattern with which the arcs appear in a graph is referred to as either the structure
of the graph or the configuration of the arcs. In the context of this topic it is assumed
Search WWH ::




Custom Search