圖的彩虹連通數(shù)與距離.pdf

1、一個交互網(wǎng)絡(luò)通?？梢猿橄蟪梢粋€圖，其中點代表開關(guān)元件或交換器，邊代表通信鏈路。一方面，為了防止黑客入侵，人們在每個鏈路上設(shè)置一個密碼。另一方面，為了便于管理，密碼的總數(shù)要求在滿足下面的條件下盡可能的少:任意兩個交換器可以通過一系列密碼不同的鏈路來交換信息。這個問題可以抽象成一個圖，并且通過彩虹連通數(shù)來研究。彩虹連通數(shù)是由Chartrand等人在2008引入的。
　　一個圖G=(V，E)的k-邊著色是一個映射c:E→S，其中S是一個

2、由k種顏色組成的集合，也就是說，把G的邊用k種顏色來著。通常k種顏色的集合我們?nèi)閧1，2，...，k}。圖G是一個邊著色圖，其中相鄰的邊可以著同一種顏色，如果一條路上的任意兩條邊的顏色不同，那么這條路稱為彩虹路。圖G是一個k-邊著色圖。如果圖G的任意兩個頂點之間存在一條彩虹路，那么該著色稱為k-彩虹邊著色。如果一個圖G有一個k-彩虹邊著色，那么該圖是k-彩虹邊連通的。一個圖G的彩虹連通數(shù)rc(G)是最小的整數(shù)k使得圖G有一個k-彩虹邊

3、著色。對于整數(shù)n和k，讓t(n，k)表示n個頂點k-彩虹連通圖的最小邊數(shù)。
　　本論文共分七章。第一章，我們首先引入彩虹連通數(shù)的定義和研究背景。然后我們縱覽一下本文的主要結(jié)果。
　　由于直徑是彩虹連通數(shù)的一個自然的下界，我們主要研究彩虹連通數(shù)與直徑（半徑)的關(guān)系。顯然，對一個圖來說，它的彩虹著色必然要求橋都著不同的顏色，這種情況比較平凡，在本論文中，我們主要考慮無橋圖。一個圖的直徑和半徑有下面關(guān)系:rad(G)≤diam(G

4、)≤2rad(G)。在第二章，我們研究彩虹連通數(shù)與半徑的關(guān)系，證明對任意的無橋圖G，rc(G)≤Σrad(G)i=1 min{2i+1，η(G)}≤rad(G)η(G)，其中η(G)是最小的整數(shù)使得圖G的每條邊包含在長度不超過η(G)圈中。
　　在第二章我們研究了彩虹連通數(shù)與半徑的關(guān)系。不像半徑，研究彩虹連通數(shù)與直徑的關(guān)系是比較困難的。不過好的方面是，幾乎所有的圖的直徑都是2。在第三章和第四章，我們將研究小直徑圖的彩虹連通數(shù)，從而

5、得到下面的結(jié)果:對直徑為2的無橋圖G，rc(G)≤5;對直徑為3的無橋圖G，rc(G)≤9。
　　超立方體和遞歸循環(huán)圖是兩個過去幾十年被很多學(xué)者研究過的網(wǎng)絡(luò)。由于他們都是阿貝爾群上的凱萊圖。第五章，我們利用阿貝爾群的交換性來研究阿貝爾群上的凱萊圖的彩虹連通數(shù)，證明:對任意的阿貝爾群Γ和Γ的逆閉生成集S(∈)Γ\{1}，(f)rc(C(Γ，S))≤min{∑a∈S*「|a|/2」|S*(∈)S/ΓΓ*ffl(φ)1}。(ii)如果S

6、是Γ的一個極逆閉小生成集，那么∑a∈S*「|a|/2」≤rc(C(Γ，S))≤src(C(Γ，S))≤∑a∈S*「|a|/2」，其中S*∈S是Γ的一個極小生成集。進一步，如果每個a∈S的階數(shù)是偶數(shù)，那么rc(C(Γ，S))=src(C(Γ，S))=∑a∈S*|a|/2.
　　第六章，我們研究極小k-彩虹連通圖，證明(i)對充分大的n，t(n，2)≥nlog2n-4nlog2log2n-2n;(ii)對于3≤k＜「n/2」，n-k-