图的M着色算法演示.ppt

《图的M着色算法演示.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的m着色问题讲课:吴双燕PPT制作:谭晓雅目录问题产生的背景问题描述程序运行及结果四一二三算法设计与分析图的着色问题是由地图的着色问题引申而来的，用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。一、产生背景二、问题描述给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。如果有则称这个图是m可着色，否则称这个图不是m可着色。若一个图最少需要k种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数k为该图的色数。三、算法设计输入：颜色种类m输出：如果这个图不是m可着色，给出

2、否定回答；如果这个图是m可着色的，找出所有不同的着色法。思考？如何将给定的无向图存储在计算机中？1423可以用一下邻接矩阵来表示1111011111111101111101011邻接矩阵中通常用二维数组来存放边之间的关系，用一维数组来存放顶点的信息。所以在接下来的求解问题中我们将用到二维数组a来存放两边是否相邻，用一维数组x来存放每个顶点的颜色;x[i]=j表示第i个节点图第j中颜色。5我们可以把问题简化为3个点来分析，现给定如下图，怎样求解呢？123该图的色数是多少？怎样用解空间树来表示呢？由图可知，对于每一个顶点可选的颜色可以有3种不同的选择，所以每一个节点有3个儿子节点，有4层

3、。判断条件是什么？新加入来得节点t取某一种颜色i时，依次和上层的每一个节点j(jN），即可输出一种方案for(i=1;i<=m;i

4、++){if(OK(t,i)){x[t]=i;Backtrace(t+1,m);}}if(t>N){sum++;printf("第%d种方案：",sum);for(i=1;i<=N;i++)printf("%d",x[i]);}四、程序代码#include#include#defineN3//图中节点的个数inta[N+1][N+1]={0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,};//邻接矩阵intx[N+1];//记录颜色intsum=0;//保存可以着色的方案数intOK(intt,inti)//判断函数{intj

5、;for(j=1;jN)//算法搜索至叶子节点{sum++;printf("第%d种方案：",sum);for(i=1;i<=N;i++)printf("%d",x[i]);printf("");}else{for(i=1;i<=m;i++){if(OK(t,i)){x[t]=i;Backtrace(t+1,m);}}}}intmain(){intm;inti;printf("请输入颜色种类：");scanf("

6、%d",&m);for(i=1;i<=m;i++)//初始化x[i]=0;Backtrace(1,m);if(sum==0){printf("不是%d可着色的!",m);}return0;}运行结果当N=5时，色数又是多少呢？X[1]=1X[1]=4X[1]=2X[1]=3X[2]=1X[3]=1X[4]=1X[5]=1234234N=5时的子集树谢谢大家的观看！