图的色数

紫书P286:

经典问题,无向图 G ,每个节点染色,相邻的节点不同色,求最少多少颜色。

设 d(S) 表示把节点 S 染色,所需要的最少颜色。 则有 d(S) = d(S-S) + 1; S是可以染成一种颜色的,(即S没有u,v使得u,v相邻)。然后就是在S中枚举这个子集 S了。

#include <bits/stdc++.h>
using namespace std;

#define maxnode 1000
#define INF 0x3f3f3f3f

int n;  ///节点个数
int d[maxnode<<1]

int main()
{

    d[0] = 0;
    for(int S=1;S<(1<<n);S++) {
        d[S] = INF;
        for(int S0 = S; S0 ; S0 = (S0-1)&S) {
            if(no_edges_inside[S0])
                d[S] = min(d[S],d[S-S0]+1);
        }
    }

    return 0;
}
时间: 10-27

图的色数的相关文章

图m着色问题

1 问题描述: 给定无向图,m种不同的颜色.使每一种着色法使G中每条边的2个顶点不同颜色,若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,则成这个数m为该图的色数.求一个图的色数m的问题称为图的m可着色优化问题. 2 算法设计 用图的邻接矩阵a表示无向图连通图G=(V,E). 若存在相连的边,则a[i][j] = 1,否则 a[i][j]=0. 整数1,2,3...m用来表示为一棵高度为n+1的完全m叉树. 解空间树的第i层中每一结点都有m个儿子,每个儿子相应于x[i]的m个可

图论---图的m-点着色判定问题(深搜--迭代式)

转自 图的m着色问题 图的m-着色判定问题--给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色? 图的m-着色优化问题--若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色,则称这个数m为该图的色数.求一个图的最小色数m的问题称为m-着色优化问题. 算法描述(迭代算法) color[n]存储n个顶点的着色方案,可以选择的颜色为1到m t=1->n 对当前第t个顶点开始着色:(DFS) if: t>

算法导论-顺序统计

目录 1.问题的引出-求第i个顺序统计量 2.方法一:以期望线性时间做选择 3.方法二(改进):最坏情况线性时间的选择 4.完整测试代码(c++) 5.参考资料 内容 1.问题的引出-求第i个顺序统计量 什么是顺序统计量?及中位数概念 在一个由元素组成的集合里,第i个顺序统计量(order statistic)是该集合第i小的元素.例如,最小值是第1个顺序统计量(i=1),最大值是第n个顺序统计量(i=n).一个中位数(median)是它所在集合的“中点元素”.当n为奇数时,中位数是唯一的:当n

Kneser猜想与相关推广

本文本来是想放在Borsuk-Ulam定理的应用这篇文章当中.但是这个文章实在是太长,导致有喧宾夺主之嫌,从而独立出为一篇文章,仅供参考. (图1:Kneser叙述他的猜想原文手稿) 目录 1 Lyusternik-Shnirel'man定理与Greene定理 2 Kneser猜想与Greene的证明 3 Lovász的证明大意 4 Bárány的证明与Schrijver定理 5 Dol'nikov定理与超图上的Kneser猜想 6 Matou?ek的组合证明以及推广 7 拓扑组合的历史注记 8

JAVA IDE IntelliJ IDEA使用简介(一)—之界面元素

(注:简介基于IDEA的版本为:11.0,下载地址:http://www.jetbrains.com/idea/) 打开IDEA,(当第一次打开的时候出现的是一个欢迎页面,随便创建一个project来进入到IDEA的主界面),主界面显示如下: 主界面由6个主要区域组成(图中红色数字标注的) 1.菜单和工具栏 2.导航条:编辑文件时帮助定位和导航项目中的文件 3.状态栏:显示当前项目,IDEA本身的状态,还有别的一些状态相关的一些信息 4.编辑器 5.工具窗口:辅助类窗口.IDEA提供了各式各样的

poj1129 Channel Allocation(染色问题)

题目链接:poj1129 Channel Allocation 题意:要求相邻中继器必须使用不同的频道,求需要使用的频道的最少数目. 题解:就是求图的色数,这里采用求图的色数的近似有效算法——顺序着色算法(实质是一种贪心策略:在给任何一个顶点着色时,采用其邻接顶点中没有使用的,编号最小的颜色). 注:中继器网络是一个平面图,即图中不存在相交的边. 看讨论后发现这组数据,AC代码没过orz: 6 A:BEF B:AC C:BD D:CEF E:ADF F:ADE 正确答案应该是3 : A(1)B(

BZOJ 1006 神奇的国度(弦图的染色数)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1006 题意:给定一个弦图,求最小染色数.就是用最小数目的颜色进行染色使得任意两个相邻的节点颜色不同. 思路:(1)求出弦图的完美消除序列. (2)贪心染色.从后向前用可以用的编号最小的颜色染色.在这里因为最小染色等于最大团,我直接求的最大团.为什么最小染色等于最大团呢?最大团w(G) 是包含点数最多的团,最小染色x(G)是相邻点不同色的最小颜色个数.那么w(G)<=x(G),因为最大团

bzoj 1006 弦图染色

给定一个弦图,问最少染色数. 对于弦图的一个完美消去序列,从后往前染色,每次染可以染的最小编号的颜色,由完美消去序列的定义,序列任一后缀的点的导出子图中,由该后缀第一个元素及其邻接点导出的子图一定是完全图,所以,序列中某一元素染的颜色编号是该完全图的大小.所以最小染色数小于等于最大团的点数,而显然前者又大于等于后者,故弦图的最小染色数等于最大团的大小. 1 /************************************************************** 2 Prob

算法java实现--回溯法--图的m着色问题

(转自:http://blog.csdn.net/lican19911221/article/details/26264471) 图的m着色问题的Java实现(回溯法) 具体问题描述以及C/C++实现参见网址 http://blog.csdn.NET/lican19911221/article/details/26228345 /** * 着色问题 * @author Lican * */ public class Coloring { int n;//图的顶点数 int m;//可用颜色数 i