關(guān)于輪圖的猜測數(shù)畢業(yè)論文-預(yù)覽頁
【正文】 息傳輸指明了一個新的研究方向。在多播通信網(wǎng)絡(luò)中，通過網(wǎng)絡(luò)編碼可使信息傳播速率達(dá)到最大值。在傳統(tǒng)的通信網(wǎng)絡(luò)中，信息傳輸采用路由的機(jī)制，每個中間節(jié)點(diǎn)將收到的信息傳給與它相鄰的下一個節(jié)點(diǎn)。他們以著名的蝴蝶網(wǎng)絡(luò)(Butterfly Network) 為例闡述了網(wǎng)絡(luò)編碼的基本原理。同年在論文“Graph Entropy, Network Coding and Guessing games” [5]中， 借用信息論中熵的概念研究了圖的猜測數(shù)問題。第一是定義任意有向圖的猜測圖，并且證明任意有向圖的猜測數(shù)等于其猜測圖的獨(dú)立數(shù)的對數(shù)。同時， 和 在這篇論文中提出了奇圈的猜測數(shù)問題，即和 等尚未解決的問題。二．猜測數(shù)問題的簡介（一）猜測數(shù)問題的提出先考慮一個合作游戲(A game of cooperation)，其規(guī)則如下：個人擲 面骰子(其中每一面的點(diǎn)數(shù)分別為 )，然后把自己的值ns 0,給別人觀看。令每個人都相信所有人的值之和被 整除，此時所有人都可以計算出自己的s值。對于兩個節(jié)點(diǎn) ，假設(shè)??012.,Ss???2,34.,s?,vwV?當(dāng) 時 知道 的值，否則 不知道 的值。nV?易知，猜測策略的總數(shù)為 。if顯然有，()??g(,),lGss?下面證明上述最優(yōu)策略為在合作游戲中所有人猜對的概率最大的策略。g,n?我們?nèi)∪缦虏呗?，其中01(,.):Znssff???=ZsS ()0101(,.,.,)(..)iiniinfcccc?????(01)i??則 ????01):nFx???從而 ，即得 。??,S在這一節(jié)中，我們主要考慮源節(jié)點(diǎn)和匯節(jié)點(diǎn)數(shù)相同的網(wǎng)絡(luò)組播問題。1NnodesG? Nnodes N證明：考慮有向圖 (,)NVE?設(shè)網(wǎng)絡(luò) 的源節(jié)點(diǎn)和匯節(jié)點(diǎn)分別記為 和12,.ni12,.no由于網(wǎng)絡(luò) 中無圈，所以可以對中間節(jié)點(diǎn)定義偏序，記為N()121212...nmniino???下面考慮網(wǎng)絡(luò) 的任意網(wǎng)絡(luò)編碼策略 ??12,.mFffg?()12211221121221212(,.),.(,.,.,),.,.,.(,.,.,)nmnmout noutnnmzfxzzfxgxzxxz???其中 、 和 分別表示源節(jié)點(diǎn)、中間節(jié)點(diǎn)和(1)i?)iz?(outi?匯節(jié)點(diǎn)的信息。 □Pr(|,)guesralguesraljjiixz????,NS推論 [3] 源節(jié)點(diǎn)和匯節(jié)點(diǎn)數(shù)均為 的信息流問題 可解當(dāng)且僅當(dāng)對應(yīng)的n?有向圖 的猜測數(shù)滿足 。因此，有G, □2g(,)loix()g)HsGs??2()logFix(),)l lls??定理 [6] 設(shè) 為有向圖 的子圖，則有()(,)(,)()sHV??其中 表示有向圖 和 的頂點(diǎn)之差。?Gii(?因此， g(,)(,)s??反之，設(shè) 為 的最優(yōu)策略。由定理 有2m?1m?m， ()(,)(,)ss???1(,)g(,)llmssC?????而 為完全圖，因此2CK???()21g(,)(,).(,)nnsssC?????????()g1ll lC□下面考慮有向圖猜測數(shù)的上下界和線性猜測數(shù)的代數(shù)表示。下面利用圖論的一些概念計算猜測數(shù)的上下界。n cp()定理 [8] 設(shè) 為無向圖，對任意 有(,)GVE?2s?()cpg(,)()Gn????其中 為圖 的獨(dú)立數(shù)， 為圖 的團(tuán)覆蓋數(shù)。引理 設(shè) 為有向輪圖，則有()whelG??()1g(),2whelGns????證明：由定理 和例 有 () □(,)(),g(,)12wheln nssCC?????????定理 有向輪圖的猜測數(shù)為 當(dāng)且僅當(dāng) 。01001As??????????(4)whelGA???rank()2A??I由定理 和定理 2.,8 知，()g(),g(4),g(4),rank()2whel whellwhelGnsssA???????????(充分性)當(dāng) 時，即 n 點(diǎn)的出度或入度為 0。g(,=1helGs當(dāng) 時，刪除頂點(diǎn) ，其中 為滿足 且 的點(diǎn)。 □（二）無向輪圖的猜測數(shù)類似于有向輪圖，我們可以考慮無向輪圖的猜測數(shù)。()whelGn除掉頂點(diǎn) 之后， 中沒有頂點(diǎn)數(shù)大于 2 的完全子圖(團(tuán))。lGn由于頂點(diǎn) 與其他所有點(diǎn)都相鄰，所以 的包含頂點(diǎn) 的獨(dú)立集的頂點(diǎn)數(shù)()whelGnn為 1。{|0, 1./2}in??/2n?從而， 。\{}lC?因此， 。設(shè) 為無向圖，用 表示頂點(diǎn)集為 、邊集為(,)GVE{}Gv???{}Vv???的無向圖。因此， 。??Mix()|XX???M不妨設(shè) (否則，以最優(yōu)策略 代替 )。則由推論 有，6,yi?()22 52log51lFixg(),2g(,)log5whelGC??????故 。i?i下面考慮 上的策略()whelGn01(,.,nPff?）()1,)) 3iiniifxxi?????, ()010(,)(nfx??23121(,(,)nnnnfxfx??????()1202))nnfx?()011(,.(,nfx???則對任意 和任意 有1,.)Fi)nxxP????,.as()1((, 3ii iiifafx??????()23123212,))(,)nnnnnnfxafx? ????()1021021((,fxaa????()0 1(,.))nnnfxax??因此， ，即有??121,. Fi(P???()i())s?從而， 。他們用圖的獨(dú)立數(shù)、團(tuán)覆蓋數(shù)和圈填充數(shù)[5]給出了猜測數(shù)的上下界。對于完全圖、二部圖、路、有向圈和無向偶圈之間笛卡爾積的猜測數(shù)，已經(jīng)得到了非常好的結(jié)論。猜測數(shù)方面仍然有非常大的研究空間，本人今后也將不斷開拓創(chuàng)新，為尋求一個解決猜測數(shù)問題的系統(tǒng)有效的方法做出貢獻(xiàn)。要感謝的人太多，要說的話
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1