193 - Graph Coloring

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
ricky_bd
New poster
Posts: 3
Joined: Fri May 31, 2002 6:38 am

problem no 193

Post by ricky_bd »

what is the output of the following input
1
3 2
1 2
1 3

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra »

Hi!

For this test case the answer is :

2
2 3

(these nodes can be colored black because they are not directly connected)

Good Luck :wink:

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

193 something is strange

Post by rascle »

My algorithem is ...

Form the minimum degree node to the maxmum degree node,
if its all neighbors are not black,it is going to be colored.

Is it wrong ...??...

I can got correct results in many cases,but I got WA,WA,and WA...

visser
New poster
Posts: 8
Joined: Mon Jun 10, 2002 11:13 am
Location: Netherlands

Post by visser »

Nice heuristic, but nothing more than that...
Can you PROOF your algorithm is correct?

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

Post by rascle »

Sorry,I can't proof.....

This method broke into my heart occasionally.

I just don't know why it's wrong...^^....

Ex.

1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

Step 1. Construct all neighbors for each node

node neighbors degree can_be_color
1 2 3 2 true
2 1 4 5 3 true
3 1 4 6 3 true
4 2 3 6 3 true
5 2 6 2 true
6 3 4 5 3 true

Step 2. Start from the node which has lowest degree.

The lowest degree in this case is "2"

So,we search from node 1 to node 6 to find the node which can be
colored and has degree "2"....we get node "1" , so all neighbors of
node 1 can not be colored...


node neighbors degree can_be_color
1 2 3 2 "colored"
2 1 4 5 3 "false forever"
3 1 4 6 3 "false forever"
4 2 3 6 3 true
5 2 6 2 true
6 3 4 5 3 true

Then we get node 5 which can be colored and has degree "2",so all
neighbors of node 5 can not be colored....

node neighbors degree can_be_color
1 2 3 2 "colored 1 "
2 1 4 5 3 "false forever"
3 1 4 6 3 "false forever"
4 2 3 6 3 true
5 2 6 2 "colored 2 "
6 3 4 5 3 "false forever"

Step 3. Now we have finished all node having degree 2,so we go to
degree 3..
We find node 4 can be colored and has degree "3",so we select it and
find that all node have been considered..............

node neighbors degree can_be_color
1 2 3 2 "colored 1 "
2 1 4 5 3 "false forever"
3 1 4 6 3 "false forever"
4 2 3 6 3 "colored 3 "
5 2 6 2 "colored 2 "
6 3 4 5 3 "false forever"


So the answer is

3
1 4 5

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

Post by rascle »

Sorry,I can't proof.....

This method broke into my heart occasionally.

I just don't know why it's wrong...^^....

Ex.

1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

Step 1. Construct all neighbors for each node

node neighbors degree can_be_color
1 2 3 2 true
2 1 4 5 3 true
3 1 4 6 3 true
4 2 3 6 3 true
5 2 6 2 true
6 3 4 5 3 true

Step 2. Start from the node which has lowest degree.

The lowest degree in this case is "2"

So,we search from node 1 to node 6 to find the node which can be
colored and has degree "2"....we get node "1" , so all neighbors of
node 1 can not be colored...


node neighbors degree can_be_color
1 2 3 2 "colored"
2 1 4 5 3 "false forever"
3 1 4 6 3 "false forever"
4 2 3 6 3 true
5 2 6 2 true
6 3 4 5 3 true

Then we get node 5 which can be colored and has degree "2",so all
neighbors of node 5 can not be colored....

node neighbors degree can_be_color
1 2 3 2 "colored 1 "
2 1 4 5 3 "false forever"
3 1 4 6 3 "false forever"
4 2 3 6 3 true
5 2 6 2 "colored 2 "
6 3 4 5 3 "false forever"

Step 3. Now we have finished all node having degree 2,so we go to
degree 3..
We find node 4 can be colored and has degree "3",so we select it and
find that all node have been considered..............

node neighbors degree can_be_color
1 2 3 2 "colored 1 "
2 1 4 5 3 "false forever"
3 1 4 6 3 "false forever"
4 2 3 6 3 "colored 3 "
5 2 6 2 "colored 2 "
6 3 4 5 3 "false forever"


So the answer is

3
1 4 5

sayeed
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm

193 --

Post by sayeed »

/*@BEGIN_OF_SOURCE_CODE*/
#include<stdio.h>
#include<stdlib.h>

#define BLACK 2
#define WHITE 1

int vertex[102][102];
int flag[102],x[102],max,vertx;

void Coloring(int i,int count)
{
int j;
if(i==vertx){
if(max<count){
max =count;
for(j=0;j<vertx;j++)
if(flag[j]==BLACK) x[j] =1;
else x[j] = 0;
}
return;
}

for(j=0;j<vertx;j++)
if(vertex[j] == 1 && flag[j] == BLACK) break;

if(j==vertx){
flag =BLACK;
Coloring(i+1,count+1);
flag = 0;
}
else{
flag = WHITE;
Coloring(i+1,count);
flag = 0;


}

}
int main()

