计算机科学与工程学院实验报告

课程名称

算法设计与分析

班级

实验内容

实验1：图的着色问题

指导教师

姓名

重剑DS

学号

实验日期

2022.04.28

前言：

图着色问题（Graph Coloring Problem, GCP） 又称着色问题，是最著名的NP-完全问题之一。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。NP完全问题也叫做NPC问题。[2]

数学定义：给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。

对于任意简单无向图G，判断G的顶点可否3-着色是一个NP完全问题，哪怕G是平面图且每个顶点的度都不大于4。[1]

问题描述：

图的m着色问题.给定无向连通图G和m种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色.如果要求的每条边的两个顶点着不同颜色.给出所有可能的着色方案数量；如果不存在着这样的方案，则回答“No”.

    输入数据格式：

    第1行有3个正整数n，m和k，表示给定的图G有n个顶点和m条边，k种颜色。顶点编号为1，2，…，n。接下来的m行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。

【输入样例】

5 8 4

1 2

1 3

1 4

2 3

2 4

2 5

3 4

4 5

输出数据格式：

    程序运行结束时，将计算出的不同的着色方案数输出。

【输出样例】

48

IDE：Dev-C++ 5.4.0

编程语言：C++

调试的输入数据：

5 8 4

1 2

1 3

1 4

2 3

2 4

2 5

3 4

4 5

上机输入效果界面截图：

运行结果：

48

最终运行界面截图：

中间运行过程debug调试截图：

 由上图可以看到，找到了第一个可行的染色方案，并且方案被记录在了color数组里

算法流程图如下图所示：

算法的时间复杂度如下：

   图可着色问题的回溯算法的计算时间上界可以通过计算解空间树中内结点个数来估计。

题给的颜色总数为m，总节点数为n，那么图可着色问题的解空间树中内结点个数是mn（我是理解为树有n+1层，即深度为n，然后每层大概有m个分支(除了最后一层)）。

对于每个结点，在最坏情况下，用Check函数检查点的颜色是否满足条件大概需要付出的时间开销为O(n)。因此，回溯法总的时间耗费是O(n*mn)

算法空间复杂度分析如下：

    算法的空间复杂度主要来自用于存图的邻接矩阵。

其大小和问题所提供的图的节点数n有关，所以空间复杂度S(n)=O(n2)。

中间卡了一段时间，奇怪为什么用上面的输入样例得到的总的方案数总是0，后面发现是自己手误打错了代码（但是看起来运行没有什么问题，因为程序貌似没有崩溃之类的迹象）。 错误如下图所示：

[1] M.R.Garey,D.S.Johnson and L.Stockmeyer, Some simplified

NP-complete graph problems,Theoretical Computer Science(1976)

237-267.

[2] MR Garey，DS Johnson ．Computers and Intractability: A Guide to the Theory of NP-Completeness： W. H. Freeman，1979