Directed Graph: Dr. Safaa O. Al-Mamory

Directed Graph
Dr. Safaa O. Al-mamory

Department of Software 1
Review
PlanarGraph
 A graph or multigraph which can be drawn in the plane so
that its edges do not cross is said to be planar.
Maps & Regions
 A particular planar representation of a finite planar
multigraph is called a map. We say that the map is
connected if the underlying multigraph is connected.
 A given map divides the plane into various regions.
 By the degree of a region r, written deg(r), we mean the
length of the cycle or closed walk which borders r.
 The sum of the degrees of the

regions of a map is equal to twice
the number of edges.
Graph Coloring
 A vertex coloring, or simply a coloring of G is an
assignment of colors to the vertices of G such that adjacent
vertices have different colors.
 We say that G is n-colorable if there exists a coloring of G
which
 The minimum number of colors needed to paint G is called
the chromatic number of G and is denoted by χ(G). uses n
colors.
Dual Maps & The Four Color Theorem
 Any planar graph is 4-colorable
Welch-Powell Coloring Algorithm
 .
Welch-Powell Coloring Algorithm
 A5,A1
 A3,A4,A8
 A7,A2,A6
 So, it is 3-colorable.
DiGraph
 A directed graph,or digraph,consists of:
 a set V ,whose elements are called vertices,
 a set E,whose elements are called directed edges or
arcs,and an incidence function that assigns to each edge a
tail and a head. The tail of an arc is the vertex it
leaves,and the head is the vertex it enters. E
 A strict digraph has no
D
self-loops or multi-arcs.
C
Department of Software A 9
In Degree & Out Degree
 If <v0, v1> is an edge in a directed graph
 v0 is adjacent to v1, and v1 is adjacent from v0
 The edge <v0, v1> is incident on v0 and v1
 The in-degree of a vertex v is the number of edges
that have v as the head
 The out-degree of a vertex v is the number of edges
that have v as the tail
 The degree of v, or deg(u), is the sum of its indegree and
outdegree. A vertex with indegree 0 is a source and with
outdegree 0 a sink.
In Degree & Out Degree (Cont.)
 If di is the degree of a vertex i in a graph G with n vertices
and e edges, the number of edges is
n 1
e( d )/ 2
0
i
 Since adjacent vertices each count the adjoining edge, it

will be counted twice
0 in:1, out: 1
 Example
1 in: 1, out: 2
Department of Software 2 in: 1, out: 0 11

Adjacency Matrix
 Suppose digraph D contains n vertices v1, v2, ... , vn. The
adjacency matrix of D is the matrix A = (aij)n×n, where aij
equals 1 if a directed edge runs from vi to vj and 0 otherwise.
Reachability
 Aclosed path is a cycle. If a directed path runs from vq to vn,
vn is reachable from vq.
 Is there some way to determine if a vertex Vj in a digraph is
reachable from a vertex u?
Strongly Connected Graph
 A digraph D is strongly connected if every vertex in D is
reachable from every other vertex.
 Theorem
 According to the Theorem, the digraph D is strongly

connected if and only if rij > 0 for every i  j. The matrix R
is the reachability matrix of the digraph.
Example
 Is the digraph D strongly connected?
 Since every element off the main diagonal of R is nonzero,

the digraph is strongly connected. 15
Department of Software
Weighted Digraph
 A weighted digraph is a digraph with a weight assigned to
each directed edge. The weight of the edge (x,y) is denoted
by w(x,y).
 The weight of the edge (a,c) is 5; that is, w(a,c) = 5.
 The weight of a path in a weighted digraph is the sum of the
weights of the edges along the path. For instance, the weight
of the path a-c-b-d-z in Figure 10.32 is 5 + 1 + 1 + 7 = 14,
and that of c-b-d-e-z is 7.
Weighted Adjacency Matrix
 .
Shortest Path
 A path of least weight from vertex u to vertex v in a
weighted digraph is a shortest path from u to v.
 An efficient method was developed in 1959 by the Dutch
mathematician Edsger W. Dijkstra, a pioneer in the art of
computer programming.
 Dijkstra‘s algorithm can find a shortest path from any
vertex to any vertex in the digraph, if it exists, as the next
example demonstrates.
Dijkstra’s Algorithm
 Example 1
Dijkstra’s Algorithm (Cont.)
 Example 2
Dijkstra’s Algorithm (Cont.)
 A
Be ready for the
exam on the next
lecture
References
1. Seymour Lipschutz, and Marc Lipson, “Schaum’s
Outlines: Discrete Mathematics,” 3rd edition, McGraw-
Hill, 2007.
2. Rosen, Discrete Mathematics and Its Applications, 6th
edition, 2007.
3. Kevin Ferland, Discrete Mathematics, An Introduction
To Proofs And Combinatorics, Richard Stratton, 2009.
4. Thomas Koshy, Discrete Mathematics with Applications,
Elsevier Press, 2004.
Thank You for
Listening.

Directed Graph: Dr. Safaa O. Al-Mamory

Uploaded by

Copyright:

Available Formats

Directed Graph: Dr. Safaa O. Al-Mamory

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Directed Graph: Dr. Safaa O. Al-Mamory

Uploaded by

Copyright:

Available Formats

Directed Graph

Dr. Safaa O. Al-mamory

 The sum of the degrees of the

 Since adjacent vertices each count the adjoining edge, it

Department of Software 2 in: 1, out: 0 11

 According to the Theorem, the digraph D is strongly

 Since every element off the main diagonal of R is nonzero,

You might also like