網(wǎng)絡(luò)中的超圖嵌入問(wèn)題.pdf_第1頁(yè)
已閱讀1頁(yè),還剩74頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論