随机图的点可区别V-全染色算法

张忠辅教授逝世三周年纪念会暨张忠辅学术思想研讨会举办单位：兰州交通大学数理学院（应用数学研究所）西北师范大学数学与统计学院时间：2013-09-28下午14时30分至19时30分地点：西北师范大学新校区，教学楼309教室一、张忠辅教授生平简介(摘自/view/3987233.htm)张忠辅（1937-2010），兰州交通大学数理与软件工程学院教授，应用数学研究所所长。

张忠辅1937年6月出生于河南长葛市，1962年毕业于兰州大学数力系，1962年至今在兰州交通大学从事教学和研究工作，教学生涯将近50年。

1987年破格晋升为教授，1991年起享受国务院特殊津贴，曾任中国数学会理事、中国运筹学学会常务理事、中国工业与应用数学理事、中国教育普及工作委员会主任、甘肃数学会副理事长、甘肃运筹学会理事长，1988年至1998年为甘肃省政协委员；1998年至2003年为甘肃省政协常委。

2003年退休后，一直被学校返聘，并被西北师范大学、西北民族大学、兰州城市学院聘为兼职教授。

张忠辅教授曾两次参加世界数学家大会，并作学术专题报告，曾被多所国际著名大学邀请去作演讲，主持参与了4项国家自然科学基金资助项目，发表学术论文400余篇。

据了解，张忠辅提出了数学界比较著名的“张王猜想”，这在图论数学领域不亚于“哥德巴赫猜想”。

多年以来，数学界都是外国人提出定义，中国人跟从研究。

但张教授改变了这种状况。

他在图染色领域提出的很多论题和猜想，成为许多国外机构研究的方向和课题，并且成为许多国际大学的博士生的研究论题。

也因为他带领的团队在数学领域的杰出贡献，兰州由此成为全国乃至世界著名的数学科学领域图染色基地。

7月16日中午，74岁的兰州交通大学数理软件工程学院张忠辅教授因胃癌与世长辞，他在弥留之际留下两个心愿：一是去世后将自己的器官捐献出来；二是拿出20万元设立专项奖学金。

承担的学术研究课题：1.图染色及其它不变量研究，国家自然科学基金项目，2000-2002（主持）2.图染色与邻强边染色的研究，中韩项目，2003-2005（主持）3.Ramsey数下界研究，广西省自然科学基金项目，2001-2002（第二完成人）4.图的邻强边染色和图的自同态么半群研究，甘肃省自然科学基金项目，2002-2003（主持）获得的学术研究表彰/奖励：1．《Ramsey数下界研究》2001年获广西省科技进步一等奖；2．《图论在化学中的应用》1999年获甘肃省科技进步三等奖；3．1995年获铁道部“优秀科技工作者”称号；4．1990年被铁道部授予“有突出贡献的中青年科技专家”，1992年享受国务院政府特殊津贴；5．曾任中国运筹学会教育与普及工作委员会主任，甘肃省运筹学会理事长；曾任中国数学会理事，中国运筹学会常务理事，中国工业与应用数学会理事，西北运筹学会联络组副组长，甘肃省数学会副理事长，甘肃省政协常委。

算法：染色法什么是染色法染色法是一种常用的算法，用于解决一类图论问题。

在这类问题中，我们需要对图的节点进行染色，使得相邻节点的颜色不同。

染色法可以应用于多个领域，例如地图着色、任务调度、图像分割等。

算法思路染色法的基本思路是通过迭代遍历图的节点，并为每个节点分配一个颜色。

在遍历过程中，需要检查相邻节点的颜色，确保它们不与当前节点的颜色相同。

具体步骤如下：1.初始化一个颜色集合，用于存储可用的颜色。

2.遍历图的所有节点。

3.对于每个节点，获取其相邻节点列表。

4.检查每个相邻节点已经被染过的颜色，并从可用颜色集合中删除这些颜色。

5.从剩余的可用颜色中选择一个最小的颜色，并将其分配给当前节点。

6.重复步骤3-5，直到所有节点都被染过为止。

算法示例让我们通过一个简单的示例来演示染色法。

假设有一个无向图如下所示：A/ \B---C\ /D我们的目标是为每个节点分配一个颜色，使得相邻节点的颜色不同。

按照染色法的步骤，我们可以按照以下方式进行染色：1.初始化一个包含4种颜色（红、绿、蓝、黄）的颜色集合。

2.从节点A开始，将其染成红色。

3.节点A的相邻节点是B和C。

检查它们已经被染过的颜色，并从可用颜色集合中删除这些颜色。

剩余可用颜色为绿、蓝和黄。

4.选择最小的颜色（绿），并将其分配给节点B。

5.继续处理节点B的相邻节点。

由于节点A已经被染成红色，所以可用颜色集合中删除红色。

剩余可用颜色为蓝和黄。

