阿波羅網絡模型的廣義邊魔幻優(yōu)美全標號

蘇 靜, 閆光輝, 姚 兵,

(1. 西北師范大學 數(shù)學與統(tǒng)計學院, 蘭州 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)的邊魔幻優(yōu)美全標號 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年代開始，我國各地相繼創(chuàng)建大批以經濟技術開發(fā)區(qū)和高新技術產業(yè)開發(fā)區(qū)為主的經濟功能區(qū)。經濟功能區(qū)是由政府主導，利用資源豐富、交通便利、信息暢通等相對區(qū)位優(yōu)勢，進行集中投入、連片開發(fā)，實行特殊經濟政策及管理模式的地區(qū)或城市的特定區(qū)。經過幾十年實踐發(fā)展，經濟功能區(qū)管理模式日趨穩(wěn)定成熟，對經濟社會發(fā)展的影響不斷增大，特別是聚集起大量高新產業(yè)人員、技術、裝備，國防動員潛力資源日益豐厚，成為新時期推進基干民兵（簡稱“民兵”，下同）編組“三個拓展”，編建民兵新質力量的新型陣地，急需加強對經濟功能區(qū)民兵建設的研究。

輸入: 阿波羅網絡模型A(t);

輸出: 阿波羅網絡模型的廣義邊魔幻優(yōu)美全標號.

步驟如下:

① 取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)的邊魔幻優(yōu)美全標號 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

證明: 優(yōu)化阿波羅網絡模型的廣義邊魔幻優(yōu)美全標號, 使得邊魔幻常數(shù)ki的個數(shù)比定理1中ki的個數(shù)少. 對網絡模型A(t)(t≤2), 按下列算法標號:

輸入: 網絡模型A(t)(t≤2);

輸出： 網絡模型A(t)(t≤2)的廣義邊魔幻優(yōu)美全標號.

步驟如下:

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)的 邊魔幻優(yōu)美全標號 magic graceful totally labelling of network model A(2) in theorem 2

對網絡模型A(t)(t≥3), 可根據(jù)阿波羅網絡模型的拓撲結構得到標號, 并選擇A(2)的標號作為“拓撲結構基”, 即網絡模型A(t)(t≥3)的標號均由A(2)的標號生成,A(2)的標號如圖4所示. 下面用數(shù)學歸納法證明該類廣義邊魔幻優(yōu)美全標號存在.

當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)均變?yōu)?個A(2), 故A(k+1)是由3k-1個A(2)拼接而成. 上述方法得到的A(2)拼接在一起可得到標號, 這里要求公共頂點和公共邊的標號相同, 表3列出了網絡模型前5個時刻的實驗結果. 由表3可見, 定理2中的方法得到的魔幻常數(shù)ki的個數(shù)比定理1中的少.

表3 定理2中方法得到的5個時刻網絡模型魔幻常數(shù)ki的個數(shù)

由圖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)所示.

圖5 A(1)和A(2)的拓撲結構劃分Fig.5 Topological structure partition of A(1) and A(2)

定理3阿波羅網絡模型中每個頂點各加一個葉子后的模型記為AL(t), 由定理2的標法可得

圖6 AL(2)的一個邊魔幻優(yōu)美全標號 magic graceful totally labelling of AL(2)