寻找无向图最小着色方案

题目

（1）图的m可着色判定问题

  给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。

（2）图的m可着色优化问题

  若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色

---

题解

二分法

#include "stdio.h"
#define dot 5
int count =0;//定义方案数量
int color[dot] = {0};//用0代表每个点当前未着色
int a[dot][dot]={0,1,1,1,0,      //a数组代表无向图的邻接矩阵
             1,0,1,1,1,
             1,1,0,1,0,
             1,1,1,0,1,
             0,1,0,1,0};
int OK(int t){
    for (int j =0; j<dot; j++) {
        if (a[t][j]==1) {//判断第t个顶点与其他顶点是否相连，如果相连并且颜色一样返回0，否则就返回1.
            if (color[t]==color[j]) {
                return 0;
            }
        }
    }
    return 1;
}

int Traceback(int t,int sort){
    int Oldvalue = 0;
    if (t ==dot) {
        count++;
        if (count ==1) {
            return 1; 
        }
        return 0;
    }
    Oldvalue = color[t];
    for (int j =1; j<=sort; j++) {
        color[t] = j;
        if (OK(t)) {
            if(Traceback(t+1,sort))
            	return 1;
        }
    }
    color[t] = Oldvalue;
    return 0;

}
int main(void){
	
	int left=0,right=dot;
	int mid=(left+right)/2;
	
	while(left<right){
		printf("%d %d\n",left,right);
		if(Traceback(0, mid)==1){
			right=mid;
		}else{
			left=mid+1;
		}
		mid=(left+right)/2;
	}
	
	printf("m:%d",right);
	
	
    return 0;
}

贪心法

#include <iostream>
#include <set>

using namespace std;
 
#define dot 5
int count =0;//定义方案数量
int color[dot] = {0};//用0代表每个点当前未着色
int a[dot][dot]={0,1,1,1,0,      //a数组代表无向图的邻接矩阵
             1,0,1,1,1,
             1,1,0,1,0,
             1,1,1,0,1,
             0,1,0,1,0};

int getDu(int n){
	int res=0;
	for(int i=0;i<dot;i++){
		res+=a[i][n];
	}
	return res;
}

int main(){
	
	set<int> uncolor;
	for(int i=0;i<dot;i++)
		uncolor.insert(i);
	int m=0;
	
	while(uncolor.size()){
		m++;
		cout<<"---------"<<m<<"-----------"<<endl;
		set<int> cancolor=uncolor;
		uncolor.clear();
		while(cancolor.size()){
			int mini=*cancolor.begin();
			int mind=getDu(mini);
			
			for(auto i=cancolor.begin();i!=cancolor.end();i++){
				int t=getDu(*i);
				if(t<mind){
					mini=*i;
					mind=t;
				}
			}
			
			for(int i=0;i<dot;i++){
				if(a[i][mini]){
					uncolor.insert(i);
					cancolor.erase(i);
				}
				a[i][mini]=0;
				a[mini][i]=0;
			}
			color[mini]=m;
			cout<<mini<<endl; 
			cancolor.erase(mini);
		}
	}
	cout<<endl;
	cout<<"m:"<<m<<endl;
	
	return 0;
}