PROGRAM:
import java.io.*;
class gcoloring
{
int a[][]=new
int[10][10]; //adjacency matrix
int x[]=new
int[10]; //color array
int m, n; //m->no of colors n->no of vertices
void read()
{
DataInputStream
in=new DataInputStream(System.in);
try
{
System.out.println("Enter number of vertices in the
graph");
n=Integer.parseInt(in.readLine());
System.out.println("Enter 1 if there is an edge Otherwise 0");
for(int
i=1;i<=n;i++)
for(int
j=1;j<=n;j++)
{
System.out.println("between "+i+" and "+j);
a[i][j]=Integer.parseInt(in.readLine());
}
}
catch(Exception
e){}
System.out.println("Given adjacency matrix is ");
for(int
i=1;i<=n;i++)
{
for(int
j=1;j<=n;j++)
System.out.print(a[i][j]+"\t");
System.out.println();
}
for(int
i=1;i<=n;i++)
x[i]=0; //initialise color
array to 0
for(int
i=2;i<n;i++)
{
m=i; //no of colors start from 2 upto n
System.out.println("All possible combinations for m =
"+i+" are ");
mcoloring(1); //1 represents first vertex
}
}
void mcoloring(int
k)
{
do
{
nextvalue(k);
if(x[k]==0)
break;
if(k==n) //all
vertices have been assigned colors
{
for(int
i=1;i<=n;i++)
System.out.print(x[i]+"\t");
System.out.println();
}
else
mcoloring(k+1); //to assign color for next vertex
}while(true);
}
void nextvalue(int
k) //getting the next next color until a
{ // suitable color is found
int j;
do
{
x[k]=(x[k]+1)%(m+1);
if(x[k]==0) return;
for(j=1;j<=n;j++)
{
if((a[k][j]==1) &&
(x[k]==x[j]))
break;
}
if(j==n+1) return;
}while(true);
}
}
class Graphcoloring
{
public static void
main(String args[ ])throws IOException
{
gcoloring g=new
gcoloring();
g.read();
}
}
OUTPUT:
Enter the no. of vertices in the graph:5
Enter 1 if there is an edge otherwise 0
All possible combinations for m=1 are (1,0)
m=2
are (2,0)
m=3
are (3,0)
m=4
are (4,0)
m=5
are (5,0)
No comments:
Post a Comment