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

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

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

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

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

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

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

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