6.选择最小的颜色（蓝），并将其分配给节点C。

7.最后处理节点D。

由于它与节点B相邻，所以从可用颜色集合中删除蓝色。

剩余可用颜色为黄。

8.将剩余唯一的可用颜色（黄）分配给节点D。

我们得到了如下染色结果：A (红)/ \B (绿)---C (蓝)\ /D (黄)算法分析染色法的时间复杂度取决于图的规模和相邻节点的数量。

在最坏情况下，每个节点都需要遍历一次其相邻节点，并检查颜色。

时间复杂度为 O(V + E)，其中 V 是节点数，E 是边数。

图色数的一种求法杨雅琴【摘要】利用组合数学中图转化成树的思想,从图中一顶点出发,按照图的邻接矩阵中各顶点间边存在的情况,建立各级树,根据要着色的顶点与已着色顶点间边存在的情况,给所要着色的顶点着色.当所有顶点都已着色后,所用颜色个数就是图的色数.【期刊名称】《高师理科学刊》【年(卷),期】2018(038)004【总页数】3页(P1-3)【关键词】图;邻接矩阵;树;色数【作者】杨雅琴【作者单位】齐齐哈尔大学理学院,黑龙江齐齐哈尔 161006【正文语种】中文【中图分类】O157近年来，对于图着色的研究有许多[1-6]，但关于图色数的求法并不多，多数文献是研究图的邻点可区别全色数的上界和图的一般邻点可区别全染色问题．本文借助利用组合数学中图转化成树的思想，从图中一顶点出发，按照图的邻接矩阵中各顶点间边存在的情况，建立各级树，根据要着色的顶点与已着色顶点间边存在的情况，给所要着色的顶点着色，当所有顶点都已着色后计算所用颜色个数就是图的色数．定义[1]251 设是阶一般图，并令其顶点按某种顺序排列．是一个的矩阵，其第行第列元素等于连接顶点和的边的数目．于是，总有，而且等于顶点处的环的个数，这样的矩阵称为的邻接矩阵．算法已知图所包含点的集合和所有边的集合，以及用来给图中各点着色的种颜色构成的集合．Step1 根据图所包含点的集合和所有边的集合，得出图的邻接矩阵．Step2 设表示点集中已被着色的点构成的集合，表示已给点着色的颜色构成的集合，初始值．Step3 设从点集中点开始着色，给点着色，则．Step4 以点为树根，根据邻接矩阵中点所对应行中元素值为1所对应点的情况，建立二级树（见图1），将点记入中，即．Step5 逐个选取点，考察邻接矩阵中点所对应行中元素值为1所对应点的情况，如果点与中每一点都有边相连（邻接矩阵第行中与中所有点所在的列上的元素都为1），则给点着中新的颜色，并将颜色记入中，即；否则，检查点与中没有边相连的点（邻接矩阵中第行中与中这点所在的列上的元素为0），记为．若中和点着同色的点与点都没有边相连，则点与该点着同一颜色；否则，给点着中新的颜色，并将颜色记入中，即．Step6 在图1中分别以为树根，得到一些新的点，将点记入中，即，重复Step5，直到或为止．例1 求图2的色数．解已知图2的点集为和边集，颜色集{红、蓝、黄、白、黑}．（1）得到图2的邻接矩阵．（2）以点1为起始着色点，给点1着红色，，{红}，建立以点1为树根的二级树（见图3）．由于点3与中点1有边相连（邻接矩阵中第3行第1列元素为1），因此从中选取颜色给点3着色，点3着蓝色，，{红，蓝}；由于点4与中点1和点3有边相连（邻接矩阵中第4行第1列元素和第4行第3列元素均为1），因此从中选取颜色给点4着色，点4着黄色，，{红，蓝，黄}；由于点5与中点1、点3和点4有边相连，因此给点5着白色，，{红，蓝，黄，白}；（3）建立三级树（见图4a），由于点2与集合上点1无边相连（邻接矩阵中第2行第1列元素为0），给点2着与点1同色，即给点2着红色（见图4b）．此时，所以，图2的色数是4．有时不用写出图的邻接矩阵也可以求图的色数．例2 求图5的色数．解已知图5的点集为和边集，颜色集{红，黄，蓝，白，黑，紫，绿}．（1）以点为起始着色点，给点着红色，，{红}，建立以点为树根的二级树（见图６）．（2）由于点与中点有边相连，因此从中选取颜色给点着色，点着黄色，，{红，黄}；点与中点有无边相连，点着黄色，，{红，黄}．（3）建立三级树（见图7a），由于点与集合中点无边相连，因此给点着与点相同的色，即给点着红色（见图7b），，{红，黄}；同理，给点着红色，，{红，黄}；点虽与集合中点无边相连，但与点有边相连，又点虽与集合中点无边相连，但与点有边相连，因此给点着蓝色，，{红，黄，蓝}．（4）建立四级树（见图8a或图8b），因点与中点和点都无边相连，因此给点着黄色，，{红，黄，蓝}．所以，图5的色数是3．【相关文献】[1] Richard A，Brualdi．组合数学[M]．北京：机械工业出版社，2012：245-295[2] VanLint J H，Wilson R M．组合数学教程[M]．北京：国防工业出版社，2006：1-6[3] 柳柏濂．组合矩阵论[M]．2版．北京：科学出版社，2005：56[4] 晁福刚，张忠辅，强会英．图的邻点可区别全色数的一个上界[J]．纯粹数学与应用数学，2010（1）：91-95 [5] 严谦泰．关于图的一般邻点可区别全染色[J]．系统科学与数学，2010（1）：101-106[6] Alan Tucker．应用组合数学[M]．北京：人民邮电出版社，2009：1-19。

