本文關鍵詞：星連通圈網(wǎng)絡和三角塔網(wǎng)絡的若干性質研究

  更多相關文章： 互連網(wǎng)絡 星連通圈網(wǎng)絡 三角塔網(wǎng)絡 圖的嵌入 直徑 Hamilton圈 條件連通度

【摘要】：互連網(wǎng)絡是超級計算機的重要組成部分.在設計和選擇一個互連網(wǎng)絡的拓撲結構時,Hamilton性和可靠性是評估網(wǎng)絡性能的重要指標,而條件連通度和限制連通度為衡量網(wǎng)絡的可靠性提供了度量參數(shù).本文討論了星連通圈網(wǎng)絡和三角塔網(wǎng)絡拓撲結構中的幾個問題,主要結果如下：1.星連通圈網(wǎng)絡的主要結論：2010年,師海忠提出了一個猜想：星連通圈網(wǎng)絡n-SCC(n≥4)可分解為邊不交的一個Hamilton圈和一個完美對集的并.在本文中證明當n=4時是成立的,另外得到如下結果：(1)星連通圈網(wǎng)絡中存在3·2l(3≤l≤nl/2)圈,且當n=4時,4-SCC是Hamilton圖,當n=5時,發(fā)現(xiàn)5-SCC中存在18-400的偶圈.(2)完全二叉樹可以嵌入到星連通圈網(wǎng)絡,且該嵌入的膨脹數(shù)為1,同時給出了完全二叉樹嵌入星連通圈網(wǎng)絡的構造算法.(3]通過分析和研究,我們得到了星連通圈網(wǎng)絡n-SCC的條件連通度和簡單的限制連通度如下：當n=3時,κ1(3-SCC)=2,當n=4時,κ1(4-SCC)=3,當n5時,κ1(n-SCC)=4而當n4時,κ2(n-SCC)=n-1.并且星連通圈網(wǎng)絡的1-條件連通度與2-限制連通度是相等的.2.三角塔網(wǎng)絡的主要結果：(1)分析了一種新的互連網(wǎng)絡-三角塔網(wǎng)絡.當n4時,它是極大連通的,緊的超連通的,即三角塔網(wǎng)絡的連通度κ(TTn)=2n-3星網(wǎng)絡是三角塔網(wǎng)絡的子網(wǎng)絡,說明Sn能以膨脹數(shù)1嵌入TTn.(2)給出了三角塔網(wǎng)絡的直徑和平均距離分別是「3(n-1)-1/2」和n+2/n-1-2Hn/n(n-1)-Hn. (3)提出了關于三角塔網(wǎng)絡Hamilton性的一簇猜想：當n3時,三角塔網(wǎng)絡TTn可以分解成k(1kn-2)個邊不交的哈密頓圈和2n-3-2k個完備匹配的并,且這個完備匹配和哈密頓圈是邊不交的.并且證明這個猜想對于n=3,4以及n=5,6,k=1,2時是正確的.
【關鍵詞】：互連網(wǎng)絡 星連通圈網(wǎng)絡 三角塔網(wǎng)絡 圖的嵌入 直徑 Hamilton圈 條件連通度
【學位授予單位】：西北師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5;TP338
【目錄】：

• 摘要8-10
• Abstract10-12
• 第1章 研究背景12-14
• 1.1 研究背景12-13
• 1.2 本文的主要工作13-14
• 第2章 基本知識14-21
• 2.1 圖論的有關術語及符號14-15
• 2.2 有關連通性方面的概念及一些引理15-17
• 2.3 星連通圈網(wǎng)絡的概念和若干性質17-18
• 2.4 三角塔網(wǎng)絡的概念和若干性質18-21
• 第3章 星連通圈網(wǎng)絡的主要結果21-38
• 3.1 星連通圈網(wǎng)絡n-SCC的泛圈性21-29
• 3.2 完全二叉樹到星連通圈網(wǎng)絡的嵌入29-32
• 3.3 星連通圈網(wǎng)絡的條件點連通度32-38
• 第4章 三角塔網(wǎng)絡的主要結果38-44
• 4.1 三角塔網(wǎng)絡的直徑和平均距離38-41
• 4.2 三角塔網(wǎng)絡的Hamilton性41-44
• 第5章 結束語44-45
• 參考文獻45-49
• 攻讀碩士學位期間發(fā)表的論文49-50
• 致謝50

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 李炯生,范益政;關于圖的代數(shù)連通度的注記(英文)[J];中國科學技術大學學報;2002年01期

