图染色问题研究--成品
图的染色问题研究
杨光------112208204124 摘要：本文主要介绍图染色问题的出现，历史进程以及一些有关图染色的基本性质和结论和它今后的应用与展望。
一、序言：
（1）问题的提出：图的染色问题起源于著名的“四色猜想”问题，这个
由伦敦的一名中学生在一百多年前提出的猜想是说，每个地图至多用4种色就可以“正常”着色了（即，可以使每两个有公共边界的国家都涂上不同的颜色）。我们把地图看成是由平面上的顶点和边所组成，每个国家对应于其中的一个平面区域，这样，每张地图就对应于一个平面图（即，可画在平面上使任两边都不在非顶点处交叉的图），而每个国家对应对应于平面图中的一个面。在图论中四色猜想是说：每个平面图的面至多用4种色就可以“正常”着色了。[1]
（2）研究与发展： “四色猜想”提出后，许多数学家着手研究“四色
猜想”，力图给出证明。时隔二十七年后，1897年肯普给出了“四色猜想”的第一个证明，又过了十一年，1890年希伍德发现肯普的证明是错误的。但他指出，肯普德证明方法虽然不能证明地图染色用四种颜色足够，却可以证明用五种颜色就够了。[2]然而，这个困扰了无数天才数学家和众多业余爱好者达一个多世纪的猜想，终于在1976年由Appel和Haken用大型计算机证实了。当时需要用手工输入1400个图形到计算机里，在用巨型程序去计算。因此，从1976年以后，就把“四色猜想”改称为“四色定理”了。该证明至今未能得到彻底的检验。近来Robertson，Sanders，Seymour和Thomas提出了一个改进，“只要”633个图形就够了，且简化了证明方法。但是，无论如何，由于至今未能得到理论上的证明，人们仍然无法一窥“四色猜想”得以成立的内在机制，使证明该猜想的努力难以停息。[3]
二、[4]性质：
（1）边着色问题：
a.基本定理：
定义1:对图G的边进行着色,且相邻的边没有相同的颜色,称为图G 的一个边着色.
定义2:使图G的n边着色最小的n,称为图n的边色数,记作x'(G)。
定义3（Vizing定理）:任意(简单,无向)图G的边着色数(edge chromatic number) 有△≤x≤△+1。
定义3：由Vizing定理可知x'（G）=△或x'（G）=△+1。若x'（G）=△，称图G为第一类，记作 ，否则x'（G）=△+1，称图G为第二类 记作。
b.基本结论：
引理1 (Vizing邻接引理)：设G为△临界图,且uv E（G），d（v）= k 则有(1) 若k<△, u 至少相邻于G的△-k+1个度数为△的顶点;
(2) 若k =△，u至少相邻于G的两个度数为△的顶点.
引理2：若G为△临界图（△≥3），则。
定理3：对实数α（0≤α≤3），满足△（G）≥3α-1和
的图G是第一类的。
定理4：设G为一连通的平面图,如果:G的任何两个长为3的面都不相邻(即不共边)，且只含有长为3，k,k+1, …的面(k≥4) ,则有
。
定理5：设G为一连通的平面图,如果G的任何两个长度为3的面都不关联于同一个顶点,且只有长为3，k,k+1, …的面（k≥4)，则有
。
[5] （2）列表着色问题：
a.基本定理：
令G为一个图，f是从G（V）到N的函数。图G的f—列表L是指对每一个顶点v满足)v)
(L=f(v)。如果存在一个f—列表L，使得G具有一个唯一列表染色，则称图G是唯一f—列表可染的，或UFLC的。
定义1：给图G的每个顶点x一个列表L(x),称G是L可染的 是指对每个顶点x∈V(G) 都可从其对应列表L(x)中找到一种染色c x）∈L(x)，使得c是G的正常染色。
定义2：一个图G的k-列表是指G每个顶点的列表长度都为k。如果对任意的k-列表图G都有一个列表染色,则称G为k-可选的(k-choosable)。使得G为k-可选的的最小无称为列表色数(list chromatic number)或选择数(choosability)记为x i(G)或ch(G)。
定义3：假设对图G的任意一个顶点v，存在v的一个长为k的颜色列表L(v)使得图G存在唯一L-染色，那么我们称图G是唯一k-列表可染色图 具有简称为UkLC(uniquely-list colorable)图或者说G是UkLC的。
定义4：如果一个图不是UkLC的，我们就说G具有M k）性质。使得G 具有M k）性质的最小k称为G的m数，记为M G）。
定义5：令G为一个图，f为一个从V(G)到N的函数。图G的f-列表L 是指对每一个顶点v满足L V）=f v）。如果存在一个f-列表L，使得G具有一个唯一列表染色，则称图G是唯一f-列表可染的或UfLC的。
定义6：给图G的每条边e一个列表L e），称G是L边可染的，是指对每边e∈E(G)，都可从其对应列表L e）中找到一种染色c e）∈L e），使得c 是G的正常边染色。
定义7：如果对任意的k-列表图G都有一个边列表染色，则称G为k-边可选的(k-edge-choosable)。使得G为k-边可选的的最小k称为边列表色数(list edge chromatic number 或边选择数(edge choosability) 记为x1∈G。
定义8：给图G的每条边、每个顶点x一个列表L(x)，称G是L全可染的，是指对每条边、每个顶点x∈E G）或x∈V(G)，都可从其对应列表L(x)中找到一种染色c e）∈L e），使得c是G的正常全染色。
定义9：如果对任意的k-列表图G都有一个全列表染色，则称G为k-全可选的(k-total-choosable)。使得G为k-全可选的的最小k称为全列表色数(list total chromatic number) 或全选择数(total choosability) 记为1
X（G）。
1
b.基本结论：
定理1：任意不含三角的唯一k+1可染图是唯一k-列表可染图.
定理2：连通图G具有M(2)性质当且仅当它的每个块或者是圈，或者是完全图，或者是完全二部图。
定理3:令d G)表示图G的平均度,也就是说d G)= 2 /e G n G).
则。
定理4:如果G 是唯一f 列表可染的,则
。
定理5：对任意的平面图m G)<4。 定理:6：如果一个平面图G 最多有7个三角面,则m(G)<3。
定理7：对任意图G ，有m G ）≤△G+1，若m G ）≥△G+1，则G 是正则图。
定理8: 如果一个图最多有3k 个顶点，则m G ）≤k+1。
定理9: 对任意的k ≥2，都存在一个UkLC 的完全三部图。
定理10:若3
435G)(-≤X V ，则)((G )G X x =。 定理11：
定理12: 令G 是一完全k 部图，其中，有一部为m 个顶点，有s 部都是单点集,，k-s-1部为两点集。若m ≤2s+1，则G 是k 可选的。
定理13: (Mahdian 和Mahmoodian) 一个连通图G 是U2LC 图当且仅当它至少有一个块不是圈，不是完全图，也不是完全二部图 。
（3）点着色问题：
图的染色问题具有重要的实际意义和理论意义。图的染色基本问题就是确定各种染色法的色数。随着图论领域研究的不断深入,关于点染色的成果也不断深入。Burris 等研究了点可区别的正常染色之后,张忠辅等又对邻边强染色,邻点可区别染色,进行了讨论。随后提出了点可区别的正常染色和邻点可区别的正常全染色、并对圈、完全图、完全二部图、扇、轮、树和奇数阶完全图删去一边所得到的图的邻边可区别染色进行了讨论,确定了这些图的邻点可区别的全染色.
[6]
a.基本定理:
邻强边染色(邻点可区别染色):对图G 的k-边染色f(uv)∈E (G),有f(u )≠f(v),f(u)={f(uw)|E(uw)∈G},那么我们称f 为图G( V , E)的邻强边染色,记作k — ASEC,并称x G)=min(k|存在G 的一个k —ASEC)为图的邻强边色。 b.基本结论：
1）邻点可区别全色数：
定理1：对任意阶为n(n ≥2)的简单连通图G ,邻点可区别全色数X G ）存在,并且X G ）≥△G+1。
定理2： 若图G （V ，E ）有两个相邻的最大度点,则有 X(G)≥△G+2。
2）单圈图邻强边染色：
定理1：设G 是p (p ≥3) 阶的单圈图, C 为G 中唯一的圈，C 的长为r 。若△G=2，则
。 3）完全4-部图的邻强边染
定理1：设m >n> p> q ≥1, 则mnpq x = m+n+p
定理2：设n ≥2,则 x K 111n ）= n+3.
定理3：设m >n>2, 则x K mn 11 ）= m+n+2.
定理4：若n ≥p+2且p ≥2，则 x K
p nnn ）= 3n. 定理5： 若n ≥p+1且p>1,，则x K nnpp )= 2n+p+1. 定理6： 若n ≥p+2且2p, 则 x
K nppp )= n+2p+1. 定理7: 若n ≥2,则x
K 1-nnnn )= 3n. 定理8: 若n ≥3,则x
K 1-nnnn ）= 3n-1。 4）联图（S S n ∨n ）的邻强边染色
定理1：对:m>n>1，x
S S ∨n =m+n+1。
定理2：对m>n>1,有
三、应用与意义：
研究图染色问题有什么应用价值及理论意义呢？若仅就地图染色而言，用四种色或更多一些颜色并无多大实用价值。然而，若将地图中的几个区域视为几种化学品，凡两个邻接的区域所代表的两种化学品有某种关系，例如该两种化学品若放在一起容易发生爆炸或引起变质等。现欲建造仓库来存放几种化学品，显然建造几个仓库分别存放这几种化学品是万无一失的。但建库费用大，怎样才能使建库数量最少，又能使这几种化学品的存放万无一失呢？显然，两两均无任何危险关系的几种化学品可存放于同一仓库中，即只要建造一个仓库就够了。可见，这一建库问题就转化为图点染色问题了，所以研究图染色问题是具有实用价值的。但是如此得到的图，一般并非平面图或可平面图，则可由研究非平
面图的点染色问题求得解决。
至于图边染色，在电网络、时间表问题、拉丁方构造等方面都有很好的应用实例，这里不一一列举了。
虽然图染色问题已经取得了不少的理论研究及应用研究成果，但是染色问题的原本问题——“四色猜想”迄今尚未得到令人满意的结果，致使“四色定理”的证明成为悬而未决的一大世界数学难题。由于这一数学难题历时150多年尚未解决，就不能不使一些数学家们想到：很可能“四色定理”的证明必然伴随着一个全新的数学方法的诞生，以至形成一个全新的数学分支。若果真如此，研究“四色定理”的意义就远远超出其染色本身了，这将是数学家们对数学发展的一个重大贡献。[7]
参考文献
【1】孙惠泉图论及其应用科学出版社2010年8月页码2
【2】百度文库：图的染色问题
https://www.wendangku.net/doc/c59559607.html,/view/52b07b225901*********c71.html
【3】孙惠泉图论及其应用科学出版社2010年8月页码3
【4】多半是他人总结，参考而已，但是纯手工输入
【5】图的着色问题——PPT第36页
https://www.wendangku.net/doc/c59559607.html,/view/2e1a0e2acfc789eb172dc81e.html 【6】图的着色问题——PPT第8页
https://www.wendangku.net/doc/c59559607.html,/view/2e1a0e2acfc789eb172dc81e.html 【7】百度文库：有关图的染色问题的研究
https://www.wendangku.net/doc/c59559607.html,/view/39770c0b6c85ec3a87c2c548.html
回溯法论文-回溯法的分析与应用
沈阳理工大学算法实践与创新论文
摘要 对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。 回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的 K值。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。 在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。 关键词: 回溯法图的着色问题符号三角形问题图排列问 题
目录 第1章引言 (1) 第2章回溯法的背景 (2) 第3章图的着色问题 (4) 3.1 问题描述 (4) 3.2 四色猜想 (4) 3.3 算法设计 (5) 3.4 源代码 (6) 3.5 运行结果图 (10) 第4章符号三角形问题 (11) 4.1 问题描述 (11) 4.2 算法设计 (11) 4.3 源代码 (12) 4.4 运行结果图 (16) 第5章圆的排列问题 (17) 5.1 问题描述 (17) 5.2 问题分析 (17) 5.3 源代码 (18) 5.4 运行结果图 (22) 结论 (23) 参考文献 (24)
图着色
算法设计课程设计 题目图着色问题 姓名学号 专业年级 指导教师职称 2014年 12月 4日
图的m着色问题 1 摘要 (3) 2 图的着色问题 (4) 2.1 图的着色问题的来源 (4) 2.2 图的着色问题的描述 (4) 3算法的基本思想 (4) 3.1 求极小覆盖法----布尔代数法 (4) 3.2 穷举法－Welch Powell着色法 (4) 3.3 回溯法 (4) 3.4 贪心法 (4) 3.5 蚁群算法 (5) 4算法步骤 (5) 4.1 求极小覆盖法----布尔代数法 (4) 4.2 穷举法－Welch Powell着色法 (4) 4.3 回溯法 (4) 4.4 贪心法 (4) 4.5 蚁群法 (4) 5 理论分析（复杂度比较）、实验性能比较 (7) 5.1 复杂度分析 (4) 5.2 实验性能比较 (4) 6 心得体会 (8) 7参考文献 (8) 8 附录 (8)
摘要 图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有着广泛的应用背景. 本文首先讨论了人工智能的状态搜索方法在图着色中的具体应用，并用可视化方法展示了低维的着色空间和约束的具体意义。 关键词：图着色 c++代码 2、图的着色问题 2.1图的着色问题的来源 1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)在一家科研单位从事地图着色工作时，发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的颜色。” 用数学语言来表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这就是源于地图着色的四色猜想问题。这里所指的相邻区域，是指有一整段边界是公共边界。如果两个区域只相遇于一点或有限多点，就不叫相邻。因为用相同的颜色给它们着色不会引起混淆。 用四种颜色着色的世界地图： 采用四种颜色着色的美国地图： 2.2图的着色问题的描述 （一）图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。 （二）通常所说的着色问题是指下述两类问题：
最大度是5的可平面图的边染色
最大度是5的可平面图的边染色 倪伟平 (枣庄学院数学与信息科学系,山东枣庄 277160) 摘 要:对于最大度是Δ的可平面图G,如果χ′(G )=Δ,称G 为第一类图;如果χ′ (G )=Δ+1,称G 为第二类图.χ′ (G )表示G 的边染色数.1965年,V izing 举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用D ischarge 方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图. 关键词:平面图;边染色;最大度;圈 中图分类号:O157.5 文献标识码:A 文章编号:1000-2162(2010)03-0018-06 Edge color i n gs of pl anar graphs w ith max i m u m degree f i ve N IW ei 2p ing (Depart m ent of M athematics and I nfor mati on Science,Zaozhuang University,Zaozhuang 277160,China ) Abstract:Let G be a p lanar graph of maxi m u m degree Δ,G was said t o be class 1if χ′ (G )=Δand class 2if χ′(G )=Δ+1,where χ′ (G )denoted the chr omatic index of G .I n 1965,V izing p r oved that p lanar graphs of class 1and class 2were exist f or Δ=5.By app lying a discharging method,the author p r oved that every si m p le p lanar graph G with Δ=5was of class 1,if G had no chordal -4-cycles and chordal -5-cycles,or no chordal -4-cycles and chordal -6-cycles . Key words:p lanar graph;edge col oring;maxi m um degree;cycle 文中考虑的图都是简单、无向有限图.若图G 可以表示在平面上,并且任意两条边仅在其端点处才可能相交,则称G 是可平面图,图G 的这种平面上的表示法称为G 的一个平面嵌入,或称为平面图.分别 用V (G )、E (G )、F (G )、Δ(G )(简记为Δ)表示G 的顶点集合、边集合、面集合、最大度.用d (x )表示x 在 G 中的度数,x ∈V (G )∪F (G ).用d k (v )表示点v 的度数为k 的邻点的个数,d k +(v )表示点v 的度数不小于k 的邻点的个数.度数为k 的点(或面)称为k -点(或k -面),度数不小于k 的点(或面)称为k + - 点(或k +-面).若一个3-面f 关联3个度数分别为i,j ,k 的顶点,其中,i ≤j ≤k,则称f 为(i,j ,k )-面.设C 是G 中长度为k 的圈,如果xy ∈E (G )\E (C ),其中,x,y ∈V (C ),称xy 为C 的一条弦,C 为有弦的k -圈.若存在一个映射φ:E (G )→{1,2,…,k},对G 中任意两条相邻接的边e 1和e 2,有φ(e 1)≠φ(e 2), 则称G 是k -边可染色的,使得图G 具有k -边可染色的最小的正整数k 定义为G 的边色数,记作χ′ (G ).若图G 满足χ′(G )=Δ(G ),称G 为第一类图,若χ′ (G )=Δ(G )+1,称G 为第二类图.若图G 是连通的第二类图,并且去掉任意边e ∈G 后,G -e 是第一类图,则称G 是一个临界图.最大度为Δ的临界图简称 收稿日期:2009-10-24 基金项目:山东省教育厅科研计划基金资助项目(J08L I 66) 作者简介:倪伟平(1965—),女,山东枣庄人,枣庄学院副教授,硕士. 引文格式:倪伟平.最大度是5的可平面图的边染色[J ].安徽大学学报:自然科学版,2010,34(3):18-23. 2010年5月 第34卷第3期安徽大学学报(自然科学版)Journal of Anhui University (Natural Science Editi on )May 2010Vol .34No .3
算法设计与分析复习题目及答案(1)
分治法1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间） 分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).
色盲、色弱测试图大全
色盲、色弱测试图大全 红绿色盲者中的红色盲者只能找到紫色的线，而绿色盲者只能找到红色的线，但红绿色弱者、正常者则两线都找得到。 红绿色盲者中的红色盲者能读出６，而绿色盲者能读出２，但红绿色弱者及正常者则两个字都能读出来。
正常看应是一幅“牛”的图案，如看到的是一头“鹿”，就有可能是色盲或色弱。 正常者能读出６，红绿色盲者及红绿色弱者读成5，而全色弱者则全然读不出上述的两个字。 红绿色盲者及红绿色弱者大多能读成５，但全色弱者及正常者则大多都读不出来。 红绿色盲者及红绿色弱者容易找到，但正常者及全色弱者大多却找不到。 下列还有一些图片是测试是否是色盲人群：
色觉检查图组合一 1-11-2 1-31-4 1-51-6 色觉检查图组合二 2-12-2 2-32-4
2-52-6 色弱矫正 图象一图象二 色盲是指缺乏或完全没有辨别色彩的能力。通常说的色盲多是指红绿色盲。面对五色缤纷的世界，人们到底是如何感知它的呢？原来在人的视网膜上有一种感光细胞——锥细胞，它有红、绿、蓝3种感光色素。每一种感光色素主要对一种原色光产生兴奋，而对其余两种原色光产生程度不等的反应。如果某一种色素缺乏，则会产生对此种颜色的感觉障碍，表现为色盲或色弱（辨色力弱）。色盲又分许多不同类型，仅对一种原色缺乏辨别力者，称为单色盲，如红色盲，又称第一色盲，比较多见；绿色盲，称为第二色盲，比第一色盲少些；蓝色盲，即第三色盲，比较少见。如果对两种颜色缺乏辨别力者，称为全色盲，较为罕见。色盲多为先天性遗传所致，少数为视路传导系统障碍所致。一般是女性传递，男性表现。
理论上全色盲的人的眼里应该只有黑白的，但是事实并非如此，有趣的是红色盲的人照样能分辨出红色信号灯，同样绿色盲的人也能分辨出绿信号灯，这是为什么呢？这是因为单色盲的人对于三原色是能分辨的，但对于如橙色，淡黄等复合色就分不清了。 先天性色觉障碍通常称为色盲，它不能分辩自然光谱中的各种颜色或某种颜色。而对颜色的辨别能力差的则称色弱，它与色盲的界限一般不易严格区分，只不过轻重程度不同罢了。色盲又分为全色盲和部分色盲(红色盲、绿色盲、蓝黄色盲等)。色弱包括全色弱和部分色弱(红色弱、绿色弱、蓝黄色弱等)。 1．全色盲 属于完全性视锥细胞功能障碍，与夜盲(视杆细胞功能障碍)恰好相反，患者尤喜暗、畏光，表现为昼盲。七彩世界在其眼中是一片灰暗，如同观黑白电视一般，仅有明暗之分，而无颜色差别。而且所见红色发暗、蓝色光亮、此外还有视力差、弱视、中心性暗点、摆动性眼球震颤等症状。它是色觉障碍中最严重的一种，患者较少见。 2．红色盲 又称第一色盲。患者主要是不能分辨红色，对红色与深绿色、蓝色与紫红色以及紫色不能分辨。常把绿色视为黄色，紫色看成蓝色，将绿色和蓝色相混为白色。曾有一老成持重的中年男子买了件灰色羊毛衫，穿上后招来嘲笑，原来他是位红色盲患者，误红色为灰色。早年还有过报道，一红色盲患者当了火车司机，因看错了信号而造成火车相撞。 3．绿色盲 又称第二色盲，患者不能分辨淡绿色与深红色、紫色与青蓝色、紫红色与灰色，把绿色视为灰色或暗黑色。一美术训练班上有位画画得很好的小朋友，总是把太阳绘成绿色，树冠、草地绘成棕色，原来他是绿色盲患者。临床上把红色盲与绿色盲统称为红绿色盲，患者较常见。我们平常说的色盲一般就是指红绿色盲。 4．蓝黄色盲 又称第三色盲。患者蓝黄色混淆不清，对红、绿色可辨，较少见。 5．全色弱 又称红绿蓝黄色弱。其色觉障碍比全色盲程度要低，视力无任何异常，也无全色盲的其它并发症。在物体颜色深且鲜明时，则能够分辨；若颜色浅而不饱和时，则分辨困难。患者也少见。 6．部分色弱 有红色弱(第一色弱)、绿色弱(第二色弱)和蓝黄色弱(第三色弱)等，其中红绿色弱较多见，患者对红、绿色感受力差，照明不良时，其辨色能力近于红绿色盲；但物质色深、鲜明且照明度佳时，其辨色能力接近正常。 ①
回溯法实验(最大团问题)
算法分析与设计实验报告第七次附加实验
} } 测试结果 当输入图如下时： 当输入图如下时： 1 2 3 4 5 1 2 3 4 5
当输入图如下时： 1 2 3 4 5
附录： 完整代码（回溯法） //最大团问题回溯法求解 #include
cout<<"最大团：（"; for(int i=1;i 实验二用回溯法求解图的m着色问题 一、实验目的 1 2、使用回溯法编程求解图的m着色问题。 二、实验原理 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树搜索。否则，进入该子树，继续按深度优先的策略进行搜索。 回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可结束。 回溯法从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 三、问题描述 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。若一个图最少需要m种颜色才能使图中任何一条边连接的2个顶点着有不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。设计一个算法，找出用m种颜色对一个图进行着色的不同方案。 四、算法设计与分析 用邻接矩阵a来表示一个无向连通图G=(V,E)。用整数1,2,…,m来表示m种不同的颜色。x[i]表示顶点i所着的颜色来，则问题的解向量可以表示为n元组x[1:n]。问题的解空间可表示一棵高度为n+1的完全m叉树。解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。 在回溯算法Backtrack中，当i>n时，表示算法已搜索至一个叶结点，得到一个新的m着色方案，因此当前已找到的可m着色方案数sum增1。当i≤n时，当前扩展结点Z是解空间树中的一个内部结点。该结点有x[i]=1,2,…,m。对当前扩展结点Z的每一个儿子结点,由函数Ok检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。 五、实验结果 源程序： #include 色盲测试图(答案) 色盲症当中的大多数表现为红绿色色盲。小的时候，父母或老师就常指着红色对我们说，这是红色，然后又指着绿色对我们说，这是绿色，但是，父母或老师却很难明显红色和绿色是不是我们眼睛里所看到的，如果是红绿色盲的话，这两种颜色就会颠倒。所以说，别人看到的颜色可能并不是我们看到的颜色。下面的三幅图画分别是正常人和红绿色盲症的人所看到的区别所在。 色盲者看不出任何数字 第一幅图像中，正常人会在圆圈的小点点中看到一个数字“７”，而色盲看到则是并排在一起的另外两个影像。 色盲者看不出任何数字 在第二幅图象中，正常人会在图像中看到一个数字“２”，而色盲则什么也看不到，对于他们来说。图像中仍然是一堆堆的圆点。 每个数字由竖栏割隔开 第三幅图画是从0-19的数字，每个数字由带颜色的栏隔开，每个数字的背景都是不同的，那么色盲又会看到什么呢？在他们眼里，0-5这一段是统一的，中间没有任何栏隔开，10-15的情况也是一样。 左边为数字25，右边为数字29（色盲者看不出数字29） 左边为数字45（盲者看不出数字45），右边为数字56 左边为数字6，右边为数字8（色盲者看不出数字6和8） 上面是一组用来测试红绿色盲的图像。正确答案依次是25，29，45，56，6，8。 正确答案是数字“5”，色盲者看到的是数字“2” 正常人看到的是数字“5”，色盲看到的是数字“2”。 再来几个 红绿色盲者中的红色盲者只能找到紫色的线，而绿色盲者只能找到红色的线，但红绿色弱者、正常者则两线都找得到 红绿色盲者中的红色盲者能读出６，而绿色盲者能读出２，但红绿色弱者及正常者则两个字都能读出来。 正常看应是一幅“牛”的图案，如看到的是一头“鹿”，就有可能是色盲或色弱。 一、颜色特征 1 颜色空间 1.1 RGB 颜色空间 是一种根据人眼对不同波长的红、绿、蓝光做出锥状体细胞的敏感度描述的基础彩色模式,R、 G、B 分别为图像红、绿、蓝的亮度值,大小限定在 0～1 或者在 0～255。 1.2 HIS 颜色空间 是指颜色的色调、亮度和饱和度,H表示色调,描述颜色的属性,如黄、红、绿,用角度 0～360度来表示;S 是饱和度,即纯色程度的量度,反映彩色的浓淡,如深红、浅红,大小限定在 0～1;I 是亮度,反映可见光对人眼刺激的程度,它表征彩色各波长的总能量,大小限定在 0～1。 1.3 HSV 颜色模型 HSV 颜色模型依据人类对于色泽、明暗和色调的直观感觉来定义颜色, 其中H (Hue)代表色度, S (Saturat i on)代表色饱和度,V (V alue)代表亮度, 该颜色系统比RGB 系统更接近于人们的经验和对彩色的感知, 因而被广泛应用于计算机视觉领域。 已知RGB 颜色模型, 令M A X = max {R , G, B },M IN =m in{R , G,B }, 分别为RGB 颜色模型中R、 G、 B 三分量的最大和最小值, RGB 颜色模型到HSV 颜色模型的转换公式为: S =(M A X - M IN)/M A X H = 60*(G- B)/(M A X - M IN) R = M A X 120+ 60*(B – R)/(M A X - M IN) G= M A X 240+ 60*(R – G)/(M A X - M IN) B = M A X V = M A X 2 颜色特征提取算法 2.1 一般直方图法 颜色直方图是最基本的颜色特征表示方法,它反映的是图像中颜色的组成分布,即出现了哪些颜色以及各种颜色出现的概率。其函数表达式如下: H(k)= n k/N (k=0,1,…,L-1) (1) 其中,k 代表图像的特征取值,L 是特征可取值的个数,n k是图像中具有特征值为 k 的象素的个数,N 是图像象素的总数。由上式可见,颜色直方图所描述的是不同色彩在整幅图像中所占的比例,无法描述图像中的对象或物体,但是由于直方图相对于图像以观察轴为轴心的旋转以及幅度不大的平移和缩放等几何变换是不敏感的,而且对于图像质量的变化也不甚敏感,所以它特别适合描述那些难以进行自动分割的图像和不需要考虑物体空间位置的图像。 由于计算机本身固有的量化缺陷,这种直方图法忽略了颜色的相似性,人们对这种算法进行改进,产生了全局累加直方图法和局部累加直方图法。 2.2 全局累加直方图法 全局累加直方图是以颜色值作为横坐标,纵坐标为颜色累加出现的频数,因此图像的累加直方空间 H 定义为: 分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间） 分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法 ). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法 )之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树 ). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ） 算法设计与分析课程设计 题目：用回溯法分析着色问题 学院：理学院 专业：信息与计算科学 班级：09信科二班 姓名：蔡秀玉 学号: 200910010207 用回溯法分析着色问题 目录 1 回溯法 (3) 1.1回溯法的概述 (3) 1.2 回溯法的基本思想 (3) 1.3 回溯法的一般步骤 (3) 2 图的m着色问题 (3) 2.1图的着色问题的来源 (3) 2.2通常所说的着色问题 (3) 2.3图的着色问题描述 (3) 2.4回溯法求解图着色问题 (5) 2.5图的m可着色问题的回溯算法描述 (6) 2.5.1回溯算法 (6) 2.5.2 m着色回溯法递归 (8) 2.5.3 m着色回溯法迭代 (9) 2.5.4例题利用回溯法给图着色 (11) 2.6复杂度分析着色回溯法迭代 (12) §1 回溯法 1.1回溯法的概述 回溯法是一种系统地搜索问题解的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 1.2回溯法的基本思想 回溯法的基本思想是，在确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 1.3回溯法的一般步骤 用回溯法解题的一般步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 §2 图的m着色问题 2.1图的着色问题的来源 图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得 图的染色问题 应锡娜06990213@https://www.wendangku.net/doc/c59559607.html, （浙江师范大学初阳学院，浙江金华321004） 摘要：本文介绍了图染色问题的提出、应用及意义，主要对已取得的研究成果及当今的研究状况进行了阐述。 关键词：图；染色；色数 一、引言 图染色问题起源于著名的“四色猜想”[1]问题。早在一百多年前的1852年，英国Guthrie提出了用四种颜色就可对任意一张地图进行染色的猜想。即对世界地图或任何一个国家的行政区域地图，最多用四种颜色就可以对其染色，使得凡是相邻的国家或相邻的区域都着以不同的颜色。 二、研究与发展 “四色猜想”提出后，一些数学家着手研究这个猜想，力图给出证明。时隔二十七年后，1879年Kempe给出了“四色猜想”的第一个证明，又过了十一年，1980年Hewood发现Kempe的证明是错误的。但他指出，Kempe的证明方法虽然不能证明“四色猜想”，却可以证明用五种颜色就够了。此后，“四色猜想”一直成为数学家们感兴趣而未能解决的世界数学难题。直到1976年6月美国数学家伊利诺斯大学教授Appel与Haken宣布：他们用计算机证明了“四色猜想”是正确的。因此，从1976年以后，就把“四色猜想”改称为“四色定理”了。[2] 值得指出的是，Appel与Haken的证明，计算机运行了1200个小时。诚然用计算机证明数学难题实在是一个伟大的尝试或创举，但是，世界数学家们仍期待着用常规的数学方法证明“四色定理”。目前仍有许多数学家在潜心研究，寻求常规的证明方法。 地图的特点在于，多个区域位于同一平面上，每个区域可以是毫无规则的各种形状，任意两个区域可以有公共边界，但不能有公共区域。于是人们开始研究所谓“平面图”。人们把地图中的每一个区域称为一个“面”，地图染色就是对“面”染色。进一步研究之后人们把地图中的每个区域的“面”视为一个点，若两个“面”相邻接，即地图中的两个区域有一段或几段公共边界，则在表示这两个区域的点之间连线，该连线可以是直线也可以是任意形状的曲线，并称之为边。如此，就可以把一张地图改画为一个平面上的图，人们把该图称为地图的对偶图。其特点是：所有的点及边均处在同一平面上，并且任意两条边除端点外可以不交叉，人们称这样的图为平面图。例如图1的对偶图如图2所示。 第8章回溯法 (1) 8.1概述 (1) 8.1.1 问题的解空间树 (1) 8.1.2 回溯法的设计思想 (2) 8.1.3 回溯法的时间性能 (3) 8.1.4 一个简单的例子——素数环问题 (4) 8.2图问题中的回溯法 (5) 8.2.1 图着色问题 (5) 8.2.2 哈密顿回路问题 (8) 8.3组合问题中的回溯法 (10) 8.3.1 八皇后问题 (10) 8.3.2 批处理作业调度问题 (13) 习题8 (16) 第8章回溯法 教学重点回溯法的设计思想；各种经典问题的回溯思想教学难点批处理作业调度问题的回溯算法 教学内容 和 教学目标 知识点 教学要求 了解理解掌握熟练掌握问题的解空间树√ 回溯法的设计思想√ 回溯法的时间性能√ 图着色问题√ 哈密顿回路问题√ 八皇后问题√ 批处理作业调度问题√ 8.1 概述 回溯法（back track method）在包含问题的所有可能解的解空间树中，从根结点出发，按照深度优先的策略进行搜索，对于解空间树的某个结点，如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该结点为根结点的子树进行剪枝。回溯法常常可以避免搜索所有的可能解，所以，适用于求解组合数较大的问题。 8.1.1 问题的解空间树 复杂问题常常有很多的可能解，这些可能解构成了问题的解空间（solution space），并且可能解的表示方式隐含了解空间及其大小。用回溯法求解一个具有n个输入的问题，一般情况下，将问题的可能解表示为满足某个约束条件的等长向量X=(x1, x2, …, x n)，其中分量x i（1≤i≤n）的取值范围是某个有限集合S i={a i,1, a i,2, …, a i,r i }，所有可能的解向量构成了问题的解空间。例如，对于有n个物品的0/1背包问题，其可能解由一个等长向量{x1, x2, …, x n}组成，其中x i=1（1≤i≤n）表示物品i装入背包，x i=0表示物品i没有装入背包，则解空间由长度为n的0/1向量组成。当n=3时，其解空间是： 颜色代码表：以下样色显示您可能觉得不够精确，这和电脑显示器有直接关系。您可查看html字体的颜 色代码，绝对正确，绝无重复。 QQ空间代码 欢迎您使用RGB颜色查询对照表 当你要给你的网页添加颜色时，有时，你能够直接使用该颜色的名称，但是大多情况下，你只能使用十六进制代码来使用这些字体颜色。（浏览器能够理解这些代码。） 为了方便你去使用这些代码，我们制作了这个列表，右边是颜色，左边是十六进制代码。 Hex Code Color #FFFFFF #FFFFCC #FFFF99 #FFFF66 #FFFF33 #FFFF00 #FFCCFF #FFCCCC #FFCC99 #FFCC66 #FFCC33 #FFCC00 #FF99FF #FF99CC #FF9999 #FF9966 #FF9933 #FF9900 #FF66FF #FF66CC #FF6699 #FF6666 #FF6633 #FF6600 #FF33FF #FF33CC #FF3399 #FF3366Hex Code Color #CCFFFF #CCFFCC #CCFF99 #CCFF66 #CCFF33 #CCFF00 #CCCCFF #CCCCCC #CCCC99 #CCCC66 #CCCC33 #CCCC00 #CC99FF #CC99CC #CC9999 #CC9966 #CC9933 #CC9900 #CC66FF #CC66CC #CC6699 #CC6666 #CC6633 #CC6600 #CC33FF #CC33CC #CC3399 #CC3366 Hex Code Color #99FFFF #99FFCC #99FF99 #99FF66 #99FF33 #99FF00 #99CCFF #99CCCC #99CC99 #99CC66 #99CC33 #99CC00 #9999FF #9999CC #999999 #999966 #999933 #999900 #9966FF #9966CC #996699 #996666 #996633 #996600 #9933FF #9933CC #993399 #993366 一、选择题 1、二分搜索算法是利用（A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（B）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．最长公共子序列算法利用的算法是（B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 13．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 14.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 图的m着色问题 问题描述： 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m 可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。 编程任务： 对于给定的无向连通图G和m种不同的颜色，编程计算图的所有不同的着色法。 数据输入： 由文件input.txt给出输入数据。第1行有3个正整数n，k和m，表示给定的图G 有n 个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G的一条边(u,v)。 结果输出: 程序运行结束时，将计算出的不同的着色方案数输出到文件output.txt中。 输入文件示例输出文件示例 input.txt output.txt 58448 12 13 14 23 24 25 34 45 /*图的m着色问题求解程序（回溯算法）*/ #include 图的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，则a[i][j]=1，否则a[i][j]=0。整数1，2，…，m用来表示m种不同颜色。顶点i所有颜色用x[i]表示，数组x[1：n]是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第I （1<=i<=n）层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。 在算法backtrack中，当i>n时，算法搜索至叶结点，得到新的m着色方案，当前找到的m着色方案数sum增1。 当I用回溯法求解图的m着色问题
色盲测试图
图像颜色特征提取原理
算法设计与分析复习题目及答案doc
用回溯法分析着色问题
图的染色问题
回溯法
图片颜色代码
太原理工大学软件学院算法设计与分析复习题目及答案
m着色问题
图的m着色问题回溯法