圖的對稱性和容錯性分析.pdf

1、稱圖Γ是對稱圖或弧傳遞圖，如果Γ的全自同構(gòu)群作用在Γ的弧集上傳遞.對稱圖，特別是小度數(shù)對稱圖，常被用來設(shè)計互連網(wǎng)絡(luò).互連網(wǎng)絡(luò)投入使用過程中出現(xiàn)故障是不可避免的，這就要求互連網(wǎng)絡(luò)應(yīng)該具有一定的容錯性.而圖的一些定義和性質(zhì)可以用來有效的評估互連網(wǎng)絡(luò)的容錯性.本文主要研究五度對稱圖的分類和構(gòu)造，以及討論兩類基于對稱圖設(shè)計的互連網(wǎng)絡(luò)的容錯性.
　　論文結(jié)構(gòu)組織如下.
　　第1章緒論部分，主要介紹了本文所要用到的有限群論和圖論的基本概

2、念，以及與圖的對稱性和容錯性研究相關(guān)的背景知識和本文的主要研究工作.
　　第2章研究二倍素數(shù)階連通五度對稱圖的正則覆蓋.稱一個連通圖的正則覆蓋為循環(huán)覆蓋或二面體覆蓋，如果其覆蓋變換群分別是循環(huán)群或二面體群.如果保簇自同構(gòu)群作用在覆蓋圖上弧傳遞，則稱此覆蓋為弧傳遞覆蓋或?qū)ΨQ覆蓋.本章給出了二倍素數(shù)階連通五度對稱圖的弧傳遞循環(huán)覆蓋和二面體覆蓋的完全分類.所有的覆蓋圖都是以凱萊圖的形式構(gòu)造出來，而且它們的全自同構(gòu)群也被完全決定.

3、　　第3章研究小整數(shù)倍素數(shù)冪階五度對稱圖.一個連通的素數(shù)度對稱圖是Basic圖，如果其全自同構(gòu)群不包含非平凡的正規(guī)子群作用在頂點集合上有多于兩個軌道.設(shè)p是一個素數(shù).
　　首先，我們給出了2p3階連通五度對稱圖的完全分類.所有的2p3階連通五度對稱圖都是某個2p3階群上的正規(guī)凱萊圖，而且其全自同構(gòu)群也被完全決定.證明了當p=3時，不存在2p3階連通的五度對稱圖;當p=2或5時，在同構(gòu)意義下只有一個2p3階連通的五度對稱圖;當p≥7

4、時，有七個無限類圖，其中六類當且僅當5|(p-1)時存在而且為1-正則圖，另外一類當且僅當5|(p±1)時存在而且為1-傳遞非1-正則圖.
　　其次，我們給出了4pn階和6pn階連通五度Basic圖的完全分類，其中n是一個非負正整數(shù).證明了在同構(gòu)意義下，只有兩個4pn階連通五度Basic圖，階分別為16和36;有五個6pn階連通五度Basic圖，階分別為6，42，66，114和162.作為應(yīng)用，我們給出了4p2，4p3和6p2階連

5、通五度對稱圖的完全分類.4p階和6p階連通五度對稱圖在[Discrete Mathematics，2011(311):2259-2267]中已經(jīng)被分類.
　　第4章給出了無平方因子階連通五度對稱圖的一個刻畫.作為應(yīng)用，2pqr階連通五度對稱圖被完全分類，其中r＜q＜p是三個奇素數(shù).
　　第5章研究n-維超立方體網(wǎng)絡(luò)Qn和n-維平衡超立方體網(wǎng)絡(luò)BHn的容錯性分析.
　　首先，我們從容錯圈嵌入方面分析Qn的容錯性.設(shè)F是Q

6、n的一個錯誤集，fv和fe分別是F中錯誤頂點和錯誤邊的個數(shù).稱一條邊e是自由邊，如果e以及其兩個端點均不在F中.圖Γ的一個圈是無錯圈，如果它既不包含F(xiàn)中的點又不包含F(xiàn)中的邊.我們證明了當n≥3時，如果fv+fe≤2n-5，fe≤n-2且每個無錯頂點至少關(guān)聯(lián)兩條自由邊，那么Qn的每條自由邊都位于長從6到2n-2fv的無錯偶圈中.這一結(jié)論證實了Tsai在[Information Processing Letters，2007(102):24

7、2-246]中提出的一個猜想.
　　最后，我們從外連通度方面分析BHn的容錯性，其中n≥2.連通圖Γ的h-外連通度，記為κh(Γ)，是指去掉最少的頂點的個數(shù)使得Γ不連通且每個連通分支至少含有h+1個頂點.Yang在[Applied Mathematics and Computation，2012(219):970-975]中證明了κ1(BHn)=4n-4.本章，我們推廣了Yang關(guān)于BHn的外連通度的結(jié)論，證明了κ2(BHn)=κ