本文關(guān)鍵詞：圖的對(duì)稱性和容錯(cuò)性分析

  更多相關(guān)文章： 對(duì)稱圖 正則覆蓋 Basic圖 圈嵌入 外連通度

【摘要】：稱圖Γ是對(duì)稱圖或弧傳遞圖,如果r的全自同構(gòu)群作用在r的弧集上傳遞.對(duì)稱圖,特別是小度數(shù)對(duì)稱圖,常被用來設(shè)計(jì)互連網(wǎng)絡(luò).互連網(wǎng)絡(luò)投入使用過程中出現(xiàn)故障是不可避免的,這就要求互連網(wǎng)絡(luò)應(yīng)該具有一定的容錯(cuò)性.而圖的一些定義和性質(zhì)可以用來有效的評(píng)估互連網(wǎng)絡(luò)的容錯(cuò)性.本文主要研究五度對(duì)稱圖的分類和構(gòu)造,以及討論兩類基于對(duì)稱圖設(shè)計(jì)的互連網(wǎng)絡(luò)的容錯(cuò)性.論文結(jié)構(gòu)組織如下.第1章緒論部分,主要介紹了本文所要用到的有限群論和圖論的基本概念,以及與圖的對(duì)稱性和容錯(cuò)性研究相關(guān)的背景知識(shí)和本文的主要研究工作.第2章研究二倍素?cái)?shù)階連通五度對(duì)稱圖的正則覆蓋.稱一個(gè)連通圖的正則覆蓋為循環(huán)覆蓋或二面體覆蓋,如果其覆蓋變換群分別是循環(huán)群或二面體群.如果保簇自同構(gòu)群作用在覆蓋圖上弧傳遞,則稱此覆蓋為弧傳遞覆蓋或?qū)ΨQ覆蓋.本章給出了二倍素?cái)?shù)階連通五度對(duì)稱圖的弧傳遞循環(huán)覆蓋和二面體覆蓋的完全分類.所有的覆蓋圖都是以凱萊圖的形式構(gòu)造出來,而且它們的全自同構(gòu)群也被完全決定.第3章研究小整數(shù)倍素?cái)?shù)冪階五度對(duì)稱圖.一個(gè)連通的素?cái)?shù)度對(duì)稱圖是Basic圖,如果其全自同構(gòu)群不包含非平凡的正規(guī)子群作用在頂點(diǎn)集合上有多于兩個(gè)軌道.設(shè)p是一個(gè)素?cái)?shù).首先,我們給出了2p3階連通五度對(duì)稱圖的完全分類.所有的2p3階連通五度對(duì)稱圖都是某個(gè)2p3階群上的正規(guī)凱萊圖,而且其全自同構(gòu)群也被完全決定.證明了當(dāng)p=3時(shí),不存在2p3階連通的五度對(duì)稱圖；當(dāng)p=2或5時(shí),在同構(gòu)意義下只有一個(gè)2p3階連通的五度對(duì)稱圖；當(dāng)p≥7時(shí),有七個(gè)無限類圖,其中六類當(dāng)且僅當(dāng)5 |(p-1)時(shí)存在而且為1-正則圖,另外一類當(dāng)且僅當(dāng)5 |(p士1)時(shí)存在而且為1-傳遞非1-正則圖.其次,我們給出了4pn階和6pn階連通五度Basic圖的完全分類,其中n是一個(gè)非負(fù)正整數(shù).證明了在同構(gòu)意義下,只有兩個(gè)4pn階連通五度Basic圖,階分別為16和36；有五個(gè)6pn階連通五度Basic圖,階分別為6,42,66,114和162.作為應(yīng)用,我們給出了4p2,4p3和6p2階連通五度對(duì)稱圖的完全分類.4p階和6p階連通五度對(duì)稱圖在[Discrete Mathematics,2011 (311):2259-2267]中已經(jīng)被分類.第4章給出了無平方因子階連通五度對(duì)稱圖的一個(gè)刻畫.作為應(yīng)用,2pqr階連通五度對(duì)稱圖被完全分類,其中rqp是三個(gè)奇素?cái)?shù).第5章研究n-維超立方體網(wǎng)絡(luò)Qn和n-維平衡超立方體網(wǎng)絡(luò)BHn的容錯(cuò)性分析.首先,我們從容錯(cuò)圈嵌入方面分析Qn的容錯(cuò)性.設(shè)F是Qn的一個(gè)錯(cuò)誤集,fv,和fe分別是F中錯(cuò)誤頂點(diǎn)和錯(cuò)誤邊的個(gè)數(shù).稱一條邊e是自由邊,如果e以及其兩個(gè)端點(diǎn)均不在F中.圖Γ的一個(gè)圈是無錯(cuò)圈,如果它既不包含F(xiàn)中的點(diǎn)又不包含F(xiàn)中的邊.我們證明了當(dāng)n≥3時(shí),如果fv+fe≤2n-5,fe≤n-2且每個(gè)無錯(cuò)頂點(diǎn)至少關(guān)聯(lián)兩條自由邊,那么Qn的每條自由邊都位于長(zhǎng)從6到2n -2fv的無錯(cuò)偶圈中.這一結(jié)論證實(shí)了Tsai在[Information Processing Letters,2007(102):242-246]中提出的一個(gè)猜想.最后,我們從外連通度方面分析BHn的容錯(cuò)性,其中n≥2.連通圖Γ的h-外、連通度,記為Kh(Γ),是指去掉最少的頂點(diǎn)的個(gè)數(shù)使得Γ不連通且每個(gè)連通分支至少含有h+1個(gè)頂點(diǎn)Yang在[Applied Mathematics and Computation,2012(219):970-975]中證明了K1(BHn)=4n-4.本章,我們推廣了Yang關(guān)于BHn的外連通度的結(jié)論,證明了κ2(BHn)=κ3(BHn)=4n-4,κ4(BHn)=κ5(BHn)=6n-8,以及給出了κh(BHn)的一個(gè)上界,其中h≤2n-1.第6章討論一些有待研究的問題.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5
，

本文編號(hào)：1269777