網(wǎng)絡(luò)中的超圖嵌入問(wèn)題.pdf

1、在全光網(wǎng)絡(luò)中，波分復(fù)用(Wavelength Division Multiplexing)網(wǎng)絡(luò)技術(shù)在現(xiàn)實(shí)的通信世界中扮演著基礎(chǔ)和決定性的角色． 若把網(wǎng)絡(luò)看作一個(gè)圖的模型，對(duì)于網(wǎng)絡(luò)中的每一個(gè)通訊請(qǐng)求，如果每一個(gè)通訊請(qǐng)求恰好只有網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)組成(一個(gè)源信號(hào)節(jié)點(diǎn)和一個(gè)接收信號(hào)節(jié)點(diǎn))，那么在圖模型中需要選擇一條路當(dāng)作它的通訊頻道來(lái)滿足其通訊請(qǐng)求．而對(duì)于所有此類通訊請(qǐng)求，需要在圖模型中選定一系列通路來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)中的通訊請(qǐng)求，這些通路就組

2、成了這組通訊請(qǐng)求的一個(gè)路由． 通常在實(shí)際的通訊網(wǎng)絡(luò)中一個(gè)通訊請(qǐng)求含有網(wǎng)絡(luò)中兩個(gè)以上的節(jié)點(diǎn)，所以這種更普遍的情況是將這一系列通訊請(qǐng)求看作是圖(或網(wǎng)絡(luò))中的一個(gè)超圖，而其中每個(gè)通訊請(qǐng)求看作是此超圖中的一條超邊．為了實(shí)現(xiàn)這種通訊請(qǐng)求，對(duì)超圖中每條超邊需要確定一個(gè)路由算法來(lái)建立圖(或網(wǎng)絡(luò))中一條虛擬通路或者說(shuō)專用通路來(lái)連接此超邊的每個(gè)節(jié)點(diǎn)，在確定這樣一個(gè)路由算法中最重要的一點(diǎn)是使得圖中的每條邊上的最大阻塞度(congestion)最小，

3、其中阻塞度為任意一條邊上通過(guò)的通路的數(shù)量，此問(wèn)題稱作路由和波長(zhǎng)(BLWA)分配問(wèn)題． 如果將網(wǎng)絡(luò)限定在一個(gè)環(huán)網(wǎng)絡(luò)中，問(wèn)題變?yōu)榇_定一個(gè)路由算法來(lái)實(shí)現(xiàn)超圖在此環(huán)中的通訊請(qǐng)求，并且使得此環(huán)中任意一邊上的最大阻塞度最?。藛?wèn)題稱作最小化超圖嵌入圈的最大阻塞度(MCHEC)問(wèn)題．此問(wèn)題的結(jié)果在實(shí)際生活中應(yīng)用廣泛，例如在并行計(jì)算問(wèn)題中，并行計(jì)算機(jī)的處理器可以代表是超圖的所有頂點(diǎn)，其中需要互相傳遞信息的各組處理器看作是一條超邊，MCHEC問(wèn)題

4、的最優(yōu)解對(duì)每一組內(nèi)所有處理器之間的通訊確定了一個(gè)路由算法使得計(jì)算機(jī)之間的最大阻塞度最?。?本論文主要研究來(lái)源于WDM網(wǎng)絡(luò)帶寬分配問(wèn)題的幾個(gè)超圖嵌入問(wèn)題，對(duì)兩類有較深應(yīng)用價(jià)值的網(wǎng)絡(luò)結(jié)構(gòu)：樹環(huán)網(wǎng)絡(luò)和環(huán)圈網(wǎng)絡(luò)，考慮了其超圖嵌入問(wèn)題；而后討論了有關(guān)加權(quán)有向超圖在網(wǎng)絡(luò)中的嵌入問(wèn)題，以及圖論中有向圖的幾個(gè)問(wèn)題，共分為五章．第一章主要介紹了WDM網(wǎng)絡(luò)的一些相關(guān)的最優(yōu)化問(wèn)題，關(guān)鍵定義和相關(guān)結(jié)論，以及一些有向圖問(wèn)題的來(lái)源和相關(guān)結(jié)論． 在第

5、二章我們簡(jiǎn)化了MCHEC問(wèn)題的算法，用新的方法證明了幾個(gè)關(guān)鍵引理并且分別給出MCHETR(超圖嵌入樹環(huán))問(wèn)題和MCHERC(超圖嵌入環(huán)圈)問(wèn)題的PTAS算法． Ganley和Cohoon提出了MCHEC問(wèn)題并且證明了此問(wèn)題為NP-完備的． 定理1[51]MCHEC問(wèn)題為NP-完備的． MCHEC問(wèn)題存在一個(gè)PTAS算法[20]．在算法進(jìn)行過(guò)程中我們將超邊分為兩部分來(lái)嵌入：R<,i1,i2，..ik>和U<,i1,

