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

宋晨; 李敬文; 张荞君

doi:10.19603/j.cnki.1000-1190.2023.04.003

华中师范大学学报（自然科学版） ›› 2023, Vol. 57 ›› Issue (04) : 500 -507. DOI: 10.19603/j.cnki.1000-1190.2023.04.003

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

宋晨, 李敬文, 张荞君

作者信息 +

Author information +

文章历史 +

PDF

摘要

对于图G（V,E）,若存在正整数k（1≤k≤|G|+|E|）和映射f:V（G）∪Ε（G）→{1,2,…,k},使得对任意两点u,v∈V（G）,有S（u）=S（v）,其中■,则称f为G的点魔幻全染色，且称χ_VMTC（G）=max{k|k-VMTC of G}为点魔幻全色数.在已有的点魔幻标号和点可区别染色研究基础之上，结合实际问题提出了点魔幻全染色（VMTC）,设计了一种新型的点魔幻全染色算法，该算法使用迭代寻优的方式对随机图进行了研究，通过实验结果分析，总结得到了若干定理并给出证明.