一类特殊图的顶点染色数张祥波【摘要】If there are common vertexes in all the maximum cliques of graph, and there are k common vertexes, then we call graph is the k class graph. Hereby, this paper gives a new method to study vertex coloring of graph. According to this method, this paper studies a class vertex coloring of special graphs, and gives vertex coloring number of some graphs.%如果图G含有的所有最大团存在公共顶点,且公共顶点的个数为k,就称此图为第k类图。

据此,本文给出了研究图的顶点染色的一种新方法,并以此研究了一类特殊图的顶点染色及一些图的顶点染色数。

【期刊名称】《安庆师范学院学报（自然科学版）》【年(卷),期】2015(000)003【总页数】4页(P11-13,30)【关键词】最大团;顶点染色数;第k类图;图的厚度【作者】张祥波【作者单位】临盘中学，山东临邑 251507【正文语种】中文【中图分类】O157.5给定一个无向简单图G(V,E)(以下简称图G)，使得任意相邻顶点染不同颜色，这种染色所需要的最小数目，叫做图G的顶点染色数，记为χ(G)。

图的顶点染色较为复杂，这是一个NPC问题。

关于这个方面的研究主要包括它的求解算法[1-5]和特殊图的顶点染色[6-11](尤以平面图的染色较多[12-18])两个方面。

本文则提出了第k类图的概念，对图的结构进行统一分类，给出了研究图的顶点染色的一种新方法。

按照这种方法，本文研究了|S|且|S|=p-3时，图G的顶点染色，并给出了其中4类图的顶点染色数。

几类图的2-距离和可区别染色几类图的2-距离和可区别染色简介：图论是研究顶点和边构成的图的结构和性质的数学学科。

其中，图的距离和染色是图论中的两个重要概念。

本文将讨论几类特殊的图的2-距离和可区别染色，并探讨它们的性质和应用。

一、路径图的2-距离和可区别染色路径图是由一系列不相交的边连接的顶点构成的图，顶点按顺序排列，边只能连接相邻的两个顶点。

对于路径图，我们可以定义2-距离为两个顶点之间的距离。

例如，路径图中相邻顶点的距离为1，隔一个顶点的距离为2，以此类推。

而在路径图的可区别染色中，相邻的两个顶点不能染成相同的颜色。

通过对路径图的研究，我们可以发现以下性质：1. 路径图的2-距离是唯一确定的，两个不同的顶点之间的2-距离不同。

2. 路径图的可区别染色需要至少n种颜色，其中n是顶点的个数。

3. 路径图是可完全染色的，即可以使用n种颜色将路径图的顶点染色，且相邻的两个顶点颜色不同。

二、环图的2-距离和可区别染色环图是由一系列相邻的顶点构成的图，首尾相连形成一个循环。

对于环图，我们同样可以定义2-距离为两个顶点之间的距离。

而在环图的可区别染色中，相邻的两个顶点不能染成相同的颜色。

与路径图不同的是，环图的性质有所差异：1. 环图的2-距离是多样的，同一个顶点到不同顶点的2-距离可相同。

2. 环图的可区别染色需要至少2种颜色，即使顶点个数增加，所需的颜色数目也不变。

3. 环图是可完全染色的，可以使用2种颜色将环图的顶点染色，其中相邻的两个顶点颜色不同。

三、完全图的2-距离和可区别染色完全图是每两个顶点之间都存在边的图。

对于完全图，我们同样可以定义2-距离为两个顶点之间的距离。

而在完全图的可区别染色中，相邻的两个顶点不能染成相同的颜色。

完全图的性质如下：1. 完全图的2-距离是唯一确定的，两个不同的顶点之间的2-距离不同。

2. 完全图的可区别染色需要至少n种颜色，其中n是顶点的个数。

3. 完全图是可完全染色的，可以使用n种颜色将完全图的顶点染色，其中相邻的两个顶点颜色不同。