”;
Map colouring problem states that given a graph G {V, E} where V and E are the set of vertices and edges of the graph, all vertices in V need to be coloured in such a way that no two adjacent vertices must have the same colour.
The real-world applications of this algorithm are – assigning mobile radio frequencies, making schedules, designing Sudoku, allocating registers etc.
Map Colouring Algorithm
With the map colouring algorithm, a graph G and the colours to be added to the graph are taken as an input and a coloured graph with no two adjacent vertices having the same colour is achieved.
Algorithm
-
Initiate all the vertices in the graph.
-
Select the node with the highest degree to colour it with any colour.
-
Choose the colour to be used on the graph with the help of the selection colour function so that no adjacent vertex is having the same colour.
-
Check if the colour can be added and if it does, add it to the solution set.
-
Repeat the process from step 2 until the output set is ready.
Examples
Step 1
Find degrees of all the vertices −
A – 4 B – 2 C – 2 D – 3 E – 3
Step 2
Choose the vertex with the highest degree to colour first, i.e., A and choose a colour using selection colour function. Check if the colour can be added to the vertex and if yes, add it to the solution set.
Step 3
Select any vertex with the next highest degree from the remaining vertices and colour it using selection colour function.
D and E both have the next highest degree 3, so choose any one between them, say D.
D is adjacent to A, therefore it cannot be coloured in the same colour as A. Hence, choose a different colour using selection colour function.
Step 4
The next highest degree vertex is E, hence choose E.
E is adjacent to both A and D, therefore it cannot be coloured in the same colours as A and D. Choose a different colour using selection colour function.
Step 5
The next highest degree vertices are B and C. Thus, choose any one randomly.
B is adjacent to both A and E, thus not allowing to be coloured in the colours of A and E but it is not adjacent to D, so it can be coloured with D’s colour.
Step 6
The next and the last vertex remaining is C, which is adjacent to both A and D, not allowing it to be coloured using the colours of A and D. But it is not adjacent to E, so it can be coloured in E’s colour.
Example
Following is the complete implementation of Map Colouring Algorithm in various programming languages where a graph is coloured in such a way that no two adjacent vertices have same colour.
#include<stdio.h>
#include<stdbool.h>
#define V 4
bool graph[V][V] = {
{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0},
};
bool isValid(int v,int color[], int c){ //check whether putting a color valid for v
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}
bool mColoring(int colors, int color[], int vertex){
if (vertex == V) //when all vertices are considered
return true;
for (int col = 1; col <= colors; col++) {
if (isValid(vertex,color, col)) { //check whether color col is valid or not
color[vertex] = col;
if (mColoring (colors, color, vertex+1) == true) //go for additional vertices
return true;
color[vertex] = 0;
}
}
return false; //when no colors can be assigned
}
int main(){
int colors = 3; // Number of colors
int color[V]; //make color matrix for each vertex
for (int i = 0; i < V; i++)
color[i] = 0; //initially set to 0
if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring
printf("Solution does not exist.");
}
printf("Assigned Colors are: n");
for (int i = 0; i < V; i++)
printf("%d ", color[i]);
return 0;
}
Output
Assigned Colors are: 1 2 3 1
#include<iostream>
using namespace std;
#define V 4
bool graph[V][V] = {
{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0},
};
bool isValid(int v,int color[], int c){ //check whether putting a color valid for v
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}
bool mColoring(int colors, int color[], int vertex){
if (vertex == V) //when all vertices are considered
return true;
for (int col = 1; col <= colors; col++) {
if (isValid(vertex,color, col)) { //check whether color col is valid or not
color[vertex] = col;
if (mColoring (colors, color, vertex+1) == true) //go for additional vertices
return true;
color[vertex] = 0;
}
}
return false; //when no colors can be assigned
}
int main(){
int colors = 3; // Number of colors
int color[V]; //make color matrix for each vertex
for (int i = 0; i < V; i++)
color[i] = 0; //initially set to 0
if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring
cout << "Solution does not exist.";
}
cout << "Assigned Colors are: n";
for (int i = 0; i < V; i++)
cout << color[i] << " ";
return 0;
}
Output
Assigned Colors are: 1 2 3 1
public class mcolouring {
static int V = 4;
static int graph[][] = {
{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0},
};
static boolean isValid(int v,int color[], int c) { //check whether putting a color valid for v
for (int i = 0; i < V; i++)
if (graph[v][i] != 0 && c == color[i])
return false;
return true;
}
static boolean mColoring(int colors, int color[], int vertex) {
if (vertex == V) //when all vertices are considered
return true;
for (int col = 1; col <= colors; col++) {
if (isValid(vertex,color, col)) { //check whether color col is valid or not
color[vertex] = col;
if (mColoring (colors, color, vertex+1) == true) //go for additional vertices
return true;
color[vertex] = 0;
}
}
return false; //when no colors can be assigned
}
public static void main(String args[]) {
int colors = 3; // Number of colors
int color[] = new int[V]; //make color matrix for each vertex
for (int i = 0; i < V; i++)
color[i] = 0; //initially set to 0
if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring
System.out.println("Solution does not exist.");
}
System.out.println("Assigned Colors are: ");
for (int i = 0; i < V; i++)
System.out.print(color[i] + " ");
}
}
Output
Assigned Colors are: 1 2 3 1
V = 4
graph = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]
def isValid(v, color, c): # check whether putting a color valid for v
for i in range(V):
if graph[v][i] and c == color[i]:
return False
return True
def mColoring(colors, color, vertex):
if vertex == V: # when all vertices are considered
return True
for col in range(1, colors + 1):
if isValid(vertex, color,
col): # check whether color col is valid or not
color[vertex] = col
if mColoring(colors, color, vertex + 1):
return True # go for additional vertices
color[vertex] = 0
return False # when no colors can be assigned
colors = 3 # Number of colors
color = [0] * V # make color matrix for each vertex
if not mColoring(
colors, color,
0): # initially set to 0 and for Vertex 0 check graph coloring
print("Solution does not exist.")
else:
print("Assigned Colors are:")
for i in range(V):
print(color[i], end=" ")
Output
Assigned Colors are: 1 2 3 1
”;