图的点可约全标号算法研究

对于无向连通图G(V,E),若存在一个单射函数f:V(G)∪E(G)→{1,2,…,|V|+|E|},使得对图中所有度数相同的点及其关联边的标号和都有Sum(u)=f(u)+∑uv∈E(G)f(uv)=K,K为常数,称映射关系f为图的点可约全标号(vertex reducible total labeling,VRTL)。借助计算机的算法及优化点可约全标号的传统解空间的方式,设计点可约全标号算法,针对点可约全标号的解空间进行递归搜索,对有限点以内的连通图进行点全标号验证。通过观察有限点内图的标号规律,延展出能刻画无限点的同类图的标号规律,给出具有延展性的全标号定理及数学证明。

若干特殊图及其联图的邻点可约边标号算法

设G(V,E)是一个简单图,若存在一一映射f:E(G)→{1,2,…,|E|},使得对任意两点uv∈E(G),如果d(u)=d(v),有S(u)=S(v),其中S(u)=∑uω∈E(G)∫(uω),d(u)表示点u的度,则称f为G的邻点可约边标号(adjacent vertex reducible edge labeling,AVREL)。在已有图标号概念与可约染色概念的基础之上,结合实际问题提出了邻点可约边标号新概念,并设计了一种新的邻点可约边标号算法(简称AVREL算法)。该算法对边初始标号,然后针对邻点可约边标号的解空间进行递归搜索,最终筛选出满足边标号的图集并以标号矩阵的形式输出。经过对算法结果分析,总结出若干路图、扇图、星图、轮图、树图等特殊图及其联图在不同情况下的邻点可约边标号定理,并给出了证明。