一类增长网络模型的生成树

2015-12-01 08:15张婉佳
关键词:条边数目度数

张婉佳,刘 霞,姚 兵

(西北师范大学数学与统计学院,甘肃 兰州730070)

物联网是一个基于互联网、传统电信网等信息承载体,让所有能够被独立寻址的普通物理对象实现互联互通的网络.众所周知,图论的方法已经成功地应用到各种网络研究中[1-8].由于我们周围的网络几乎都是无标度网络 (scale-free networks)和小世界网络(small-world networks)[9-10],这些大型动态网络有着庞大的节点和连线,无法用图形将他们描绘和刻画.然而,一般网络均是连通的.图论中研究连通性的有力工具之一是生成树.而且生成树已经成功地应用到实际问题研究[11],积累了大量的理论成果.生成树最典型的应用之一是Perlman Radia[12]利用生成树与网络间的结构关系发明了广泛用于网桥、交换机上的生成树协议.毫无疑问,物联网的研究必将给数学本体带来新问题、新课题,从而产生新的研究对象,研究结果的积累和升华最终将导致新数学分支的产生[1].

为了更好地理解和认识复杂网络,人们采用建立动态网络模型来逼近或模拟现实网络[13-14],刻画其拓扑结构.张忠志等[13]通过迭代算法给出一类增长网络模型,刻画了其拓扑性质,但没有涉及生成树,而且他们的增长网络模型初始状态是一个三角形.一般地,增长网络的初始状态是任意的.基于文献[13]的增长网络模型,本文建立了初始网络可以是任何一个连通网络的增长网络模型,并给出其基本性质和具有最多叶子生成树,提出一些新的统计方法,文中涉及的图均为简单、无向、有限图.记号[m,n]代表集合{m,m+1,…,n},整数m和n满足0≤m<n.度数为1的节点叫做叶子.若一个节点u连有k条边,则称u为k-度节点.(p,q)-图是有p个节点和q条边的图.

1 基本概念和边界增长网络模型

令 N(0)是有nv(0)个节点和ne(0)条边的连通初始网络(以下初始网络总是连通的,不再特别指出),V(0)和E(0)分别为 N(0)的节点集合和边集合.显然,nv(0)=|V(0)|,ne(0)=|E(0)|.对于 N(0)中的每条边uv,增加一个不在N(0)中的新节点w,并且将w与边uv的两个端点u和v分别连接,得到一个新网络模型N(1).网络模型N(1)的节点集合为V(1)=V(0)∪X1,边集合为E(1)=E(0)∪Y1,其中X1是新加入到初始网络N(0)的节点之集,Y1={wu,wv:uv∈E(0),w∈X1}是新添加进初始网络N(0)的边之集.网络模型N(1)有如下的性质:节点数目nv(1)=nv(0)+ne(0),边数目ne(1)=ne(0)+2ne(0)=3ne(0),其中ne(0)=|X1|,2ne(0)=|Y1|.注意到,|Y1|=2|X1|.对于整数t≥2,在第t步,对第t-1步中产生的网络模型N(t-1)中的新增边集合Yt-1的每条边添加一个新节点w,并且将w与这条边的两个端点分别连接,从而得到高阶的网络模型N(t),以下称作边界增长网络模型.图1的例子解释边界增长网络模型N(t).模型N(t)的节点集合和边集合分别为:

图1 增长网络模型N(k),k=0,1,2,3Fig.1 Four network models N(k),k=0,1,2,3

其中,Xt是新加入到N(t-1)的节点的集合,新添加的边的集合Yt={wu,wv:uv∈Yt-1,w∈Xt}.注意到:|Xt|=|Yt-1|,|Yt|=2|Xt|,这里Y0=E(0),|Xt|=ne(0)×2t-1.令nv(t)和ne(t)分别表示边界增长网络模型N(t)的节点数目和边数目.根据公式(1),有

边界增长网络模型N(t)的平均度〈k〉满足

故,N(t)属于稀疏型模型.令Δ(N(0))是 N(0)的最大度.边界增长网络模型N(t)的最大度Δ(N(t))=(t+1)·Δ(N(0)),最小度δ(N(t))=2.

2 具有最多叶子的生成树

不失一般性,边界增长网络模型N(t)的具有最多叶子的生成树总记为TM(t).用L(H)表示一棵树H的全体叶子的集合,则对N(t)的每一棵生成树H,都有|L(TM(t))|≥|L(H)|.下面,我们将证明高阶边界增长网络模型N(t)的一棵生成树TM(t)可以从低阶边界增长网络模型N(t-1)的一棵生成树TM(t-1)通过添加叶子而获得.由于N(t)的直径不大于TM(t)的直径,我们将要用TM(t)的直径来说明N(t)是小世界网络模型.记N(t)的节点u的度数为d(N(t),u).

2.1 具有最多叶子生成树的性质

引理1 对于所给定的初始网络N(0)和整数t≥1,边界增长网络模型N(t)的任何生成树TM(t)满足Xt⊂L(TM(t)).

