图的着色

· · 个人记录

我觉得既然你无法预料究竟要考什么那就在考到之前把oiwiki上的所有东西搬到你的博客里，这就是我现在正在做的。

点着色

(无自环无向图)

定义：对无向图的每个节点染k种颜色，使得相邻节点颜色不同，则该无向图是k-可染色的。若该图是k-可染色的，但不是k-1-可染色的，则k为该图G的色数，记作\chi(G)。

以下用\Delta(G)表示G中所有节点的最大度数。对任意图，\chi(G)\le\Delta(G)+1。特别的，对于二分图，\chi(G)=2(显然)。

Brook定理

设连通图不是完全图也不是奇环，则\chi(G)\le\Delta(G)。

四色定理

任意平面图都是4-可染色的。

Welsh—Powell 算法

一个基于贪心求解图染色方案的算法，要求不限制最大着色数。过程大概是：

  1. 降序按所有点的度数把点排序。
  2. 将第一个点染成一个未被使用的颜色。
  3. 顺次遍历接下来的点，若当前点和所有与第一个点颜色相同的点不相邻，则将该点染成与第一个点相同的颜色。
  4. 返回第一步。 显然它是O(n^2)的。啥你问我有最大限制？建议爆搜。

这代码我还用上吗（口胡了一份应该没什么问题，有问题私我

bool cmp(int a,int b){
    return deg[a]>deg[b];
}
void getcolor(){
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(!col[i]){
            col[i]=++cnt;
            for(int j=i;j<=n;j++){
                bool jud=false;
                for(int k=head[j];k;k=edge[k].next){
                    if(col[edge[i].v]==cnt){
                        jud=true;break;
                    }
                }
                if(!jud)col[j]=cnt;
            }
        }
    }
}

边着色

类似点着色，对所有边染k种色，有公共节点的边不能染一种色，则该图是k-边可着色的。色数的定义同上。

Vizing 定理

设G是简单图，则\Delta(G)\le \chi(G)\le\Delta(G)+1。特别的，对于二分图，有\Delta(G)=\chi(G)。

对n阶完全图K_n，当n为奇数时\chi(K_n)=n，为偶数时\chi(K_n)=n-1。

这个有的时候有用。

给定一张二分图，左侧有n个点，编号为1到n，右侧有m个点，编号为1到m，有k条无向边。

给定c，你需要将每条边染色为[1,c]中的一种颜色。现在，对于第i个点，我们定义它的代价为与i点相连的边中，出现最多的颜色数减去出现最少的颜色数（如果一种颜色没有出现，我们认为它的出现次数为0）。

你需要构造一种方案，使得每个点的代价和最小,输出代价和方案。

首先根据Vizing定理可以知道这个最小的代价和是度数不为c倍数的点的个数。接下来考虑如何构造这个方案。

首先拆点，对于度数为c倍数的点，拆成若干度数为c的点。对于其余的点，拆成若干度数为c倍数的点和一个度数为除以c的余数的点。边连的点任意。

加入一条边(x,y)时，尝试找到编号最小的没有被两个节点使用的颜色col_x,col_y。若相等则直接染色。

否则假设col_x<col_y。从y开始找到颜色依次为col_x,col_y,col_x\cdots的一条增广路，把它们的颜色反色(即col_x变为col_y，col_y变为col_x)。然后将该边染为col_x。