



全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图的m着色问题1 问题描述给定无向量图G顶点和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G图中每条边的两个顶点着不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色,则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色问题。2 算法设计一般连通图的可着色法问题并不仅限于平面图。给定图G=(V,E)和m种颜色,果这个图不是m可着色,给出否定回答,如果这个图是m的可着色的,找出所有不同的着色法。下面根据回朔法的递归描述框架backtrack设计图的m着色算法。用图的邻接矩阵a表示无向量连通图G=(V,E)。若(i,j)属于图G=( V,E)的边集E,则aij=1,否则aij=0。整数1,2,m用来表示m种不同颜色。顶点i所有颜色用xi表示,数组x1:n是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第I(1=in时,算法搜索至叶结点,得到新的m着色方案,当前找到的m着色方案数sum增1。当I n )/搜索解空间树至叶节点 sum+;for ( int i=1; i );System.out.println();else/搜索解空间树的内结点for ( int i=1; i = m; i+ )xt=i;/保存填充的颜色if ( ok(t) )backtrack(t+1);private boolean ok( int k )/检查颜色可用性for ( int j=1; j = n; j+ )if ( akj & (xj=xk) ) return false;else;return true; 4.比对程序5.算法效率图的m可着色回朔法的计算时间上界可以通过解空间树中内结点个数估计. 图的可着色问 n-1题的解空间数中内结点个数是mi. 对于每一个内结点,在最坏情况下,用方法ok检查当前t=0扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn). 因此
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025湖北交投集团部分中层管理岗位竞聘上岗20人考前自测高频考点模拟试题及参考答案详解
- 2025广东深圳市市场监督管理局遴选第五批专业化职业化食品安全检查员(食品经营)模拟试卷附答案详解(模拟题)
- 2025国家电投所属国核电力院招聘1人笔试题库历年考点版附带答案详解
- 寺庙合作开发协议范本与寺庙项目合作协议范本8篇
- 2025北京通州投资发展有限公司公开招聘8人笔试题库历年考点版附带答案详解
- 2025中国东方航空食品投资有限公司校园招聘笔试题库历年考点版附带答案详解
- 福建省安全培训检查课件
- 禁毒安全知识培训班课件
- 2025法律规定合同范本制度
- 安置房协议赠与合同7篇
- 2025年甘肃省天水市供热有限公司招聘12人笔试历年参考题库附带答案详解
- 2025年一卷政治高考真题及答案
- 安静与智慧主题班会课件
- 云南民族大学附属高级中学2026届高三上学期联考(一)生物试卷(含答案)
- 2025至2030年中国包月视频点播行业市场竞争格局分析及投资方向研究报告
- 皮带机安全知识培训
- 零星维修工程施工组织设计方案方案
- 2025年汽车驾驶员(技师)考试试题及答案(含答案)
- 2025大连国际机场招聘25人笔试历年参考题库附带答案详解
- 2025年浙江铁塔招聘笔试备考题库(带答案详解)
- 2025年上海市(秋季)高考语文真题详解
评论
0/150
提交评论