6、i2，..ik>對(duì)不同的U=｜U<,i1,i2，..ik>｜超邊的嵌入又分兩種情況來(lái)討論． 當(dāng)超邊的數(shù)目為一個(gè)小數(shù)目時(shí)，利用窮舉的方法易證MCHEC問(wèn)題的PTAS算法是存在的． 定理2[20]對(duì)任意的常數(shù)C>O，當(dāng)超邊的數(shù)目u≤C(log n)時(shí)，U<,i1,i2，..ik>中的超邊嵌入到圈中存在一個(gè)PTAS算法．特別地，對(duì)任-ε>0，一個(gè)(1+ε)近似比的近似結(jié)果可以在O(n<'(C+1)>/ε>)時(shí)間內(nèi)找到．

7、 應(yīng)用線性放松和反隨機(jī)方法來(lái)近似的解決超邊為大數(shù)目時(shí)的MCHEC問(wèn)題．可得如下定理． 定理4[20]當(dāng)超邊數(shù)目m足夠大，且Copt≥cm(0

8、(超圖嵌入環(huán)圈)問(wèn)題．應(yīng)用MCHEC問(wèn)題的算法，可以得出這兩個(gè)相關(guān)問(wèn)題的PTAS證明．從而可得如下定理． 定理6 MCHETR問(wèn)題存在一個(gè)PTAS算法． 定理8 MCHERC問(wèn)題存在一個(gè)PTAS算法． 應(yīng)用定理1的結(jié)論我們可以得到上述兩個(gè)問(wèn)題的NP-完備性證明． 定理7 MCHETR問(wèn)題為NP-完備的． 定理9 MCHERC問(wèn)題為NP完備的． 在第三章我們首次提出了加權(quán)有向超圖嵌入圈(WD

9、HEC)問(wèn)題．此問(wèn)題是MCHEC問(wèn)題的加權(quán)有向版本，類似于MCHEC問(wèn)題的定義，WDHEC問(wèn)題將一個(gè)加權(quán)有向超圖的每條超邊以一條加權(quán)有向路的形式嵌入到一個(gè)強(qiáng)連通有向圈中，并且使得最大阻塞度(圈中的任一弧上經(jīng)過(guò)的加權(quán)有向路的權(quán)重之和)最?。?WDHEC問(wèn)題可以表達(dá)為一個(gè)整數(shù)線性規(guī)劃的形式．然后結(jié)合PARTITION問(wèn)題的判定問(wèn)題和僅含有兩個(gè)頂點(diǎn)的WDHEC問(wèn)題的判定問(wèn)題在多項(xiàng)式時(shí)間內(nèi)的轉(zhuǎn)換我們可以證明WDHEC問(wèn)題的NP-完備性．

10、 定理10即使圈中僅含有兩個(gè)頂點(diǎn)， WDHEC問(wèn)題依然為人Np-完備的． 通過(guò)一個(gè)簡(jiǎn)單的貪婪算法我們可以在線性時(shí)間內(nèi)得到WDHEC問(wèn)題的一個(gè)近似比為2的近似解． 定理11由貪婪算法得到的‘WDHEC問(wèn)題最大阻塞度的近似值不超過(guò)最優(yōu)解阻塞度的兩倍． 第四章主要介紹了強(qiáng)競(jìng)賽圖的定義及相關(guān)性質(zhì)，利用這些性質(zhì)我們得到強(qiáng)競(jìng)賽圖的一個(gè)新的強(qiáng)連通性質(zhì)(見如下定理)． 定理13在強(qiáng)競(jìng)賽圖T中，如果頂點(diǎn)數(shù)不少于4個(gè)

11、，則在T中存在兩個(gè)不同的頂點(diǎn){x，y}，使得T-x和T-y均為強(qiáng)競(jìng)賽圖． 通過(guò)此性質(zhì)我們可以得到Moon定理一個(gè)簡(jiǎn)潔的證明． Moon定理．[64]T是有n個(gè)頂點(diǎn)的強(qiáng)競(jìng)賽圖， n≥3．u是T中的任意一個(gè)頂點(diǎn)，則對(duì)于任意的f∈{3，4，…，n)，在T中存在一個(gè)包含u的k-圈．在第五章介紹了無(wú)向圖的定向問(wèn)題．很多人對(duì)于競(jìng)賽圖和n部圖的定向問(wèn)題進(jìn)行研究并且得到了一些有用的性質(zhì)．利用這些性質(zhì)我們提出了一類特殊圖-split完全圖

12、的最小直徑定向問(wèn)題．一個(gè)split完全圖S(m，n)由一個(gè)團(tuán)和一個(gè)獨(dú)立集構(gòu)成，且團(tuán)和獨(dú)立集之間的邊為完全的．令m，n分別為split完全圖中團(tuán)與獨(dú)立集的頂點(diǎn)個(gè)數(shù)，f(s(m，n))表示S(m，n)所有定向中能夠得到的最小直徑．我們得到split完本論文的創(chuàng)新點(diǎn)在于： 1．用區(qū)別于鄧和李的方法證明了MCHEC問(wèn)題PTAS算法的幾個(gè)關(guān)鍵引理，且首次提出超圖嵌入環(huán)圈問(wèn)題和超圖嵌入環(huán)圈問(wèn)題，并給出了這兩個(gè)問(wèn)題的NP-完備性證明和PTAS