用8長圈C-,8-最大填充和最小覆蓋完全二部圖K-,m，n-.pdf

1、本文主要考慮了下面兩個問題. 1.用Km,n表示具有m+n個頂點，二部集的基數(shù)為m和n的完全二部圖.D.Sotteau[1]解決了當m，n都是偶數(shù)，且m，n≥4時，完全二部圖Km,n的C2k的分解問題.DanArchdeacon等[2]解決了當n是奇數(shù)，且k≤n時，Kn,m\I的C2k的分解問題，這里I為Kn,n的1-因子.Elizabeth.J等[3]解決了當m，n是任意數(shù)時，完全二部圖Km,n的最大C4-填充問題.Lakei

2、sha Brown等[4]解決了當m，n是任意數(shù)時，完全二部圖Km,n的最大C6-填充問題.本文在上面的基礎上，完全解決了當m,n是任意數(shù)時，完全二部圖Km,n的最大C8-填充和最小C8-覆蓋的問題.根據(jù)m和n的奇偶性，主要分了下面三種情況來構(gòu)造的：(1)m，n都是偶數(shù)；(2)m，n一個是奇數(shù)一個是偶數(shù)；(3)m，n都足奇數(shù).本部分主要使用的是直接構(gòu)造的方法. 2.流量疏導是當今光網(wǎng)絡研究中的一個前沿和熱點問題，在波分復用(WD

3、M)光網(wǎng)絡中使用流量疏導技術(shù)能有效降低網(wǎng)絡的成本，減少網(wǎng)絡節(jié)點中業(yè)務信息的處理量.我們希望降低WDM光網(wǎng)絡中ADM的總數(shù).這個問題的解決依靠將完全圖的邊劃分成一些子圖，每個子圖至多包含c條邊(其中c是疏導率)，以減少所有子圖頂點的總數(shù).對于給定的疏導率c，利用圖論和設計理論已經(jīng)得到了最優(yōu)的構(gòu)造[5].特別地，對于c=1時，每個子圖都是1條邊，沒有降低成本的可能.當c=2時，每個子圖至多包含2條邊，由于Kn線圖是歐拉圖，在每個歐拉圈上用連

4、續(xù)的點可以降低成本，從而可使最低成本是[3n(n-1)/4][6].對于疏導率c=3[7]，c=4[8,9]，c=5[10]，c=6[6]，c≤n(n-1)/6[8]的環(huán)上的業(yè)務疏導問題，已經(jīng)解決.本文在上面的基礎上，研究了無向環(huán)WDM中疏導率c=8的業(yè)務疏導問題.當每對站點使用不超過波容量的1/8時，存在具有最小花費的分解已經(jīng)在本文中得到部分的結(jié)果.事實上，當n≡0，1，2，3，4，5，6，7(mod 16)，除去一些未確定的n=34