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

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

2、凡連通圖，k為一個(gè)整數(shù)，滿足2≤k≤n。對(duì)G的一個(gè)足一元子集S，用K(S)表示G中邊不交樹T1，T2，…，Te的數(shù)目e，這些樹要滿足V(T1)∩V(Tj)=S，對(duì)每對(duì)不同的整數(shù)i，j，其中1≤i，j≤e(注意到這些樹在G＼S中是頂點(diǎn)不交的)。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ù)目。
　　 本文的第一章主要介紹一些記號(hào)和定義，以及相關(guān)的結(jié)果等。
　　 在第二章中，我們?cè)O(shè)計(jì)了一種方法--列表方法，利用這利，方法我們可以方便而快捷的找到任意完全二部圖的所有邊不交生成樹。我們還計(jì)算了完全二部圖的所有廣義k-連通度并得到下面的結(jié)果：令a，b為滿足a≤b的任意兩個(gè)正整數(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é)分析和近似算法等中的一些技巧，我們計(jì)算出了等部完