文档介绍：Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 8-1 Applications of L. P.
Duality-2
§ The Independent Set on Chordal
Graphs (Primal-Dual)
(c) Spring 2007, Justie Su-tzu Juan 1
The independent set on chordal
graphs (Primal-Dual)
 Def: Given a graph G,
 S V(G) is called an independent set if x y in S, xy E(G).
 C = {C1, C2, …, Ct} is called a clique cover of G if
a. 1 i t, Ci V(G), G(Ci) is a clique and
b. Ci V
1it
(G) = max{|S|: S is an independent set of G}.
 k(G) = min{|C |: C is a clique cover of G}.
 Ex:
v3 v4 G1 v3 v4
v v G2 v2
1 2 v7
(G ) = 2
v5 v6 v5 v6 2
(G1) = 3
v k(G2) = 3
k(G ) = 3 8
1 (c) Spring 2007, Justie Su-tzu Juan 2
The independent set on chordal
graphs (Primal-Dual)
 Thm: (G) k(G). (W. D. I.)
Proof.
For any independent set S and any clique cover C = {C1, C2, …, Ct}.
Let f: S  C where f(u) = Ci if u Ci.
Note that f is a 1 - 1 function:
u v S, if f(u) = f(v) = Ci for some 1 i t,
then u Ci and v Ci by definition of f.
∵ Ci is a clique uv E(G).
But u, v S, S is an independent set
 uv E(G) 
f(u) f(v).
|S| |C |
 max S min C (G) k(G).
S C
(c) Spring 2007, Justie Su-tzu Juan 3
The independent set on chordal
graphs (Primal-Dual)
 Remark: [v1, v2, …, vn] is a PEO.
 i j k, vivj E, vivk E  vjvk E
 i j, i k, i j, i k  j k
 Ci = {vj: j i, j i} is a clique.
 Ex:
3 45
1 2 7
54 6
8
(c) Spring 2007, Justie Su-tzu Juan 4
The independent set on chordal
graphs (Primal-Dual)
 Algorithm:
Given a chordal graph G with PEO [v1, v2, …, vn]
S* ;
C* ;
t  0;
for i = 1 to n do
if N[vi] S* = then
S*  S* {vi};
t  t + 1;
Ct {vj: j i, j i};
C*  C* Ct;
 plexity = O(|V|+|E|).
(c) Spring 2007, Justie Su-tzu Juan 5
The independent set on chordal
graphs (Primal-Dual)
 Ex:
v3 v4
v