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

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

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

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