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

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

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

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

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