证明 考虑 X1⊂L(TM(1)).假设在 N(1)中存在一个节点w∈X1,但是它不属于叶子集合L(TM(1)).由于在N(1)中节点w为2-度节点,并且和N(1)中的边界边uv∈E(0)的2个端点相邻.所以u和v中至少有一个不是TM(1)的叶子,不妨设u∉L(TM(1)).通过删除边wv,连接u和v,则有N(1)的另一棵生成树H.显然,w∈L(H),L(TM(1))⊂L(H),从而有|L(H)|>|L(TM(1))|,这与 TM(1)具有最多叶子的定义冲突.对t≥2,同理可证 Xt⊂L(TM(t)).

引理2 设初始网络N(0)的每一个节点的度数至少是2.则对t≥2和0≤k≤t-2,边界增长网络模型 N(t)的生成树TM(t)的叶子集L(TM(t))和边界增长网络模型N(k)的节点集V(k)没有公共节点,即是L(TM(t))∩V(k)=ø.

证明 对t=2,假设有节点v∈L(TM(2))∩V(0).由于初始网络N(0)的每一个节点的度数至少是2,所以节点v在N(1)中与节点u和u′分别相邻.在N(2)中,关于节点v及其周围的结构如图2(a)所示.因为节点v是生成树TM(2)的叶子,则与节点v相邻的节点w1和w2都不是TM(2)的叶子,与节点v相邻的节点w1,2和 w2,1必须是 TM(2)的叶子(见图2(b)).则可构造边界增长网络模型N(2)的另一棵生成树H如下:在生成树TM(2)中,用边将节点v与节点w1,2和 w2,1分别连接,删去边 w1w1,2和边 w2w2,1.显然,N(2)的生成树H 的叶子数目比TM(2)的叶子数目多1(见图2(c)),这矛盾于生成树TM(2)是N(2)的叶子数目最多的生成树的定义,故有L(TM(2))∩V(0)=ø.

图2 引理2证明的图示Fig.2 Adiagram for illustrating the proof of Lemma 2

当t≥3时,若有节点a∈L(TM(t))∩V(k),则节点a在边界增长网络模型N(k)中的度数至少是2,采用完全相同于上面的证明方法,我们仍可得到矛盾.换句话说,L(TM(t))∩V(k)=ø.本引理得证.

令D(H)是网络 H 的直径,即D(H)=max{d(x,y):x,y∈V(H)},这里的d(x,y)是节点x 与节点y间最短路的边数目.

定理1 设初始网络N(0)有ne(0)条边,则当t≥3时,边界增长网络模型N(t)的任何一棵生成树TM(t)的叶子个数为

它的直径满足 D(TM(t))≤D(TM(0))+2(t-1).

证明 定义边界增长网络模型N(t)的节点的标号函数f 为:f(u)=0,u∈V(0);f(u)=j,u∈Xj,j∈ [1,t].由引理1,知 X1∩L(TM(1))=X1.所以,(L(TM(1))\X1)⊆L(TM(0)).令l(0)=|L(TM(0))|-|L(TM(1))\X1|,则生成树 TM(1)的叶子数目为|L(TM(1))|=|X1|+l(0).当t≥3时,根据边界增长网络模型 N(t)的构造和引理 2,TM(t)可由TM(t-1)生成.由TM(1)生成TM(2)的方法如下:对节点 u ∈V(TM(1))且 f(u)=0,给 u 添加d(N(0),u)片叶子,得生成树 TM(2)的叶子数目|L(TM(2))|= | X1|+ ∑u∈V(0)d(N(0),u)=3ne(0).同理,TM(3)可由TM(2)经如下的方法生成:给满足f(u)=0的节点u添加d(N(0),u)片叶子,给满足f(v)=1的节点v添加2片叶子,则得|L(TM(3))|=|X2|+2|X1|+∑u∈V(0)d(N(0),u)=6ne(0).一般地,边界增长网络模型N(t)的构造说明生成树TM(t)可给生成树TM(t-1)添加叶子得来,即给TM(t-1)中满足f(u)=0的节点u添加d(N(0),u)片叶子,给 TM(t-1)中满足t-2≥f(v)≥1的节点v添加2片叶子.从而,TM(t)的叶子个数为

公式(4)得证.根据TM(t)的构造,每次给生成树TM(t-1)添加叶子得到生成树TM(t),也就是说,给生成树TM(t-1)的最长路增加了2.注意到,TM(1)和TM(2)的直径均不超过 D(TM(0))+2.则当t≥3 时,TM(t)的 直 径 满 足 D(TM(t))≤D(TM(0))+2(t-1).本定理得证.

当t→∞,定理1的结论导致下面的2个极限

以及

由式(5)可以看到,生成树TM(t)的每个非叶子节点平均控制3片叶子;式(6)说明TM(t)中每个非叶子节点平均控制边界增长网络模型N(t)的16条边.

2.2 具有最多叶子生成树的统计指标

2.2.1 度 谱

下面的讨论总假定初始网络N(0)的每一个节点的度数至少是2.根据引理2的结论及其证明,当t≥2时,则生成树TM(t)的度谱为(图3):

(i)在 TM(t)中,Xt,Xt-1的节点均为 TM(t)的叶子;

