圖中的圈和網(wǎng)絡(luò)可靠性參數(shù).pdf

1、本文分別對(duì)一些圖類的泛圈性質(zhì)，最長(zhǎng)圈，和可靠性參數(shù)進(jìn)行了研究。 全文分為三部分，分別介紹了有關(guān)圖的泛圈性質(zhì)，最長(zhǎng)圈和網(wǎng)絡(luò)可靠性參數(shù)的一些研究結(jié)果。 第一部分只含第一章。給出了與后兩部分中要討論的問(wèn)題有關(guān)的概念，背景知識(shí)和相關(guān)的已知結(jié)果。 第二部分包含第二章和第三章。主要研究了圖的圈性質(zhì)。在第二章中，給出了泛圈圖的有關(guān)定義及概念并介紹泛圈圖的研究背景。對(duì)組合設(shè)計(jì)BIBD(u，κ，λ)的區(qū)組圖G<,D>的研究，到目前

2、為止，除了Horák和Rosa的最初的研究以外，只對(duì)入=1的情況做了研究。在這一部分中對(duì)λ≥1的情況進(jìn)行了研究，得到了組合設(shè)計(jì)BIBD(u，κ，λ)的區(qū)組圖具有泛圈性質(zhì)(有關(guān)區(qū)組圖的概念參見1.1節(jié))。1998年Ainouche引進(jìn)了擬無(wú)爪圖的概念以后，很多有關(guān)一般圖和無(wú)爪圖的Hamilton性和最長(zhǎng)圈的結(jié)果被推廣到擬無(wú)爪圖。在第三章中，對(duì)2-連通無(wú)爪圖的最長(zhǎng)圈的結(jié)果推廣到擬無(wú)爪圖，證明了2-連通擬無(wú)爪圖G 的周長(zhǎng)c(G)≥min{3δ

3、＋2，n)而且，若n≤4δ，那么G是Hamilton圖，其中是2-連通非Hamilton圖類(有關(guān)擬無(wú)爪圖的概念參見1．2節(jié))。 第三部分由三章組成。主要研究了圖的一些可靠性參數(shù)。如果采用一個(gè)圖G來(lái)表示一個(gè)通訊網(wǎng)絡(luò)模型，那么可以用圖的很多可靠性參數(shù)來(lái)估計(jì)網(wǎng)絡(luò)的可靠性。對(duì)于有相同點(diǎn)數(shù)，相同連通度的兩個(gè)不同的圖，在去掉某些頂點(diǎn)或邊以后所產(chǎn)生的最大分支所含的頂點(diǎn)個(gè)數(shù)可能就不同。這意味著在對(duì)應(yīng)的通訊網(wǎng)絡(luò)中，某種損失以后仍然能夠進(jìn)行互相通

4、訊的最大群體所含的點(diǎn)數(shù)也就不同。但是，圖的連通度不能反映這種現(xiàn)象。因此研究圖的離散度，堅(jiān)韌度，完整度等能夠反映網(wǎng)絡(luò)可靠性的參數(shù)是非常有必要的(有關(guān)離散度，堅(jiān)韌度，完整度等參數(shù)的定義參見1.3節(jié))。對(duì)于一般圖來(lái)說(shuō)，確定這些可靠性參數(shù)的問(wèn)題是NP-完備的。所以，主要研究了一些特殊圖類的可靠性參數(shù)。 分別用α，β，σ,κ和δ來(lái)表示圖的獨(dú)立數(shù)，覆蓋數(shù)，控制數(shù)，連通度和最小度，并且用ε(G)和v(G)來(lái)分別表示圖G的邊數(shù)和點(diǎn)數(shù)(有關(guān)這些參

5、數(shù)的定義參見1．3節(jié))。 對(duì)G中兩個(gè)頂點(diǎn)u和v，我們用u～u來(lái)表示u和u在G里相鄰。 兩個(gè)圖G<,1>和G<,2>的Kronecker乘積(同樣稱為直積或×乘積)G<,1>×G<,2>定義如下：G<,1>×G<,2>具有頂點(diǎn)集合V(G<,1>)×V(G<,2>)，邊集E(G<,1> ×G<,2>)={(u<,1>，u<,1>)(u<,2>，u<,2>)：U<,1>U<,2>∈E(G<,1>)和u<,1>V<,2>∈E(G

6、<,2>)}第四章中我們討論了一些圖類的離散度s(G)和堅(jiān)韌度t(G)主要得到了如下的結(jié)果： 1． m,n是大于或等于3的整數(shù)。那么3． m,n是大于或等于3的整數(shù)．那么第五章中討論了一個(gè)圖G的中間圖(middle graph)M(G)的完整度I(G)等可靠性參數(shù)。 對(duì)一個(gè)圖G，它的中間圖M(G)有頂點(diǎn)集合v(a)U E(G)，兩個(gè)頂點(diǎn)x和Y在M(G)里相鄰當(dāng)且僅當(dāng)滿足下面兩條之一：(i)z，Y c E(G)，且x和y在