2 劉鳳霞;孟吉翔;;線圖和有向線圖的第二等周點連通度(英文)[J];新疆大學學報(自然科學版);2006年03期

3 雷瀾;李霄民;;關于廣義棱連通度的一個注記[J];西南師范大學學報(自然科學版);2008年03期

4 蔡華;;圖有較高連通度的一個充要條件[J];昌吉學院學報;2009年02期

5 林輝球;孟吉翔;田應智;;立方體的線圖的限制性連通度(英文)[J];新疆大學學報(自然科學版);2010年01期

6 薩如拉;阿勇嘎;;三次圖的完全擴容圖的連通度(英文)[J];寶雞文理學院學報(自然科學版);2012年01期

7 王國亮;師海忠;;完全對換網(wǎng)絡的限制連通度[J];運籌學學報;2013年03期

8 孫惠泉;線圖的連通度[J];數(shù)學年刊A輯(中文版);1986年05期

9 周永生，，林秀琴，李唐芬;環(huán)網(wǎng)的強連通度與最佳強連通性[J];計算機應用;1995年01期

10 吳強;獨立數(shù)、連通度及r－消去圖[J];山東工業(yè)大學學報;1995年02期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 吳俊;鄧宏鐘;譚躍進;;基于自然連通度的隨機網(wǎng)絡抗毀性研究[A];第五屆全國復雜網(wǎng)絡學術會議論文（摘要）匯集[C];2009年

中國博士學位論文全文數(shù)據(jù)庫 前9條

1 楊超;乘積圖的連通度和容錯直徑的研究[D];中國科學技術大學;2007年

2 李莎莎;圖的廣義連通度若干問題的研究[D];南開大學;2012年

3 田應智;圖的超連通性和限制性連通度[D];新疆大學;2012年

4 李瑋;完全多部圖的廣義連通度[D];南開大學;2012年

5 熊瑋;幾類圖參數(shù)的研究[D];新疆大學;2014年

6 洪艷梅;圖連通度與非分離子圖[D];上海大學;2012年

7 繆惠芳;圖的連通度、強定向及無線傳感器網(wǎng)絡[D];廈門大學;2008年

8 顧磊;社會網(wǎng)絡：拓撲性質與代數(shù)性質[D];上海交通大學;2011年

9 郭龍坤;基于不相交路徑技術的可靠網(wǎng)絡設計[D];中國科學技術大學;2011年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 萬敏;星圖的一種條件連通度[D];新疆大學;2008年

2 劉曉妍;2-連通[4，2]-圖中的圈與高連通度圖的完全圈可擴性[D];山東師范大學;2006年

3 劉鳳霞;一些重要圖類的條件連通度[D];新疆大學;2006年

4 雷泓昊;圖的連通度與其路圈可擴性[D];山東師范大學;2007年

5 趙雪冰;（有向）圖的鄰域連通度的研究[D];新疆大學;2012年

6 林輝球;k-正則雙軌道圖的條件連通度[D];新疆大學;2010年

7 劉振華;全圖的圈連通度[D];新疆大學;2011年

8 段晉芳;圖的等周邊連通度的最優(yōu)化[D];太原科技大學;2011年

9 管宇;樹的代數(shù)連通度[D];上海交通大學;2007年

10 王可可;一些特殊圖的群連通度[D];北京交通大學;2011年

本文編號：716139