Lecture 15 b

MST
Planar graph
Graph coloring
 Minimum Spanning Trees
Prim’s Algorithm

Kruskal’s Algorithm
 Definition
• A Minimum Spanning Tree (MST) is a
subgraph of an undirected graph such that
the subgraph spans (includes) all nodes, is
connected, is acyclic, and has minimum
total edge weight
 Algorithm Characteristics
• Both Prim’s and Kruskal’s Algorithms work
with undirected graphs
• Both work with weighted and unweighted
graphs but are more interesting when edges
are weighted
• Both are greedy algorithms that produce
optimal solutions
Prim’s Algorithm
 Walk-Through
2
Initialize
3
F C array
K d pv
10 v

A 7 3 A F  
8 4
18 B F  
4
9
B D C F  
10
H 25 D F  
2
3 E F  
G 7
E F F  
G F  
H F  
 2
Start with any node, say
3
F C D K d p
10 v v

A 7
4
3 A
8 B
18
4
9
B D C
10
H 25 D T 0 
2
3 E
G 7
E F
G
H
 2 Update distances of
adjacent, unselected
3
F C K
nodesd p
10 v v

A 7
4
3 A
8 B
18
4
9
B D C 3 D
10
H 25 D T 0 
2
3 E 25 D
G 7
E F 18 D
G 2 D
H
 2 Select node with
minimum distance
3
10
F C K dv pv
A 7
4
3 A
8 B
18
4
9
B D C 3 D
10
H 25 D T 0 
2
3 E 25 D
G 7
E F 18 D
G T 2 D
H
 2 Update distances of
adjacent, unselected
3
F C K
nodesd p
10 v v

A 7
4
3 A
8 B
18
4
9
B D C 3 D
10
H 25 D T 0 
2
3 E 7 G
G 7
E F 18 D
G T 2 D
H 3 G
 2 Select node with
minimum distance
3
10
F C K dv pv
A 7
4
3 A
8 B
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E 7 G
G 7
E F 18 D
G T 2 D
H 3 G
 2 Update distances of
adjacent, unselected
3
F C K
nodesd p
10 v v

A 7
4
3 A
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E 7 G
G 7
E F 3 C
G T 2 D
H 3 G
 2 Select node with
minimum distance
3
10
F C K dv pv
A 7
4
3 A
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E 7 G
G 7
E F T 3 C
G T 2 D
H 3 G
 2 Update distances of
adjacent, unselected
3
F C K
nodesd p
10 v v

A 7
4
3 A 10 F
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E 2 F
G 7
E F T 3 C
G T 2 D
H 3 G
 2 Select node with
minimum distance
3
10
F C K dv pv
A 7
4
3 A 10 F
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E T 2 F
G 7
E F T 3 C
G T 2 D
H 3 G
 2 Update distances of
adjacent, unselected
3
F C K
nodesd p
10 v v

A 7
4
3 A 10 F
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E T 2 F
G 7
E F T 3 C
G T 2 D
H 3 G
Table entries
unchanged
 2 Select node with
minimum distance
3
10
F C K dv pv
A 7
4
3 A 10 F
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E T 2 F
G 7
E F T 3 C
G T 2 D
H T 3 G
 2 Update distances of
adjacent, unselected
3
F C K
nodesd p
10 v v

A 7
4
3 A 4 H
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E T 2 F
G 7
E F T 3 C
G T 2 D
H T 3 G
 2 Select node with
minimum distance
3
10
F C K dv pv
A 7
4
3 A T 4 H
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E T 2 F
G 7
E F T 3 C
G T 2 D
H T 3 G
 2 Update distances of
adjacent, unselected
3
F C K
nodesd p
10 v v

A 7
4
3 A T 4 H
8 B 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E T 2 F
G 7
E F T 3 C
G T 2 D
H T 3 G
Table entries
unchanged
 2 Select node with
minimum distance
3
10
F C K dv pv
A 7
4
3 A T 4 H
8 B T 4 C
18
4
9
B D C T 3 D
10
H 25 D T 0 
2
3 E T 2 F
G 7
E F T 3 C
G T 2 D
H T 3 G
 2 Cost of Minimum
Spanning Tree =  dv = 21
3
F C K dv pv
A 4
3 A T 4 H
B T 4 C
4
B D C T 3 D
H D T 0 
2
3 E T 2 F
G E F T 3 C
G T 2 D
H T 3 G

Done
 Kruskal’s Algorithm

• Work with edges, rather than nodes

• Two steps:
– Sort edges by increasing edge weight
– Select the first |V| – 1 edges that do not
generate a cycle
 Walk-Through
Consider an undirected, weight
3
F C graph
10
A 4
4
3
8
6
5
4
B D
4
H 1
2
3
G 3
E
 Sort the edges by increasing edge
3
F C weight
edge d edge d
10 v v

A 4 3 (D,E) 1 (B,E) 4
8 4
6 (D,G) 2 (B,F) 4
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2 (B,F) 4
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
4
8
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
4
8
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

Accepting edge (E,G) would create a

cycle
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
4
8
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
4
8
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
4
8
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4 (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
4
8
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
4
8
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
4
8
6 (D,G) 2  (B,F) 4 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
4
8
6 (D,G) 2  (B,F) 4 
5
4
B D (E,G) 3  (B,H) 4 
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
4
8
6 (D,G) 2  (B,F) 4 
5
4
B D (E,G) 3  (B,H) 4 
4
H 1
(C,D) 3  (A,H) 5 
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
 Select first |V|–1 edges which do
not generate a cycle
3
F C edge dv edge dv

A 3 (D,E) 1  (B,E) 4 
4
(D,G) 2  (B,F) 4 
5
B D (E,G) 3  (B,H) 4 
H 1
(C,D) 3  (A,H) 5 
2
 (D,F) 6

}
3 (G,H) 3
not
G E (C,F) 3  (A,B) 8 considere
d
(B,C) 4  (A,F) 10

Done
Total Cost =  dv = 21
Examples 1 – 5 from textbook
Design efficient way to schedule Examination
 An application of graph coloring in scheduling
Twelve faculty members in a mathematics department serve on the
following committees:
 Undergraduate education: Sineman, Limitson, Axiomus, Functionini
 Graduate Education: Graphian, Vectorades, Functionini, Infinitescu
 Colloquium: Lemmeau, Randomov, Proofizaki
 Library: Van Sum, Sineman, Lemmeau
 Staffing: Graphian, Randomov, Vectorades, Limitson
 Promotion: Vectorades, Van Sum, Parabolton

The committees must all meet during the first week of classes, but
there are only three time slots available. Find a schedule that will
allow all faculty members to attend the meetings of all committees
on which they serve.
 An application of graph coloring in exam scheduling
Suppose that in a particular quarter there are students taking each of the
following combinations of courses:
 Math, English, Biology, Chemistry
 Math, English, Computer Science, Geography
 Biology, Psychology, Geography, Spanish
 Biology, Computer Science, History, French
 English, Psychology, Computer Science, History
 Psychology, Chemistry, Computer Science, French
 Psychology, Geography, History, Spanish
What is the minimum number of examination periods required for
the exams in the ten courses specified so that students taking any
of the given combinations of courses have no conflicts? Find a
schedule that uses this minimum number of periods.