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

1、眾所周知，互連網(wǎng)絡(luò)在大規(guī)模并行分布計算系統(tǒng)中扮演著重要的角色互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)通常以圖為數(shù)學(xué)模型，其中圖的頂點表示服務(wù)器，圖的邊表示服務(wù)器間的連接.因此，圖的性質(zhì)和參數(shù)可用來度量網(wǎng)絡(luò)拓撲的性能.在設(shè)計和分析互連網(wǎng)絡(luò)時，需要考慮的一個基本問題是網(wǎng)絡(luò)的容錯性.連通度和生成樹填裝數(shù)是度量網(wǎng)絡(luò)容錯性的兩個重要參數(shù)廣義連通度是連通度和生成樹填裝數(shù)的一個共同推廣，它能夠更加精確地度量網(wǎng)絡(luò)的容錯性.
　　設(shè)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}.
　　近年來，圖的廣義連通度得到了廣泛的關(guān)注.2012年，Li Hengzhe等人證明了

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