Graph coloring is a technique to assign colors to the nodes in such a way that either none of the adjacent nodes share same color or none of the adjacent edges share same color.
In a graph if the adjacent vertices do not share same color, the problem is known as vertex coloring. Similarly, if adjacent edges of a graph do not share same color, the problem is known as edge coloring.
This concept is mainly used in the following applications:
- Job scheduling,
- Register allocation,
- Pattern matching,
- Timetable preparation,
- Seating arrangement etc.
In the Graph Coloring Problem, the goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color, while using the minimum number of colors possible. This problem can be formally defined as follows:
Given a graph G=(V,E)G=(V,E), where VV is a set of vertices and EE is a set of edges, the task is to assign a color to each vertex such that:
- No two adjacent vertices (connected by an edge) share the same color.
- Minimize the number of colors used for the entire graph.
The minimum number of colors needed to color a graph is called the chromatic number of the graph, denoted as χ(G).
Algorithm mColoring(k)
{
repeat
{ // Generate all legal assignment of x[k].
NextValue(k); // Assign to x[k] a legal color.
if (x[k]=0) then return ; // No new color possible.
if (k=n) // At most m colors have been used to color n vertices
write (x[1:n]);
else
mColoring (k+1);
} untill (false);
}
Algorithm NextValue(k) {
repeat {
x[k]: = (x[k]+1)mod (m+1); // Next highest color
if (x[k]=0) then return; //All colors have been used.
for j:=1 to n do
{ //check if this color is distant from adjacent colors.
if ((G[k,j]!=0) and (x[k]=x[j]))
//if (k,j ) is an edge and if adj.
//vertices have the same color.
then break;
}
if(j=n+1) then return; //New color found
}untill (false); // Try to find another color.
}
Source Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<stdlib.h>
void next_value(int **g, int *x, int m, int n, int k) {
int j;
while (1) {
x[k] = (x[k] + 1) % (m + 1);
if (x[k] == 0)
return;
for (j = 1; j <= n; j++) {
if (g[k][j] != 0 && (x[k] == x[j]))
break;
}
if (j == n + 1)
return;
}
}
void coloring(int **g, int *x, int m, int n, int k) {
int i;
do {
next_value(g, x, m, n, k);
if (x[k] == 0)
return;
if (k == n) {
for (i = 1; i <= n; i++)
printf("vertex %d = color No. %d\t", i, x[i]);
printf("\n");
} else
coloring(g, x, m, n, k + 1);
} while (k < n + 1);
}
int main() {
int e, k, l;
int *x, **g, n, i, j, m;
printf("Enter no. of vertices : ");
scanf("%d", &n);
printf("Enter no. of edges : ");
scanf("%d", &e);
x = (int *)malloc((n + 1) * sizeof(int));
g = (int **)malloc((n + 1) * sizeof(int *));
for(i = 0; i <= n; i++)
g[i] = (int *)malloc((n + 1) * sizeof(int));
m = n - 1;
printf("\nThe maximum possible colours that can be assigned are: %d\n", m);
for (i = 0; i <= n; i++)
for (j = 0; j <= n; j++)
g[i][j] = 0;
printf("Enter u and v of an edge\n");
for (i = 1; i <= e; i++) {
printf("\nfor egde %d\n", i);
scanf(" %d %d", &k, &l);
g[k][l] = 1;
g[l][k] = 1;
}
for (i = 0; i <= n; i++)
x[i] = 0;
printf("\nThe colouring possibilities are:\n");
Posts
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.