文档介绍：Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 2. Mathematical Preliminaries
§ Graphs and digraphs
Slides for a Course Based on the Text
Combinatorial Optimization -
Networks and Matroids
by Eugene Lawler
(c) Spring 2007, Justie Su-tzu Juan 1
Graphs and digraphs
 Def:
 A graph is an ordered pair G = (V, E), where
V(G) = V is a finite non-empty set of vertices (or nodes) and
E(G) = E is a set of un-ordered pairs of vertices, called edges
(or links).
 If {x, y}, {y, z} E, then we say
1. x and y are adjacent;
2. x is incident to {x, y};
3. {x, y} and {y, z} are adjacent;
4. denote {x, y} by (x, y) or xy.
 Ex. 1 2 3
V = {1, 2, 3, 4, 5, 6, 7, 8, 9}
4 5 6 E = {12, 23, 14, 25, 36, 45, 56, 47,
58, 69, 78, 89}
7 8 9
(c) Spring 2007, Justie Su-tzu Juan 2
Graphs and digraphs
 Def:
 A digraph or directed graph is an ordered pair D = (V, A), where
V(D) = V is a finite non-empty set of vertices (or nodes) and
A(D) = A is a set of ordered pairs of vertices, called arcs
(or edges).
 If (x, y) A, then we say
1. (x, y) are incident from x and incident to y.
2. x is adjacent to y, y is adjacent from x.
(c) Spring 2007, Justie Su-tzu Juan 3
Graphs and digraphs
 Def:
 The incidence matrix of a graph G, M(G) = (bik), is defined as
follows:
1, if node i is incident to edge k,
b =
ik 0, otherwise.
 In the case of a digraph, the incidence matrix, M(G) = (bik) is
defined as follows:
–1, if arc k is incident to node i,
bik = 1, if arc k is incident from node i,
0, otherwise.
e ee1 ee2 ee3 e4e e5e e6e e7 e e8
e 12 1 2 3 4 5 6 7
 Ex. 11 2e5 1
e4 1 11 1 11 00 0 0 0 00 00
2 1 0 0 1 1 0 0 0
e ee32 e 2 1 0 1 1 1 1 0
GD 13 3 5 4 3 0 1 0 1 0 1 1 0 
e6 e4 3 0 1 0 1 0 1 1
e e7 4 0 0 1 0 0 1 0 1
e 6 e 4 0 0 0 0 1 0 1 
4 2 3 5 7 5 0 0 0 0 1 0 1 1 
e8
(c) Spring 2007, Just