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

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

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

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

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

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

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

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

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

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

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

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

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