{
int edge,n,i,j,a,b,count;

scanf("%d",&n);

while(n-->0){
scanf("%d%d",&vertx,&edge);
max = 0;
for(i=0;i<vertx;i++) {
flag = 0,x = 0;
for(j = 0;j<vertx;j++)
vertex[j] = 0;
}
for(i=0;i<edge;i++){
scanf("%d%d",&a,&b);
vertex[a-1][b-1]=vertex[b-1][a-1]=1;

}

for(i =0 ;i<vertx;i++)
Coloring(i,0);



printf("%d\n",max);
for(i=0;i<vertx;i++)
if(x == 1) printf("%d ",i+1);
printf("\n");
}



return 0;
}

/*@END_OF_SOURCE_CODE*/

*******
Is the algorithm right?
Can anyone help me?

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

193 - Graph Coloring

Post by Christian Schuster »

Hello,

I tried to solve 193 (and got AC in 0.01s), but I'm using some kind of probabilistic approach: I randomly select a node, remove it and its neighbours until there are no nodes left. I repeat this several times (100 is enough) to get the maximum node count.

I know that this problem (Maximum Independent Set) is NP-complete, but is there another (maybe a bit more deterministic) solution?

mizocom2002
New poster
Posts: 3
Joined: Wed May 01, 2002 2:05 am

problem 193

Post by mizocom2002 »

i used the following heuristic to solve the problem:
find the node with minimum degree put it in the solution vector and delete it and all the nodes connected to it and so on till u finish all the nodes.
it generates the right answer for the test cases so can any body points out what is wrong with this algorithm and give me some difficult test cases, thanks.

Code: Select all

[cpp]

#include<iostream>
#include<fstream>
using namespace std;

int findmin();
void adjust(int x);

int a[101]={-1};
int b[101][101]={0};
int n;
int main()
{
	//ifstream ins;
	//ins.open("in.txt");
	//cin=ins;
	int m,k;
	int temp1,temp2;
	int f,t;
	int count;
	cin>>m;
	for(t=1;t<=m;t++)
	{
		count=0;
		//initialize a,b
		cin>>n>>k;
		for(f=1; f<=n;f++)
		{
			//a[f]=-1;
			for(int c=1;c<=n;c++)
				b[f][c]=0;
		}
		for(f=1;f<=k;f++)
		{
			cin>>temp1>>temp2;
			if(temp1 !=temp2)
			{
			b[temp1][temp2]=1;
			b[temp2][temp1]=1;
			}
		}
		for(f=1;f<=n;f++)
		{
			int y=findmin();
			if(y>n)
				break;
			a[f]=y;
			count++;
			for(int t=1;t<=n;t++)
			{
				if(b[y][t]==1)
					adjust(t);
			}
			adjust(y);

		}
		cout<<count<<endl;
		for(f=1;f<=count;f++)
		{if(f==count)
			cout<<a[f];
		else	
		cout<<a[f]<<" ";
		}
		cout<<endl;
		
	}
	return 0;


}


int findmin()
{
	int index=1000;
	int count;
	int mincount=1000;
	int i,j;
	for(i=1;i<=n;i++)
	{
		count=0;
		for(j=1;j<=n;j++)
		{
			if(b[i][j]==-1)
				break;
			if(b[i][j])
				count++;
		}
		if(j>n && count<mincount)
		{
			mincount=count;
			index=i;
		}
	}
	return index;
}
void adjust(int x)
{
	for(int i=1;i<=n;i++)
	{
		if(b[i][x]==1)
			b[i][x]=0;
		b[x][i]=-1;
	}
}

[/cpp]
mizo

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan »

so far as i know this algorithm will generate a maximal independent set, not necessarily the one that has maximum size.

maximal set: no other maximal set contains it
maximum set: the set whose cardinality is maximum

nebula12
New poster
Posts: 1
Joined: Wed Feb 12, 2003 10:46 pm

193 solution???

Post by nebula12 »

Hi,
Can anyone provide their solution to the graph coloring problem and the source code(c,c++ or java). I'm working on a problem where I need this solution.

Thanks.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

I didnt think a greedy algorithm would work... so is this problem NP-Complete. any kool algorithms? I was looking at Lawler's algorithm...

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

193 Graph Coloring

Post by Sajid »

My program got WA in 0.039 sec.

Can anyone tell me some inputs and outputs?
Sajid Online: www.sajidonline.com

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten »

not if you don't provide us with some details about your program, algorithm, or implementation

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

hmmm

Post by Sajid »

After taking the Graph, in a loop, I took the graph in another adjcency matrix and call the dfs, which call with the root (the root is 1 to n, end of the loop).

Code: Select all

for(i=1;i<=node;i++)
{
     temp=graph
     dfs(i)
}
The dfs visits every unvisited node, when it visits a node it colors white to its neighbours.

Finally, took the maximum number of Black nodes from the dfs(1->node)

is it, ok?
Sajid Online: www.sajidonline.com

Post Reply

Return to “Volume 1 (100-199)”