阿波罗网络模型的广义边魔幻优美全标号

2018-11-06闫光辉

吉林大学学报（理学版） 2018年3期

苏静, 闫光辉, 姚兵,

(1. 西北师范大学数学与统计学院, 兰州 730070; 2. 兰州交通大学电子与信息工程学院, 兰州 730070)

1 预备知识

图1 阿波罗网络模型前4个时刻的拓扑结构Fig.1 Topological structure of Apollonian network models at first four moments

定义1一个(p,q)-图G的标号f是指f:V(G)→[m,n]或f:V(G)∪E(G)→[m,n]. 记(p,q)-图G的顶点标号集为f(V(G))={f(x)|x∈V(G)},图G的边标号集为f(E(G))={f(uv)|uv∈E(G)}. 若f(V(G))=|V(G)|=p, 则称f是图G的顶点正常标号; 若f(E(G))=|E(G)|=q, 则称f是图G的边正常标号; 若f(V(G)∪E(G))=|V(G)|+|E(G)|=p+q, 则称f是图G的全正常标号.

2 主要结果

图2 由方法1)得到的A(1)和A(2)的边魔幻优美全标号 magic graceful totally labellings of A(1) and A(2) obtained by method 1)

模型(p,q)[1,p+q]Emgtl(A(t))A(0)(3,3)[1,6]1A(1)(4,6)[1,10]2A(2)(7,15)[1,22]7A(3)(16,42)[1,58]19A(4)(43,123)[1,166]64

方法2) 以算法的形式给出证明.

20世纪80年代开始，我国各地相继创建大批以经济技术开发区和高新技术产业开发区为主的经济功能区。经济功能区是由政府主导，利用资源丰富、交通便利、信息畅通等相对区位优势，进行集中投入、连片开发，实行特殊经济政策及管理模式的地区或城市的特定区。经过几十年实践发展，经济功能区管理模式日趋稳定成熟，对经济社会发展的影响不断增大，特别是聚集起大量高新产业人员、技术、装备，国防动员潜力资源日益丰厚，成为新时期推进基干民兵（简称“民兵”，下同）编组“三个拓展”，编建民兵新质力量的新型阵地，急需加强对经济功能区民兵建设的研究。

输入: 阿波罗网络模型A(t);

输出: 阿波罗网络模型的广义边魔幻优美全标号.

步骤如下:

① 取0号点中任意一个记为顶点u, 令f(u)=1; A(t)中0号点的度为2t+1;

② 选取所标顶点中标号最小的顶点a, a∈{a|f(a)=minf(u)}, 然后将其邻边按从左至右(或从右至左)的顺序依次标号f(av), 其中v表示顶点a的邻点;

③ 从②所标的边中找到最小标号边对应的另一端点b, 满足f(ab)=minf(uv), 将其从小到大标号, 标完顶点a的所有邻点后返回②.

图3 由方法2)得到的A(1)和A(2)的边魔幻优美全标号 magic graceful totally labellings of A(1) and A(2) obtained by method 2)

模型(p,q)[1,p+q]Emgtl(A(t))A(0)(3,3)[1,6]1A(1)(4,6)[1,10]2A(2)(7,15)[1,22]6A(3)(16,42)[1,58]15A(4)(43,123)[1,166]49

证明: 优化阿波罗网络模型的广义边魔幻优美全标号, 使得边魔幻常数ki的个数比定理1中ki的个数少. 对网络模型A(t)(t≤2), 按下列算法标号:

输入: 网络模型A(t)(t≤2);

输出：网络模型A(t)(t≤2)的广义边魔幻优美全标号.

步骤如下:

1) 顶点标号: 先标t=0时刻的3个点, 然后标t时刻网络新增的t号点(t=1时新增1个顶点,t=2时新增3个顶点), 再标t-1时刻新增顶点, 直到A(t)中所有的顶点均得到标号.

2) 边标号: 先标网络初始时刻的3条边, 然后标t=1时刻新产生的3条边, 再标度最大(邻边最多)的1号点剩余未标号的邻边, 最后标剩余t时刻新产生的边, 按边uv的顶点标号满足f(u)与f(v)和的值从小到大的顺序, 直至所有的边均得到标号.

图4 定理2中网络模型A(2)的边魔幻优美全标号 magic graceful totally labelling of network model A(2) in theorem 2

对网络模型A(t)(t≥3), 可根据阿波罗网络模型的拓扑结构得到标号, 并选择A(2)的标号作为“拓扑结构基”, 即网络模型A(t)(t≥3)的标号均由A(2)的标号生成,A(2)的标号如图4所示. 下面用数学归纳法证明该类广义边魔幻优美全标号存在.

当t=3时, 网络模型A(3)由三部分相同结构的A(2)构成, 在标号过程中以A(2)为单位进行标号, 共标3个A(2); 当t=k时,A(k)共有3k-2个A(2); 当t=k+1时, 相当于对模型A(k)添加顶点, 使得每个A(2)均变为3个A(2), 故A(k+1)是由3k-1个A(2)拼接而成. 上述方法得到的A(2)拼接在一起可得到标号, 这里要求公共顶点和公共边的标号相同, 表3列出了网络模型前5个时刻的实验结果. 由表3可见, 定理2中的方法得到的魔幻常数ki的个数比定理1中的少.

表3 定理2中方法得到的5个时刻网络模型魔幻常数ki的个数

由图1所示的阿波罗网络模型的拓扑结构可知,t时刻该网络模型可分为拓扑结构完全相同的3个模块.图5(A)表示网络模型A(1), 显然, 网络模型可分为拓扑结构完全相同的A,B,C三个模块, 而A,B,C三个模块的结构都恰好是网络模型A(0),A和B有两个公共顶点和一条公共边. 同理,B和C、A和C之间均分别有两个公共顶点和一条公共边, 因此3个拓扑结构相同的网络模型A(0)拼接成为网络模型A(1). 同理, 3个模块A(1)可构成网络模型A(2), 如图5(B)所示.