文档章节

回溯法---->图的着色问题

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 733
阅读 9
收藏 0

图的着色问题

1、问题描述

图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

图的m-着色优化问题——若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色,则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题

2、找一个图的所有m-着色方案

procedure MCOLORING( k )

∥这是图着色的一个递归回溯算法。图G 用它的布尔邻接矩阵GRAP H(1∶n , 1∶  n)表示∥

∥它计算并打印出符合以下要求的全部解, 把整数1 , 2 , ⋯  ,m 分配给图中∥

∥各个结点且使相邻近的结点的有不同的整数。k 是下一个要着色结点的下标∥

global integer m, n , X(1∶  n)   boolean GRAPH (1∶n  , 1∶n)

integer k

loop ∥产生对X( k)所有的合法赋值∥

call  NEXTVALUE( k) ∥将一种合法的颜色分配给X( k) ∥

if  X( k) = 0 then exit endif ∥没有可用的颜色了∥

if  k = n

then  print ( X) ∥至多用了m 种颜色分配给n 个结点∥

else  call MCOLORING( k + 1 ) ∥所有m-着色方案均在此反复递归调用中产生∥

endif

repeat

end MCOLORING

在最初调用callMCOLORING(1)之前, 应对图的邻接矩阵置初值并对数组X置0值。在确定了X(1)到X(k-1)的颜色之后,过程NEXTVALUE从这m种颜色中挑选一种符合要求的颜色, 并把它分配给X(k) , 若无可用的颜色, 则返回X(k) = 0。

3、获取下一种颜色

procedure NEXTVALUE( k)

∥进入此过程前X(1) , ⋯ , X( k - 1 )已分得了区域[ 1 , m] 中的整数且相邻近的结点有不同的

整数。本过程在区域[0 ,m] 中给X( k )确定一个值:如果还剩下一些颜色, 它们与结点k 邻

接的结点分配的颜色不同, 就将其中最高标值的颜色分配给结点k ;如果没剩下可用的颜

色, 则置X( k) 为0∥

global integer m, n , X(1∶n)  boolean GRAP H(1∶n , 1∶  n)

integer j , k

loop

X(k) ←(X(k) + 1 ) mod (m + 1) ∥试验下一个最高标值的颜色∥

if X( k ) = 0 then return endif ∥全部颜色用完∥

for j←1 to n do ∥检查此颜色是否与邻近结点的那些颜色不同∥

if GRAPH( k , j ) and ∥如果( k , j )是一条边∥

X(k) = X(j) ∥并且邻近的结点有相同的颜色∥

then exit endif

repeat

if j = n + 1 then return endif ∥找到一种新颜色∥

repeat ∥否则试着找另一种颜色∥

end NEXTVALUE

4、例子

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/16/5637087.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
算法设计策略----回溯法和分枝限界法

显示约束和解空间:规定每个分量xi取值的约束条件称为显式约束。对给定的一个问题,显示约束规定了所有可能的元组,他们组成问题的候选解集,被称为该问题实例的解空间。 隐式约束和判定函数...

Superheros
03/10
5
0
常用算法和复杂度总结

一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) 合并排序 MergeSort(A,p,r) O(nlog n) 选最大 FindMax O(n) 选最...

啊莱
2010/01/03
0
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
砝码分盐问题——从数学和计算机的角度分析(7)

本博客(http://blog.csdn.net/livelylittlefish)贴出作者(阿波)相关研究、学习内容所做的笔记,欢迎广大朋友指正! Content 0.问题 1.一些方法 2.从数学的角度分析 3.能否编程计算? 4....

晨曦之光
2012/03/09
58
0
算法的设计基本方法的理解

算法设计基本方法有什么好处? 了解常见的算法设计方法以及它们之间的区别,有利于构建算法思维的广度,有充分的理论知识。当然,如果算法思维的深度再好的话,将来你见识的算法越多,天下之...

qingliangdexiar
2017/05/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Go 使用channel控制并发

前言 channel一般用于协程之间的通信,channel也可以用于并发控制。比如主协程启动N个子协程,主协程等待所有子协程退出后再继续后续流程,这种场景下channel也可轻易实现。 场景示例 总结 ...

恋恋美食
22分钟前
1
0
Apache Flink 漫谈系列 - 持续查询(Continuous Queries)

摘要: 实际问题 我们知道在流计算场景中,数据是源源不断的流入的,数据流永远不会结束,那么计算就永远不会结束,如果计算永远不会结束的话,那么计算结果何时输出呢?本篇将介绍Apache Fl...

阿里云官方博客
26分钟前
3
0
斐波那契堆的理解,节点mark属性和势函数

斐波那契堆 看了好多博客,都是照搬算法导论的内容,没有自己的理解,比如为什么有mark属性,势函数的作用,以及为什么叫斐波那契堆,下面说说鄙人的理解。 势函数 势函数是根节点个数加上2...

杨喆
27分钟前
2
0
NIO源码详解

阻塞io和无阻塞io: 阻塞io是指jdk1.4之前版本面向流的io,服务端需要对每个请求建立一堆线程等待请求,而客户端发送请求后,先咨询服务端是否有线程相应,如果没有则会一直等待或者遭到拒 ...

沉稳2018
31分钟前
0
0
如何把已经提交的commit, 从一个分支放到另一个分支

在本地master提交了一个commit(8d85d4bca680a5dbcc3e5cfb3096d18cd510cc9f),如何提交的test_2分之上? git checkout test_2git cherry-pick 8d85d4bca680a5dbcc3e5cfb3096d18cd510cc9f......

stephen_wu
35分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部