完全k叉树的粘连度

2013-06-27陈忠李银奎

纯粹数学与应用数学 2013年5期

关键词：图论刻画网络结构

陈忠,李银奎

(青海民族大学数学系,青海西宁 810007)

完全k叉树的粘连度

陈忠,李银奎

(青海民族大学数学系,青海西宁 810007)

相对于其他网络抗毁性的描述指标来说,图的粘连度是比较理想,也是比较合理的刻画参数.而完全k叉树作为重要的网络结构被广泛地应用在通信网和嵌入式系统芯片的优化设计方面.本文通过优化组合方法界定了完全k叉树的粘连度和毁裂度.从某种程度刻画了网络的抗毁性,为网络设计提供了一种客观的理论依据.完全k叉树的粘连度为,如h是偶数.完全k叉树的毁裂,如h是偶数.

粘连度;毁裂度;完全k叉树

DO I：10.3969/j.issn.1008-5513.2013.05.007

1 引言

计算机与通讯网络设计要求网络结构不易被破坏且被毁后容易修复.这种客观要求可用多种图论参数来刻画,像坚韧度、完整度、离散数、粘连度和毁裂度都是很好的描述指标.事实上,在网络抗毁性分析方面,一般来讲,有三方面因素需主要考虑:

(1)网络中失去效力的站点数目;

(2)剩余网络的连通分支数;

(3)仍然联通的最大分支的大小.

像连通度只是基于(1)的考虑;坚韧度、完整度、离散数是基于(1),(2)两方面的考虑;而粘连度和毁裂度则是考虑了(1),(2),(3)三方面因素,因而更合适地刻画了网络结构的抗毁性.完全k叉树则是在超级计算机系统的芯片嵌入方面有着广泛应用的重要结构.本文作者界定了完全k叉树的粘连度,从而从某种程度更好地刻画了完全k叉树的毁裂度,为网络设计和维护者提供了一定的理论支持.本文用ω(G)和m(G)分别表示图G的连通分支数和最大分支的阶(所含结点数).

本文所讨论的图均为简单有限图,对于文中未定义的术语和概念参见文献[1].如果G-X不连通或G-X只含一个点,则称点集X⊆V(G)为G的割集.用G[S]表示图G的S导出子图.

2 完全k叉树的粘连度与毁裂度

[1]Cozzen M,M oazzam i D,Stueck le,S.The tenacity of a graph[C]//Proc.Seven th International Con ference on the Theory and App lications of Graphs.New York:W iley,1995.

[2]Li Y,Zhang S,Li X.The rupture degree of graphs[J].Int.J.Com puter M ath.,2005,82(7):793-803.

[3]Bondy J A,M urty U S R.G raph Theory w ith A pp lications[M].New York:The M acm illan Press LTD, 1976.

[4]Li Y.The rupture degree of trees[J].Int.J.Com puter M ath.,2008,85(11):1629-1635.

[5]李银奎,陈忠.完全k叉树的完整度与离散数[J].纯粹数学与应用数学,2011,27(3):1-7.

The tenacity and rup tu re degree of the com p lete k-ary tree Chen Zhong,Li Yinkui

(Departm ent of M athem atics,Q inghai Nationalities College,X ining 810000,China)