(ii)在TM(t)中,Xi-1的节点的度均为2(t-i)+1,i∈[2,t-1];

(iii)在 TM(t)中,V(0)的节点u 的度为 (t-1)d(N(0),u)+d(TM(1),u).

也就是说,TM(t)\V(0)中度数d=1,3,5,2(t-2)+1的节点个数nt(d)=|Xt|+|Xt-1|,|Xt-2|,|Xt-3|,…,|X1|.

设n0(di)是初始网络N(0)中度数为di的节点的个数,且di≥di+1,i=1,2,…,p-1.不难算出,在初始网络N(0)中度数为di的节点i在N(t)中的度数为dti.从而,生成树TM(t)的度谱为:度数d=1,2,4,6,…,2(t-2),2(t-1)+1,2t,2t+2,dtp,dtp-1,…,dt1的节点个数nt(d)=|Xt|,|Xt-1|,|Xt-2|,|Xt-3|,…,|X1|,n0(dp),n0(dp-1),…,n0(d1).

2.2.2 度分布

由于TM(t)的度谱是离散型,则可计算它的随机选择恰好有k条边的节点的概率P(k).对τ<t和k=2(t-τ+1)+1,有

上式说明,最多叶子生成树TM(t)服从指数分布,TM(t)亦为指数型生成树.

2.2.3 边累积分布

在k (<t)时 刻,TM(k)的 边 数 目 记 为|E(TM(k))|,则对τ<t,TM(t)的边累积分布为

上式导致 Pe-cum(k)∝2τ+1-t.取τ= (t-1)-.这就证得最多叶子生成树TM(t)的边累积分布Pe-cum(k)服从幂律分布k-γk,其中γk=2+

2.3 (αk,βk)-生成树

计算TM(t)中度数不大于k的节点总数ST(≤k)=∑d≤knt(d),以及度数不大于k的节点的度数总和DT(≤k)= ∑d≤kd·nt(d),则TM(t)中度数不小于k的节点总数为ST(>k)=nv(t)-ST(≤k)和度数不小于k的节点的度数之和为DT(>k)=2ne(t)-DT(≤k).首先,计算生成树TM(t)中度数不大于k=2(t-τ+1)+1的节点总数,根据TM(t)的度谱,我们有

由于

图3 增长网络模型 N(k)的生成树TM(k),k=0,1,2,3Fig.3 Four spanning trees TM(k)of the models N(k),k=0,1,2,3

其中αk=2-(k-1)/2.则有计算节点数目比:

下面计算生成树TM(t)中度数不大于k的节点的度数总和

以及对较大的t,可估算

从而,当t较大时,得边数目比:

[1]Li L,Alderson D,Tanaka R,et al.Towards a theory of scale-free graphs:definition,properties,and implications[J].Internet Mathematics,2005,2(4):431-523.

[2]Bondy J A,Murty U S R.Graph theory[M].London:Springer,2008:157.

[3]Yao Bing,Zhang Zhongfu,Wang Jianfang.Some results on spanning trees[J].Acta Mathematicae Applicatae Sinica,English Series,2010,26(4):607-616.

[4]Yao Bing,Yao Ming,Chen Xiangen,et al.Research on edge-growing models related with scale-free small-world networks[J].Applied Mechanics and Materials,2013,513-517:2444-2448.

[5]Yao Bing,Yao Ming,Yang Sihua,et al.Labelling edges of models from complex networks[J].Applied Mechanics and Materials,2013,513-517:1858-1862.

[6]Wang Hongyu,Yao Bing,Yao Ming.Generalized edgemagic total labellings of models from reseaching networks[J].Information Sciences,2014,279:460-467.

[7]Yao Bing,Yang Chao,Yao Ming,et al.Graphs as models of scale-free networks[J].Applied Mechanics and Materials,2013,380-384:2034-2037.

[8]李振汉,唐余亮,雷鹰.基于ZigBee的无线传感器网络的自愈功能[J].厦门大学学报:自然科学版,2012,51(5):834-838.

[9]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286:509-512.

[10]Watts D J,Strogatz S H.Collective dynamics of′smallworld′networks[J].Nature,1998,393:440-442.

[11]Kim D H,Noh J D,Jeong H.Scale-free trees:the skeletons of complex networks[J].Physical Review E,2004,70:1-5.

[12]Perlman R.Hierarchical networks and the subnetwork partition problem[J].Computer Networks and ISDN Systems,1985,9:297-303.

[13]Zhang Zhongzhi,Rong Lili,Guo Chonghui.A deterministic small-world network created by edge iterations[J].Physica A,2006,363:567-572.

[14]杨光松,陈朝阳,袁飞.水声无线传感网中延迟敏感应用的跨层方案[J].厦门大学学报:自然科学版,2014,53(3):336-341.

猜你喜欢
条边数目度数
《平行四边形》拓展精练
移火柴
图形中角的度数
2018年第2期答案
隐形眼镜度数换算
有关垂足三角形几个最值猜想的证明*
《哲对宁诺尔》方剂数目统计研究
牧场里的马
认识平面图形
探索法在数学趣题中的应用