陳忠,李銀奎

(青海民族大學(xué)數(shù)學(xué)系,青海西寧 810007)

完全k叉樹(shù)的粘連度

陳忠,李銀奎

(青海民族大學(xué)數(shù)學(xué)系,青海西寧 810007)

相對(duì)于其他網(wǎng)絡(luò)抗毀性的描述指標(biāo)來(lái)說(shuō),圖的粘連度是比較理想,也是比較合理的刻畫(huà)參數(shù).而完全k叉樹(shù)作為重要的網(wǎng)絡(luò)結(jié)構(gòu)被廣泛地應(yīng)用在通信網(wǎng)和嵌入式系統(tǒng)芯片的優(yōu)化設(shè)計(jì)方面.本文通過(guò)優(yōu)化組合方法界定了完全k叉樹(shù)的粘連度和毀裂度.從某種程度刻畫(huà)了網(wǎng)絡(luò)的抗毀性,為網(wǎng)絡(luò)設(shè)計(jì)提供了一種客觀(guān)的理論依據(jù).完全k叉樹(shù)的粘連度為,如h是偶數(shù).完全k叉樹(shù)的毀裂,如h是偶數(shù).

粘連度;毀裂度;完全k叉樹(shù)

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

1 引言

計(jì)算機(jī)與通訊網(wǎng)絡(luò)設(shè)計(jì)要求網(wǎng)絡(luò)結(jié)構(gòu)不易被破壞且被毀后容易修復(fù).這種客觀(guān)要求可用多種圖論參數(shù)來(lái)刻畫(huà),像堅(jiān)韌度、完整度、離散數(shù)、粘連度和毀裂度都是很好的描述指標(biāo).事實(shí)上,在網(wǎng)絡(luò)抗毀性分析方面,一般來(lái)講,有三方面因素需主要考慮:

(1)網(wǎng)絡(luò)中失去效力的站點(diǎn)數(shù)目;

(2)剩余網(wǎng)絡(luò)的連通分支數(shù);

(3)仍然聯(lián)通的最大分支的大小.

像連通度只是基于(1)的考慮;堅(jiān)韌度、完整度、離散數(shù)是基于(1),(2)兩方面的考慮;而粘連度和毀裂度則是考慮了(1),(2),(3)三方面因素,因而更合適地刻畫(huà)了網(wǎng)絡(luò)結(jié)構(gòu)的抗毀性.完全k叉樹(shù)則是在超級(jí)計(jì)算機(jī)系統(tǒng)的芯片嵌入方面有著廣泛應(yīng)用的重要結(jié)構(gòu).本文作者界定了完全k叉樹(shù)的粘連度,從而從某種程度更好地刻畫(huà)了完全k叉樹(shù)的毀裂度,為網(wǎng)絡(luò)設(shè)計(jì)和維護(hù)者提供了一定的理論支持.本文用ω(G)和m(G)分別表示圖G的連通分支數(shù)和最大分支的階(所含結(jié)點(diǎn)數(shù)).

本文所討論的圖均為簡(jiǎn)單有限圖,對(duì)于文中未定義的術(shù)語(yǔ)和概念參見(jiàn)文獻(xiàn)[1].如果G-X不連通或G-X只含一個(gè)點(diǎn),則稱(chēng)點(diǎn)集X?V(G)為G的割集.用G[S]表示圖G的S導(dǎo)出子圖.

2 完全k叉樹(shù)的粘連度與毀裂度

[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叉樹(shù)的完整度與離散數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),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)

the tenacity,rupture degree,com p lete k-ary trees

O 157.5

A

1008-5513(2013)05-0484-05

2012-04-08.

教育部“春暉計(jì)劃”(Z2010071).

陳忠(1975-),碩士,講師，研究方向：圖論與網(wǎng)絡(luò)優(yōu)化.

李銀奎(1967-),碩士,教授,研究方向：圖論與網(wǎng)絡(luò)優(yōu)化.

2010 MSC:05C15