随机图的邻点可区别VI-均匀全染色算法

发布时间：2018-02-11 20:19

  本文关键词： 随机图 正常均匀全染色 均匀全色数 邻点可区别VI-均匀全染色　出处：《计算机工程与应用》2017年15期 　论文类型：期刊论文

【摘要】：邻点可区别VI-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类(点或边)的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别VI-均匀全色数。提出了一种针对随机图的邻点可区别VI-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别VI-均匀全色数。
[Abstract]:Vertex differentiable VI- uniform total coloring means that any two adjacent edges in a graph assign different colors, and the maximum difference in the number of colors of any two color classes (points or edges) is 1, and the color sets of adjacent vertices are ensured to be different. The minimum number of colors used is called the vertex-differentiable vertex-uniform total chromatic number of graphs. An algorithm for vertex-distinguishing VI-uniform total coloring of random graphs is proposed. The algorithm designs three subobjective functions and a total objective function according to coloring conditions, and iterates to optimize according to the exchange rules until the coloring results meet the requirements of the total objective function. At the same time, the detailed implementation steps of the algorithm are given. A large number of tests and analyses have been carried out. The experimental results show that the proposed algorithm can efficiently obtain the minimum adjacent vertex-distinguishing VI-uniform total chromatic number of a graph with a given number of vertices.
【作者单位】： 兰州交通大学电子与信息工程学院;
【基金】：国家自然科学基金(No.11461038,No.61163037,No.61163010)
【分类号】：O157.5

【参考文献】

相关期刊论文 前9条

1 代素敏;胡腾云;尹波;李敬文;;随机图的均匀边染色算法[J];计算机应用研究;2016年06期

2 尹波;李敬文;代素敏;胡腾云;;随机图的正常均匀全染色算法[J];计算机应用;2015年08期

3 王继顺;李步军;;图的邻点可区别Ⅰ-均匀全染色[J];应用数学学报;2015年01期

4 马刚;马少仙;张忠辅;;一些联图的均匀全染色[J];应用数学学报;2010年04期

5 马刚;张忠辅;;若干倍图的邻点可区别均匀全染色[J];吉林大学学报(理学版);2009年06期

6 ;Equitable Total Coloring of F_n ∨ W_n[J];Acta Mathematicae Applicatae Sinica;2009年01期

7 严谦泰;冉红;;P_n~k的均匀全染色[J];大学数学;2007年03期

8 马刚;张忠辅;;关于联图W_m∨P_n的均匀全染色[J];西北民族大学学报(自然科学版);2006年01期

9 张忠辅,李敬文,田双亮,马少仙;圈的Mycielski图的均匀全染色[J];兰州铁道学院学报;2003年06期

【共引文献】

相关期刊论文 前10条

1 陈辉;;网球发球图像路径修正优化建模仿真[J];计算机仿真;2017年06期

2 郭丽娜;马刚;;一些图的Mycielski图的均匀全色数[J];济南大学学报(自然科学版);2017年02期

3 王岩;熊芳芳;卢曦;;应用于社区安防的车牌识别门禁系统关键技术研究[J];电脑编程技巧与维护;2016年19期

4 江红豆;李敬文;曹道通;江世明;;随机图的邻点可区别VI-均匀全染色算法[J];计算机工程与应用;2017年15期

5 丁丹军;;M(P_n)和M(C_n)的邻点可区别均匀全染色[J];河西学院学报;2016年02期

6 魏邦魁;强会英;王洪申;;冠图C_n■C_m的邻点可区别均匀E-全染色[J];淮阴师范学院学报(自然科学版);2016年01期

7 陈姗;万晓燕;吴永琢;;基于智能识别的金属加工过程监测[J];世界有色金属;2016年02期

8 王笑妍;刘焕平;;几类图的均匀邻点可区别Ⅰ-全染色[J];哈尔滨师范大学自然科学学报;2016年01期

9 强会英;王洪申;张彩霞;魏邦魁;;图C_(n,m)的邻点可区别均匀E-全染色[J];兰州理工大学学报;2015年05期

10 尹波;李敬文;代素敏;胡腾云;;随机图的正常均匀全染色算法[J];计算机应用;2015年08期

【二级参考文献】

相关期刊论文 前10条

1 ;Equitable Strong Edge Coloring of the Joins of Paths and Cycles[J];数学研究及应用;2012年01期

2 严谦泰;;几类图的均匀邻点可区别全染色[J];科技导报;2010年21期

3 马刚;马少仙;张忠辅;;一些联图的均匀全染色[J];应用数学学报;2010年04期

4 马刚;张忠辅;;若干倍图的邻点可区别均匀全染色[J];吉林大学学报(理学版);2009年06期

5 严谦泰;李武装;;关于一类二部图的均匀邻点可区别全染色[J];大学数学;2009年03期

6 ;Equitable Total Coloring of F_n ∨ W_n[J];Acta Mathematicae Applicatae Sinica;2009年01期

7 郝自军;张玉栋;张忠辅;;关于扇和完全等二部图联图的均匀全色数[J];大学数学;2009年01期

8 张忠辅;仇鹏翔;张东翰;卞量;李敬文;张婷;;图的倍图与补倍图(英文)[J];数学进展;2008年03期

9 闫丽宏;王治文;张忠辅;;关于路和路的联图的邻点可区别的均匀全染色[J];宁夏师范学院学报;2008年03期

10 马少仙;马刚;张忠辅;;关于图的均匀全色数分类[J];数学的实践与认识;2008年08期

【相似文献】

相关期刊论文 前10条

1 栗永安;若干图的均匀全染色[J];兰州铁道学院学报;1997年03期

2 马刚;张忠辅;;关于多重联图的均匀全染色[J];数学研究与评论;2007年02期

3 刘林忠，李敬文，张忠辅;若干平面图的均匀全染色[J];兰州铁道学院学报;1996年04期

4 马刚;马少仙;张忠辅;;一些联图的均匀全染色[J];应用数学学报;2010年04期

5 马刚;马明;张忠辅;;若干倍图的均匀全染色(英文)[J];数学研究;2009年01期

6 马刚;;若干图的倍图的点可区别均匀全染色[J];苏州科技学院学报(自然科学版);2013年01期

7 龚坤;张忠辅;王建方;;若干联图的均匀全染色(英文)[J];数学研究与评论;2008年04期

8 闫丽宏;王治文;张忠辅;;关于路和路的联图的邻点可区别的均匀全染色[J];宁夏师范学院学报;2008年03期

9 马刚;张忠辅;;若干倍图的邻点可区别均匀全染色[J];吉林大学学报(理学版);2009年06期

10 严谦泰;冉红;;P_n~k的均匀全染色[J];大学数学;2007年03期

相关硕士学位论文 前2条

1 马刚;关于图的均匀全染色[D];兰州大学;2007年

2 桂浩;图的均匀点染色与均匀全染色[D];浙江师范大学;2014年

，

本文编号：1503918