文档介绍：Computer Science and Information Engineering
National Chi Nan University
Discrete Mathematics
Dr. Justie Su-tzu Juan
Chapter 7 Relations: The Second
Time Around
§ Recognition: Zero-One
Matrices and Directed Graphs (2)
Slides for a Course Based on the Text
Discrete & Combinatorial Mathematics (5th Edition)
by Ralph P. Grimaldi
(c) Spring 2007, Justie Su-tzu Juan 1
§ Recognition: Zero-One Matrices and
Directed Graphs
Def : V: finite nonempty. A directed graph (or digraph) G
G = (V, E), where E V V is called the edge set, V is called
the vertex set.
v V is called the vertices or nodes of G
(a, b) E is called the (directed) edges or arcs of G
a is called the origin or source of (a, b)
b is called the terminus or terminating vertex of (a, b)
a is adjacent to b; b is adjacent from a
(a, a) is called a loop at a
isolated vertex
5
2
Ex : V = {1, 2, 3, 4, 5}, 1
E = {(1, 1), (1, 2), (1, 4), (3, 2)}
4 3
(c) Spring 2007, Justie Su-tzu Juan 2
§ Recognition: Zero-One Matrices and
Directed Graphs
a b a b
Def : If (a, b), (b, a) E, (a b), then use {a, b} = {b, a} to
represent. a and b are called adjacent vertices.
Ex : precedence graph for puter program
(S1) b := 3
(S2) c := b + 2
(S3) a := 1
(S4) d := a b + 5
(S5) e := d –1
(S6) f := 7
(S7) e := c + d
(S8) g := b f
(c) Spring 2007, Justie Su-tzu Juan 3
§ Recognition: Zero-One Matrices and
Directed Graphs
Ex : A = {1, 2, 3, 4}, R = {(1, 1), (1, 2), (2, 3), (3, 2), (3, 3),
(3, 4), (4, 2)}. The directed graph associated with R is G =
(A, R), where undirected edge {x, y} = (x, y) and (y, x).
The associated undirected graph:replace all edges (x, y) by
undirected edges {x, y}. back
1 1
2 2
G H
3 3
4 4
(c) Spring 2007, Justie Su-tzu Juan 4
§ Recognition: Zero-One Matrices and
Directed Graphs
Def : For an (directed) undirected graph G = (V, E):