第57卷第2期华中师范大学学报(自然科学版)Vol.57No.22023年4月JOURNALOFCENTRALCHINANORMALUNIVERSITY(Nat.Sci.)Apr.2023收稿日期:2021-11-09.基金项目:国家自然科学基金项目(11961041,62062049,11461038).*通信联系人.E-mail:lijingwen28163.com.DOI:10.19603/j.cnki.1000-1190.2023.02.003文章编号:1000-1190(2023)02-0201-07若干联图的邻点和可约边染色罗榕,李敬文*,张树成,张荞君(兰州交通大学电子与信息工程学院,兰州730070)摘要:该文在已有的图染色概念基础之上,结合实际问题提出了邻点和可约边染色的新概念,设计了一种新型的邻点和可约边染色(adjacentvertexsumreducibleedgecoloring,AVSREC)算法,该算法采用迭代寻优方式针对有限点内的所有非同构图集进行求解,通过实验结果分析,总结得到了若干联图的定理并给出证明.关键词:联图;邻点和可约边染色;邻点和可约边色数;算法中图分类号:TP301.5文献标志码:A开放科学(资源服务)标志码(OSID):图染色问题向来是图论中的热门研究课题,染色问题在近年来有很多方面的应用,学者们在传统染色的基础上提出了可区别染色以及可约染色等新型染色概念[1-9].Burris[1]在1993年提出了满足正常边染色的基础上要求任意两点的色集合不同的点可区别边染色的概念,又和Schelp在1997年提出了点可区别边染色的相关猜想[2].2002年,张忠辅教授等提出了在正常边染色的基础上满足任意相邻点的色集合均不同的邻点可区别边染色[5],后来Zhu等进一步研究和探讨了可区别染色[10].2006年,张忠辅等[11]提出了距离不大于β的点可区别边染色的概念,又在2009年在可区别染色的理论基础上提出了一系列图的可约染色概念[12].后来开启图的色和可区别染色研究先河的是Chartrand[13],定义是要求任意两点及其关联边的色和不同.Flandrin等[14]在邻和可区别边染色的基础上提出了邻和可区别边染色猜想.Pilsniak等在2015年的文献中提出了图的邻和可区别全染色的概念及猜想[15].本文在上述提到的染色概念基础上提出邻点和可约边染色新概念,通过借鉴传统的遗传算法、蚁群算法、模拟退火算法等随机搜索的智能算法设计思路,设计一种新型的邻点和可约边染色(adjacentvertexsumreducibleedgecoloring,AVSREC)算法,得到了有限点以内的路图、圈图、星图以及这些特殊图组合得到的联图的结果.最后对实验结果进行分析,给出若干定理及证明.1基础知识本文主要研究随机图的邻点和可约边染色,涉及的图G(V,E)均表示具有p个顶点,q条边的简单无向连通图,d(x)表示点x...
