完全k叉樹的粘連度

陳忠,李銀奎

(青海民族大學數學系,青海西寧 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)

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

O 157.5

A

1008-5513(2013)05-0484-05

2012-04-08.

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

陳忠(1975-),碩士,講師，研究方向：圖論與網絡優化.

李銀奎(1967-),碩士,教授,研究方向：圖論與網絡優化.

2010 MSC:05C15