随机图的点魔幻全染色算法  

Vertex magic total coloring algorithm for random graphs

作　　者：宋晨 李敬文[1] 张荞君 SONG Chen;LI Jingwen;ZHANG Qiaojun(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《华中师范大学学报（自然科学版）》2023年第4期500-507,共8页Journal of Central China Normal University：Natural Sciences

基　　金：国家自然科学基金项目(11961041,62062049,11461038).

摘　　要：对于图G(V,E),若存在正整数k(1≤k≤|G|+|E|)和映射f:V(G)∪Ε(G)→{1,2,…,k},使得对任意两点u,v∈V(G),有S(u)=S(v),其中S(u)=f(u)+∑_(uw∈E(G))f(uw),则称f为G的点魔幻全染色,且称χVMTC(G)=max{k|k-VMTC of G}为点魔幻全色数.在已有的点魔幻标号和点可区别染色研究基础之上,结合实际问题提出了点魔幻全染色(VMTC),设计了一种新型的点魔幻全染色算法,该算法使用迭代寻优的方式对随机图进行了研究,通过实验结果分析,总结得到了若干定理并给出证明.For graph G(V,E),if there is a positive integer k(1≤k≤|G|+|E|)and a mapping f:V(G)∪E(G)→{1,2,…,k},so that for any two points u,v∈V(G),there is S(u)=S(v),where S(u)=f(u)+∑_(uw∈E(G))f(uw),then f is called the vertex magic total coloring of G,and χ_(vmtc)(G)=max{k|k-VMTC of G}is called the vertex magic panchromatic number.Based on the existing research on vertex magic labeling and vertex distinguishing coloring,combined with practical problems,vertex magic total coloring is proposed,and a new vertex magic total coloring algorithm is designed.The algorithm uses iterative optimization to study the random graph.Through the analysis of experimental results,several theorems and proofs are obtained.

关 键 词：随机图 算法 点魔幻全色数 点魔幻全染色 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]