1.3 Directed graphs
A directed graph or digraph D is a finite nonempty set of objects called vertices together with a set of ordered pairs of distinct vertices of D called arcs or directed edges.
The vertex set of D
and the arc set is denoted by and
, respectively.
Example: and
Figure 2.10. A directed graph
If is
an arc in a directed graph, then
- if i > j then a is called as forward arc,
- if i < j then a is called as forward arc.
Let be an arc of a digraph D. Then a is said to join
u and v, or we say that a is incident from u and incident
to v, while u is incident
to a and v is incident
from a. Moreover, u is said to be adjacent to v and v is adjacent from u.
Two vertices u and v are nonadjacent in D, if u is neither adjacent to nor adjacent from v in D.
The outdegree of a vertex v
in D is the number of vertices of D that are adjacent from v.
The indegree of a vertex v
in D is the number of vertices of D that are adjacent to v.
The degree of a vertex of D
is defined by
.
A digraph D1 is isomorphic to a digraph D2 if there exists a
one-to-one mapping , called an isomorphism, from
onto
such that
iff
. We denote it by D1 = D2.
A labeled digraph D1 is a subdigraph of a labeled digraph D
if and
.
A subdigraph D1 of D is a spanning subdigraph if D1 has the same order as D.
A digraph is called symmetric,
if whenever is an arc of D, then
is also.
A digraph D is
called asymmetric digraph or an oriented graph if whenever is an arc of D, then
is not an arc of D. (So, an oriented
graph can be obtained from a graph G by assigning a direction to each
edge of G.)
A digraph D is
complete if for every two distinct vertices u and v of D,
at least one of the arcs and
is present in D. The complete symmetric
digraph of order n has both arcs
and
for every two distinct vertices u and v and is denoted by
.
A complete asymmetric digraph is called a tournament.
A digraph D is
called r-regular if for every vertex v of D.
A digraph D is connected (or weakly connected) if the underlying graph of D is connected.
A digraph D is
strong (or strongly) connected if for every pair u, v of
vertices, D contains both a path and a
path.
For vertices u
and v in a digraph D containing a u-v path, the (directed)
distance from u to v is the length of a
shortest
path in D.
The eccentricity of a vertex u in D is the distance from u to a vertex farthest from u.
The minimum
eccentricity of the vertices of D is the radius of D, while the diameter
is the greatest eccentricity.
If one allows more than one edge (but yet finite number) between the same pair of vertices in a graph, the resulting structure is a multigraph.
The edges between the same pair of vertices are called parallel edges.
If more than one arc in the same direction is permitted to join two vertices in a digraph, it results in a multidigraph.
A loop is an edge (or arc) that joins a vertex to itself.