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

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

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

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

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

5、數(shù)的定義參見1．3節(jié))。 對G中兩個頂點u和v，我們用u～u來表示u和u在G里相鄰。 兩個圖G<,1>和G<,2>的Kronecker乘積(同樣稱為直積或×乘積)G<,1>×G<,2>定義如下：G<,1>×G<,2>具有頂點集合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)和堅韌度t(G)主要得到了如下的結果： 1． m,n是大于或等于3的整數(shù)。那么3． m,n是大于或等于3的整數(shù)．那么第五章中討論了一個圖G的中間圖(middle graph)M(G)的完整度I(G)等可靠性參數(shù)。 對一個圖G，它的中間圖M(G)有頂點集合v(a)U E(G)，兩個頂點x和Y在M(G)里相鄰當且僅當滿足下面兩條之一：(i)z，Y c E(G)，且x和y在