周报

简单的图着色问题

2020年4月9日

一、问题简述

图着色问题（Graph Coloring Problem, GCP）　又称着色问题，是最著名的NP-完全问题之一。其数学定义为：给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。
在这里主要讨论两个基本问题（都是连通图）：
1、已知颜色数求总共有多少种染色方法

洛谷p2819图的m着色问题https://www.luogu.com.cn/problem/P2819

2、求将图染色至少需要多少种颜色

蓝桥杯分考场http://lx.lanqiao.cn/problem.page?gpid=T457

问题处理

第一题

邻接表存图，1~m表示每个颜色。

从小到大遍历每一个节点，依次判断某个颜色是否可行：和这个节点每一个邻接的点颜色不同。

预处理每个点都染成0（默认和已经染过色的点不同色），当搜索到n+1个点时说明找到了一个可行解。

回溯时将点染回0，这样即便在某个染色状态下，此点的所有染色方案都不可行，再往前回溯时，能继续往下搜索那个状态时的可行解。

时间复杂度：n个点m种颜色——O(m^n),判断当前染色状态下该点染色方案是否可行O(n)。总复杂度O(n*m^n).

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 10005
#define INF 0x3f3f3f3f
using namespace std;
vector<int>node[MAXN];
int n,k,m,ans;
int col[MAXN];
bool judge(int now,int colour){
    int len=node[now].size();
    for(int i=0;i<len;++i){
      if(col[node[now][i]]==colour)return false;
    }
    return true;
}
void dfs(int deep){
    if(deep==n+1){
        ans++;
        return;
    }
    for(int i=1;i<=m;++i){
        if(judge(deep,i)){
            col[deep]=i;
            dfs(deep+1);
            col[deep]=0;
        }
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    int a,b;
    cin>>n>>k>>m;
    while(k--){
        scanf("%d%d",&a,&b);
        node[a].push_back(b);
        node[b].push_back(a);
    }
    dfs(1);
    cout<<ans<<endl;
}

第二题

这里只讲暴力的方法（明明是只会暴力，咳咳……

题意转化为保证相邻点颜色不同至少需要多少种颜色。

n个节点n种颜色肯定可以，并且如果某个颜色数可行那么就可能存在颜色数更少的可行法案，于是在2~n间二分答案，判断该染色数是否有可行解。

如果照搬第一题的方法复杂度logn*（n*m^n），n是100的，m最坏也100，妥妥的t了，那么下面考虑优化。

很显然的优化就是只要找到一个可行解就拼命return，但是当m很大（准确的来说是稍微有点大）并且无解的情况下我们还是要遍历有可行方案点的所有可行方案。那怎么办？

其实很简单想了我大半天，只要回溯的时候不要把点染回0就可以了，为什么这样是对的？因为这样我们能保证从后往前每个点保持在它后一个点的最后可行状态下的最后可行状态，这样，就相当于从后往前搜，每个点保持在它前一个最后可行状态下的最后可行状态，也就是如果该染色数有解的话那这就是最后一个解，如果这个状态下不可行，那就是不可行了。(临表涕零，不知所言实话实说，这个优化是真●乱搞搞出来的，回头再想想好像的确是那么回事，仅供参考，但是代码非常好理解

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 10005
#define INF 0x3f3f3f3f
using namespace std;
vector<int>node[MAXN];
int col[MAXN];
int n,mid;
bool judge(int now,int colour){
    int len=node[now].size();
    for(int i=0;i<len;++i){
        if(col[node[now][i]]==colour)return false;
    }
    return true;
}
bool dfs(int deep){
    if(deep==n+1){
        return true;
    }
    for(int i=1;i<=mid;++i){   
        if(judge(deep,i)){
            col[deep]=i;
            if(dfs(deep+1))return true;
          //  col[deep]=0;
        }
    }
    return false;
}
int main(){
  //  freopen("input.txt","r",stdin);
    int m,k,a,b;
    cin>>n>>m;
    int l=2,r=n; 
    while(m--){
        scanf("%d%d",&a,&b);
        node[a].push_back(b);
        node[b].push_back(a);
    }
   while(l<=r){
       memset(col,0,sizeof(col));
       mid=(l+r)/2;
       if(dfs(1))r=mid-1;
       else l=mid+1;
    }
    cout<<r+1<<endl;
}

Views: 273

发表评论