Transcript No Slide Title - Extras Springer

Graph Colouring Heuristics
Contents
1. Classroom Assignment Problem
2. Graph Colouring Problem
3. Graph Colouring Heuristics (saturation degree)
Literature
• Operations Scheduling with Applications in Manufacturing
and Services, Michael Pinedo and Xiuli Chao, McGraw Hill, 2000
Chapter 8.4.
• Deterministic Scheduling Theory, Gary Parker,
Chapman & Hall, 1995.
1
Classroom Assignment Problem
Possible constraints:
• Two classes may not meet simultaneously in the same room.
• A given class cannot meet in two different rooms.
Possible objectives:
• Find a schedule of all classes that requires the fewest numbers of
rooms.
• Find any room assignment satisfying the number of rooms available.
2
G = (V, E)
vertices: classes
edges: if two classes have a required period in common
and they must be in separate rooms
Example.
Prove that at least three rooms are needed to schedule the five classes
in the periods indicated as follows:
Class
A
Periods (1,4)
B
(1,3)
C
(2,4)
D
(3,5)
E
(2,5)
B
A
C
E
D
3
Graph colouring problem: can the vertices of a graph be coloured
using p colours so that no two vertices connected by an edge are both
assigned the same colour?
Chromatic number of a graph: minimum number of colours necessary
to colour the vertices of a graph, so that no two vertices connected by
an edge are both assigned the same colour.
 NP complete problem
Degree of a vertex: number of edges connected to that vertex.
Saturation level of a vertex: number of differently coloured vertices
already connected to it.
4
Graph Colouring Heuristics (saturation degree)
Step 1.
Arrange the vertices in decreasing order of their degree.
Step 2.
Colour a vertex of maximal degree with colour 1.
Step 3.
Choose an uncoloured vertex with maximal saturation degree.
If there is a tie choose any one of the vertices
with maximal degree in the uncoloured subgraph
Step 4.
Colour the selected vertex using the colour with
the lowest possible number
Step 5.
If all vertex are coloured then STOP
else go to step 3.
5
Classes
Period 1
Period 2
Period 3
Period 4
Period 5
Degree
Satur.
Deg. uncol
A
1
0
0
1
0
2
-
B
1
0
1
0
0
2
1
1
C
0
1
0
1
0
2
1
1
D
0
0
1
0
1
2
0
2
E
0
1
0
0
1
2
0
2
B
A
C
E
D
6
B
A
C
E
Classes
Satur.
Deg. uncol
A
-
D
B
-
C
1
1
D
1
1
E
0
2
7
B
A
C
E
Classes
Satur
Deg. uncol
A
-
D
B
-
C
-
D
1
1
E
1
1
8
B
A
C
E
D
9
Classes
Period 1
Period 2
Period 3
Period 4
Period 5
Degree
Satur.
Deg. uncol
Satur.
Deg. uncol
Satur
Deg. uncol
A
1
0
0
1
0
2
-
B
1
0
1
0
0
2
1
1
-
C
0
1
0
1
0
2
1
1
1
1
-
D
0
0
1
0
1
2
0
2
1
1
1
1
E
0
1
0
0
1
2
0
2
0
2
1
1
B
A
C
E
D
10
Exercise
Consider scheduling the vertex with the lowest degree first.

If the high degree jobs are not scheduled early on,
they often end up requiring new colours at the end of the process.
11