【摘要】：圖論是現(xiàn)代應(yīng)用數(shù)學(xué)的一個重要分支,其研究對象通常是一張圖G(V,E),這里V是圖的頂點(diǎn)集合,E是圖的邊集合。經(jīng)過一百多年的發(fā)展[17],圖論已經(jīng)演化為一個擁有眾多分支領(lǐng)域諸如染色理論,拉姆齊理論,網(wǎng)絡(luò)理論等的龐大家族。一方面,從純粹基礎(chǔ)理論研究的角度,推動圖論不斷發(fā)展的是其理論領(lǐng)域本身的內(nèi)部矛盾。例如四色猜想就是最為重要的理論推動力之一。在攻克四色猜想的過程中,不斷涌現(xiàn)出的新方法和新問題使得圖的染色理論逐漸發(fā)展為圖論中主要的研究領(lǐng)域之一。而四色猜想問題本身最終于1976年被K.Appel和W.Haken借助電子計(jì)算機(jī)所證明。另一方面,由于圖本身所具有普適性,使得其被廣泛的應(yīng)用于表示和描述很多復(fù)雜的現(xiàn)實(shí)問題。因而很多由實(shí)際應(yīng)用如通信網(wǎng)絡(luò)中所產(chǎn)生的問題是推動圖論不斷發(fā)展的另一重要源泉。本論文分別從圖論的理論和實(shí)際這兩個角度出發(fā),著重研究了染色理論中的Steinberg猜想和在實(shí)際的彈性光網(wǎng)絡(luò)EON以及網(wǎng)絡(luò)虛擬化中算法的設(shè)計(jì)與分析。在第一章中,我們首先介紹了Steinberg猜想及其發(fā)展現(xiàn)狀,以及關(guān)于彈性光網(wǎng)絡(luò)EON和網(wǎng)絡(luò)虛擬化的相關(guān)背景。從理論方面,在第二章中,我們證明了平面圖不含四圈和六圈是7/2可染的,這一結(jié)論說明了所有不含四圈和六圈的平面圖的分?jǐn)?shù)色數(shù)的上界不超過7/2。這一結(jié)論和Steinberg猜想有較為緊密的聯(lián)系。在四色猜想被攻克以后,Richard Steinberg于1976年提出了如下猜想:Steinberg猜想:所有不含四圈和五圈的平面圖是三色可染的。在16年之后,為了逼近這一猜想,Paul Erdos于1991年提出了對這一猜想的如下松弛:即確定這樣的k的最小值(如果存在的話)使得所有不含4,5,…,k圈的平面圖是三色可染的[32]。在2005年,Borodin等人證明了k≤7[92]。在2017年,V.Addad,M.Hebdige,D.Kral,Z.Li和E.Salgado 否定了Steinberg 猜想[93],即k5。因此,Erdos所提出的最小的k值是否等于6是最后沒有確定的臨界值。我們的結(jié)論對k=6成立提供了支持。在實(shí)際應(yīng)用方面,隨著萬物互聯(lián)時(shí)代的到來,世界范圍內(nèi)的通訊需求和多樣化的實(shí)際應(yīng)用需求呈現(xiàn)井噴式的發(fā)展。這場信息革命要求未來的通訊網(wǎng)絡(luò)更加高效,智能,敏捷和可擴(kuò)展。為了滿足下一代通信網(wǎng)絡(luò)的趨勢,許多新興的網(wǎng)絡(luò)架構(gòu)和網(wǎng)絡(luò)技術(shù)例如彈性光網(wǎng)絡(luò)EON和網(wǎng)絡(luò)虛擬化已經(jīng)不斷的涌現(xiàn)。彈性光網(wǎng)絡(luò)EON,由于其在光譜上的靈活性,被視為下一代光網(wǎng)絡(luò)的標(biāo)準(zhǔn)架構(gòu)。網(wǎng)絡(luò)虛擬化則被視為克服目前互聯(lián)網(wǎng)僵化問題的最為有前景的網(wǎng)絡(luò)技術(shù)。伴隨著這些新架構(gòu)和技術(shù)而來的是很多亟待解決的新興的圖論問題,例如彈性光網(wǎng)絡(luò)EON中的路由和頻譜分配的RSA問題以及網(wǎng)絡(luò)虛擬化中的虛擬網(wǎng)絡(luò)嵌入的VNE問題。在第三章中,我們研究了彈性光網(wǎng)絡(luò)EON中的路由問題。在這一問題的研究上,一直存在一個令人困惑的問題:那就是通信請求的分布和底層EON拓?fù)浣Y(jié)構(gòu)的變化是如何影響路由算法的。因?yàn)槁酚蓡栴}在整個RSA中起著決定性的作用,我們對分布和底層拓?fù)鋵τ诼酚蓡栴}的影響進(jìn)行了詳細(xì)的理論分析。在研究過程中,我們提出了兩條關(guān)鍵的理論作用鏈:(1)在EON中,路由算法的最優(yōu)性是由其相應(yīng)的沖突圖的色數(shù)所決定,而沖突圖的色數(shù)又與任意兩條光路(由路由算法所決定)的相交概率成正比;(2)通信請求的分布和底層EON拓?fù)涞挠绊懣梢员灰粋�由沖突系數(shù)所構(gòu)成的沖突矩陣所刻畫。而基于沖突矩陣,任意兩條光路的相交概率可以被一個二次型規(guī)劃所決定。結(jié)合這兩條理論鏈,我們刻畫了通信請求分布和底層EON拓?fù)浣Y(jié)構(gòu)對路由算法的影響,并且給出了最優(yōu)的路由決策和相關(guān)的近似算法。實(shí)際的數(shù)值仿真結(jié)果驗(yàn)證了我們所提出的理論鏈的有效性。在第四章中,我們對RSA中的頻譜分配問題進(jìn)行了研究。在路由階段結(jié)束之后(所有的通信請求都已設(shè)定在其相應(yīng)的光路上),任意兩條光路之間如果經(jīng)過了一條或多條相同的底層光纖,則為了減少相應(yīng)的信號干擾以及保證通信的質(zhì)量和安全,分配給他們的信號頻譜應(yīng)當(dāng)在光譜上被一定的警戒帶寬所隔離。而警戒帶寬大小的設(shè)定則由任意兩條光路的具體的干擾情況所決定。因此不同光路之間的警戒帶寬的大小應(yīng)當(dāng)是根據(jù)實(shí)際情況而變化的。但目前相關(guān)的研究均把所有的警戒帶寬設(shè)定為一致的大小,從而造成了巨大的頻譜浪費(fèi)。針對這種情況,本論文對提出了一種距離頻譜分配的的DSA模型來對在警戒帶寬大小變化的情況下的頻譜分配進(jìn)行研究。我們首先證明了 DSA問題是NP困難的,并對其的不可近似性進(jìn)行了刻畫。之后,通過與沖突圖的色數(shù)和哈密頓路問題建立聯(lián)系,我們給出的DSA的最優(yōu)解的緊的理論上界和下界。為了高效的解決DSA問題,我們進(jìn)一步提出了一個二階段算法。算法的第一階段產(chǎn)生一個DSA問題的初解,并且我們證明了該初解在一些圖類中能達(dá)到最優(yōu)解或保證一定的近似比。之后,算法的第二階段采用一個隨機(jī)劃分算法對初解的結(jié)果進(jìn)行了進(jìn)一步的提升和改進(jìn)。實(shí)際的數(shù)值結(jié)果證明了我們所提出的算法能得到較好的次優(yōu)解,并且具有快速的運(yùn)算時(shí)間和良好的可擴(kuò)展性。虛擬網(wǎng)絡(luò)嵌入的VNE問題是網(wǎng)絡(luò)虛擬化中的最核心且具有挑戰(zhàn)性的問題,其主要的任務(wù)是將一些虛擬請求的網(wǎng)絡(luò)嵌入到一個共享的底層網(wǎng)絡(luò)中去。VNE問題是一個NP困難的問題,其中虛擬網(wǎng)絡(luò)的拓?fù)涠鄻有允窃斐善潆y以較好的被解決的主要原因之一。但在實(shí)際的應(yīng)用中,很多的虛擬請求網(wǎng)絡(luò)都具有一些共同的拓?fù)浣Y(jié)構(gòu)特征,例如都是路和圈。為了取得更好的實(shí)際效果,設(shè)計(jì)出針對這些特殊結(jié)構(gòu)的虛擬請求網(wǎng)絡(luò)的專有算法是提升效能的關(guān)鍵。此外,路和圈是最為基礎(chǔ)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也是構(gòu)成所有復(fù)雜結(jié)構(gòu)的基石,因此針對路和圈的結(jié)構(gòu)的VNE問題的研究對一般結(jié)構(gòu)的VNE問題起到至關(guān)重要的作用。在第五章中,我們對路和圈的VNE問題進(jìn)行研究。對于路的VNE問題,在一個簡化的情況下,我們證明了它下仍然是NP困難的,并且借助歐拉環(huán)游設(shè)計(jì)了相應(yīng)的近似算法。在真實(shí)情況下,我們證明了它的不可近似性,并且設(shè)計(jì)了一個高效的基于多背包問題和多維背包問題的啟發(fā)式算法。對于圈的VNE問題,我們構(gòu)造了一個賦權(quán)有向輔助圖,并在此基礎(chǔ)上設(shè)計(jì)了一個多項(xiàng)式時(shí)間的圈到圈VNE的最優(yōu)嵌入算法。與一般的VNE算法相比,實(shí)際的數(shù)值結(jié)果證明了我們所提出的算法能提高路和圈VNE的實(shí)際接受率和收益。
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2018
【分類號】：O157.5
，

本文編號：2594400