若干联图的邻点可约全标号

摘要

对于无向连通图G（V,E）,若存在一个单映射f:V（G）∪E（G）→{1,2,…,|V|+|E|},如果uv∈E（G）且d（u）=d（v）,有S（u）=S（v）,其中■表示点u的度，则称f为G的邻点可约全标号（adjacent vertex reducible total labeling, AVRTL）。结合遗传算法和粒子群算法设计一种启发式搜索算法，可以判断有限点内随机图是否存在AVRTL。通过对实验结果分析，总结了若干联图的定理并给出证明。得到结论：如果子图G₁和G₂是AVRTL图，则图运算↑_ab具有封闭性，即联图G₁↑_abG₂亦为AVRTL图。

关键词

联图 / 邻点可约全标号 / AVRTL图 / 启发式搜索算法 / 图运算