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

Vertex reducibletotal labeling algorithm for graphs

对于无向连通图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)。借助计算机的算法及优化点可约全标号的传统解空间的方式,设计点可约全标号算法,针对点可约全标号的解空间进行递归搜索,对有限点以内的连通图进行点全标号验证。通过观察有限点内图的标号规律,延展出能刻画无限点的同类图的标号规律,给出具有延展性的全标号定理及数学证明。

For an undirected connected graph G(V,E),if there exists a injective function f:V(G)∪E(G)→{1,2,…,|V|+|E|},such that any edge uv∈E(G),Sum(u)=f(u)+∑uv∈E(G)f(uv)=K,K is a constant,where u is any vertex in G(p,q)with the same degree,then G(p,q)is a vertex reducible total labeling(VRTL)graph,and the injective function f is vertex reducible total labeling.By means of computer and the way of optimizing the solution space of the vertex reducible total labeling,the algorithm of the vertex reducible total labeling is designed,and the solution space of the vertex reducible total labeling is recursively searched.By observing the labeling law of graphs within finite vertices,the labeling law of graphs of the same kind that can describe infinite vertices is extended and the total labeling theorems with extensibility and mathematical proof are given.