類超立方體網(wǎng)絡的廣義連通度.pdf

1、眾所周知，互連網(wǎng)絡在大規(guī)模并行分布計算系統(tǒng)中扮演著重要的角色互連網(wǎng)絡的拓撲結構通常以圖為數(shù)學模型，其中圖的頂點表示服務器，圖的邊表示服務器間的連接.因此，圖的性質(zhì)和參數(shù)可用來度量網(wǎng)絡拓撲的性能.在設計和分析互連網(wǎng)絡時，需要考慮的一個基本問題是網(wǎng)絡的容錯性.連通度和生成樹填裝數(shù)是度量網(wǎng)絡容錯性的兩個重要參數(shù)廣義連通度是連通度和生成樹填裝數(shù)的一個共同推廣，它能夠更加精確地度量網(wǎng)絡的容錯性.
　　設G是一個包含n個頂點的連通圖，k是滿足

2、2≤k≤n的整數(shù).對由G的k個頂點組成的集合S，稱G中的一棵樹T為一棵S-樹，若S(∈)V(T).稱兩棵S-樹T，T'是內(nèi)部不相交的，若V(T)∩V(T')=S且E(T)∩E(T')=(Φ).令κ(S)表示G中內(nèi)部不相交的S-樹T1，T2，…，Tr的最大數(shù)目r.定義G的廣義k-連通度κk(G)=min{κ(S):S(∈)V(G)，|S|=k}.
　　近年來，圖的廣義連通度得到了廣泛的關注.2012年，Li Hengzhe等人證明了

3、n維超立方體Qn的廣義3-連通度為n-1.本文給出了超立方體Qn的廣義4-連通度，并證明Li Hengzhe等人的結果為該結果的一個直接推論另外，本文也確定了k元n方體Qkn的廣義3-連通度.
　　本文共分為三章.
　　第一章首先介紹了本文將用到的一些圖論基本概念和符號，然后綜述了廣義連通度和超立方體的應用背景和研究現(xiàn)狀
　　第二章，介紹了超立方體Qn的定義和相關性質(zhì)，探討了超立方體的廣義4-連通度，并得到了下述結論: