完全多部圖的廣義連通度.pdf

1、連通度是圖論的基本概念之一，它常被用來衡量一個通訊網(wǎng)絡(luò)的性能。一個通訊網(wǎng)絡(luò)可以自然地表示成圖的形式，而連通度就是為使這個圖不連通所需移除的元素(頂點或邊)的最小數(shù)目，因此連通度越高也就意味著這個通訊網(wǎng)絡(luò)的性能越好。連通度被眾多的數(shù)學(xué)家進(jìn)行研究。近年來，數(shù)學(xué)家們又提出了一些新的連通度概念，如彩虹連通度，廣義連通度等，從不同的側(cè)重點研究圖的連通性質(zhì)。這篇論文的主要結(jié)果就是關(guān)于廣義連通度的一些進(jìn)展。
　　 令G為一個具有n個頂點的非平

2、凡連通圖，k為一個整數(shù)，滿足2≤k≤n。對G的一個足一元子集S，用K(S)表示G中邊不交樹T1，T2，…，Te的數(shù)目e，這些樹要滿足V(T1)∩V(Tj)=S，對每對不同的整數(shù)i，j，其中1≤i，j≤e(注意到這些樹在G＼S中是頂點不交的)。G中滿足這一性質(zhì)的一族樹{T，，T2，…，Te)稱為連接S的內(nèi)部不交樹集。圖G的k-連通度，記為Kk(G)，定義為Kk(G)=min{K(S))，其中最小是取遍V(G)的所有足k-元子集S。因此，K

3、2(G)=K(G)，而Kn(G)是G的邊不交生成樹的數(shù)目。
　　 本文的第一章主要介紹一些記號和定義，以及相關(guān)的結(jié)果等。
　　 在第二章中，我們設(shè)計了一種方法--列表方法，利用這利，方法我們可以方便而快捷的找到任意完全二部圖的所有邊不交生成樹。我們還計算了完全二部圖的所有廣義k-連通度并得到下面的結(jié)果：令a，b為滿足a≤b的任意兩個正整數(shù)，如果k>b-a+2，且a-b+k是奇數(shù)，那么
　　 Kk(Ka，b)=a+

4、b-k+1/2+[(a-b+k-1)(b-a+k-1)/(4(k-1)]；如果k>b-a+2，且a-b+k是偶數(shù)，那么
　　 Kk(Ka，b)=a+b-k/2+[(a-b+k)(b-a+k)/(4(k-1)]；如果k≤b-a+2，那么
　　 Kk(Ka，b)=a
　　 在第三章中，我們將列表方法進(jìn)一步用于完全三部圖，可以找到任意完全三部圖的所有邊不交生成樹。應(yīng)用數(shù)學(xué)分析和近似算法等中的一些技巧，我們計算出了等部完