關于輪圖的猜測數畢業(yè)論文_第1頁
已閱讀1頁,還剩25頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、<p><b>  南 開 大 學</b></p><p>  本 科 生 畢 業(yè) 論 文(設 計)</p><p>  中文題目:關于輪圖的猜測數</p><p>  外文題目:On the guessing number of wheel graphs</p><p><b>  學 號:&

2、lt;/b></p><p><b>  姓 名: </b></p><p>  年 級:2009級</p><p>  學 院:數學科學學院</p><p>  系 別:應用數學系</p><p>  專 業(yè):數學與應用數學</p><p&

3、gt;  完成日期:2013年5月1號</p><p><b>  指導教師: </b></p><p>  關于南開大學本科生畢業(yè)論文(設計)的聲明</p><p>  本人鄭重聲明:所呈交的學位論文(設計),題目《關于輪圖的猜測數》是本人在指導教師指導下,進行研究工作所取得的成果。除文中已經注明引用的內容外,本學位論文的研究成果不包含任何他

4、人創(chuàng)作的、以公開發(fā)表或沒有公開發(fā)表的作品內容。對本論文所涉及的研究工作做出貢獻的其他個人和集體,均已在文中以明確方式標明。本學位論文原創(chuàng)性聲明的法律責任由本人承擔。</p><p><b>  學位論文作者簽名:</b></p><p>  年 月 日</p><p>  本人聲明:該學位論文是本人指導學生完成的研究成果,已經審閱

5、過論文的全部內容,并能夠保證題目、關鍵詞、摘要部分中英文內容的一致性和準確性。</p><p>  學位論文指導教師簽名:</p><p>  年 月 日</p><p><b>  摘 要</b></p><p>  現代社會可以說在很大程度上是通過各種網絡來管理與控制的,因此用圖論等數學工具分析網絡問

6、題是一項十分重要的課題。而圖的猜測數是一個研究網絡編碼策略的有效工具。</p><p>  近年來很多學者試圖利用圖論、代數和信息論的方法研究圖的猜測數,但目前尚未得到一種系統有效的方法來解決圖的猜測數問題,特別對于無向圈的猜測數等問題目前還沒有較好的結論。因此,本文針對圈的一種擴充圖即輪圖的猜測數進行了研究,并得到了有向輪圖和無向輪圖猜測數。</p><p>  關鍵詞 猜測數;輪圖;獨

7、立數;團覆蓋數;</p><p><b>  Abstract</b></p><p>  It can be said that modern society is managed and controlled with a variety of networks in a large extent, so analysis of network problem w

8、ith mathematics is a very important task, while guessing number is efficient in considering strategy of network coding. </p><p>  In recent years, many scholars tried to do researches on the guessing numbers

9、 using the powerful mathematical technique, such as graph theory, algebra and information theory. But the research on the guessing numbers has not formed a method which is effective and systemic. Especially, the study of

10、 circles is still a difficulty. Therefore, this paper studied the guessing number of wheel graphs which is a expansion of circles, and got guessing number of wheel graphs.</p><p>  Key Words guessing number;

11、 wheel graphs; independence number; clique cover;</p><p><b>  目 錄</b></p><p><b>  摘 要I</b></p><p>  AbstractII</p><p><b>  目 錄III<

12、;/b></p><p><b>  一.引言4</b></p><p>  二.猜測數問題的簡介6</p><p> ?。ㄒ唬┎聹y數問題的提出6</p><p> ?。ǘ┚W絡編碼與猜測數8</p><p> ?。ㄈ╆P于猜測數的一些結論9</p><p>

13、;  1. 有向圖的猜測數9</p><p>  2. 無向圖的猜測數11</p><p>  三.輪圖的猜測數13</p><p> ?。ㄒ唬┯邢蜉唸D的猜測數13</p><p>  (二)無向輪圖的猜測數14</p><p><b>  四.結束語19</b></p>

14、<p><b>  參考文獻20</b></p><p><b>  致 謝22</b></p><p><b>  引 言</b></p><p>  最大流最小割定理決定了網絡的最大吞吐量。在多播通信網絡中,通過網絡編碼可使信息傳播速率達到最大值。網絡編碼的誕生和發(fā)展為網絡信息傳

15、輸指明了一個新的研究方向。</p><p>  一個通信網絡由一些通信節(jié)點和連接在某些節(jié)點之間的一些通信鏈路組成。網絡通信的目的是要將網絡中源節(jié)點產生的消息通過網絡傳輸到匯節(jié)點。</p><p>  在傳統的通信網絡中,信息傳輸采用路由的機制,每個中間節(jié)點將收到的信息傳給與它相鄰的下一個節(jié)點。在2000年,A.Rhlswede等人提出了新的傳輸方案,讓每個中間節(jié)點起到一個編碼器的作用,將其

16、收到的信息進行適當的編碼后傳輸出去,這種方案叫做網絡編碼。</p><p>  1999年,香港中文大學的楊偉豪教授和美國南加州大學的張箴教授在一篇關于衛(wèi)星通信網絡的學術論文“Distributed Source Coding for Satellite Communications”IEEE Transcations on Information Theory[1]中首次提出了網絡編碼(Network codi

17、ng)的概念。</p><p>  德國Bielefeld大學的Ahlswede教授,西安電子科技大學的蔡寧教授,以及香港中文大學的李碩彥教授和楊偉豪教授(2000)在論文“Network Information Flow” IEEE Transactions on Information Theory[2]中完全發(fā)展了網絡編碼的思想。他們以著名的蝴蝶網絡(Butterfly Network)為例闡述了網絡編碼的

18、基本原理。</p><p>  倫敦大學的S.Riis在2006年發(fā)表的論文“Utilizing public information in Network Coding” Springer[3]中首次提出了猜測數問題,并且證明了網絡編碼問題等價于對應有向圖的猜測數問題。并在2007年發(fā)表的論文“Information flows, graphs and their guessing numbers”Electr

19、onic Journal of Combinations[4]中說明可以把線路復雜性理論(Circuit Complexity Theory)的核心問題和網絡編碼問題轉化為有向圖的猜測數問題。論文中還介紹了一種特殊圖叫做鐘圖(Clock-graphs),利用線性猜測策略求出了鐘圖的猜測數。</p><p>  同年在論文“Graph Entropy, Network Coding and Guessing gam

20、es” [5]中,S.Riis借用信息論中熵的概念研究了圖的猜測數問題。這篇文章中定義了有向圖的熵和幾種類熵,并且證明任意圖的猜測數等于其熵值,利用熵計算出有些圖的猜測數(例如無向圈的猜測數與廣義猜測數)。</p><p>  T.Wu等人(2009)發(fā)表的論文“On the guessing number of Shift graphs” Journal of Discrete Algorithms[6]中應用

21、圈填充數等概念給出了有向圖猜測數的上下界,并且應用這一結論計算了一種Cayley圖叫做旋轉圖(Shift graphs)[9]猜測數的上下界。</p><p>  M.Gadouleau和S.Riis(2011)的論文“Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications” IEEE Tr

22、ansactions on Information Theory [7]中得出了如下兩個結論;第一是定義任意有向圖的猜測圖,并且證明任意有向圖的猜測數等于其猜測圖的獨立數的對數。論文中利用猜測圖給出幾種有向圖乘積[10]的猜測數和在不同編碼集下猜測數之間的關系式。第二是找出了圍長為的一系列有向圖使其線性猜測數與其頂點數之比趨于1。</p><p>  D.Christofids和K.Markström(

23、2011)在他們的論文“The guessing number of undirected graphs”Electronic Journal of Combinations[8]中專門討論了無向圖的猜測數問題,并利用無向圖的(分數)團覆蓋數和(分數)獨立數[11]給出了無向圖猜測數的上下界,證明了圖的猜測數等于編碼圖的獨立數的對數。同時,D.Christofids和K.Markström在這篇論文中提出了奇圈的猜測數問題,即

24、和等尚未解決的問題。</p><p>  本文主要針對輪圖的猜測數問題進行了研究。首先利用論文[6,8]的結論初步計算出輪圖猜測數的上下界。其次,對于無向輪圖,以構造一個猜測策略的方法得到了與奇圈猜測數的關系。</p><p>  二.猜測數問題的簡介</p><p> ?。ㄒ唬┎聹y數問題的提出</p><p>  先考慮一個合作游戲(A g

25、ame of cooperation),其規(guī)則如下:</p><p>  個人擲-面骰子(其中每一面的點數分別為),然后把自己的值給別人觀看。如果所有人都猜對了自己的值,則稱猜測成功,否則就算猜測失敗。</p><p>  在無策略的情況下,所有人猜對的概率為</p><p><b>  (2.1)</b></p><p&g

26、t;  假設每個人都知道其他個人的值(內部消息)。那么,我們可以采用以下策略使得上述概率達到最大值。</p><p>  令每個人都相信所有人的值之和被整除,此時所有人都可以計算出自己的值。</p><p>  在這一策略下,所有人猜對的概率等于所有人的值之和被整除的概率,即</p><p><b>  (2.2)</b></p>

27、<p>  我們把這游戲推廣到一般有向圖中;</p><p>  設為有向圖,并把圖中每一節(jié)點視為游戲參賽者。假設每一點的值均屬于,其中。對于兩個節(jié)點,假設當時知道的值,否則不知道的值。此時,希望所有人猜對的概率達到最大值。</p><p>  定義2.1 設(頂點集為,邊集為)為有向圖,記,,此時映射稱為頂點的猜測策略,其中表示節(jié)點的入度。并把向量函數稱之為有向圖的一個猜測策

28、略,其中,,。</p><p>  易知,猜測策略的總數為。</p><p>  定義2.2 設為有向圖的一個猜測策略,稱為猜測策略的固定點集。</p><p>  定義2.3 稱為有向圖的猜測數,此時等號成立的猜測策略稱為最優(yōu)策略,記為,其中表示固定點集的頂點數。</p><p>  稱為有向圖的線性猜測數,其中表示所有均為線性映射的策略。

29、</p><p><b>  顯然有,</b></p><p><b>  (2.3)</b></p><p>  下面證明上述最優(yōu)策略為在合作游戲中所有人猜對的概率最大的策略。</p><p>  設為所有人的真值向量,則所有人猜對當且僅當</p><p>  因此,猜測策

30、略下所有人猜對的概率為</p><p><b>  (2.4)</b></p><p>  例2.1 完全圖的猜測數為</p><p><b>  , (2.5)</b></p><p><b>  證明:首先證明。</b></p><p><b

31、>  對任意,如果,則</b></p><p><b>  (2.6)</b></p><p><b>  因此,,即。</b></p><p><b>  下面證明。</b></p><p>  我們取如下策略,其中</p><p>

32、;<b>  (2.7)</b></p><p><b>  則</b></p><p><b>  從而,即得。□</b></p><p>  例2.2 設為無圈有向圖,則</p><p>  (二)網絡編碼與猜測數</p><p>  這一節(jié)中我們

33、將介紹網絡編碼與猜測數問題的對應關系。在論文[3]中證明了每個網絡編碼問題均可轉化為有向圖的猜測數問題。</p><p>  定義2.4 設給定的網絡,為編碼集(),如果利用網絡編碼可以實現源節(jié)點到所有匯節(jié)點的組播,則稱信息流問題可解,并把這種策略稱為信息流問題的解。</p><p>  在這一節(jié)中,我們主要考慮源節(jié)點和匯節(jié)點數相同的網絡組播問題。我們先把網絡的源節(jié)點和匯節(jié)點一一結合起來,

34、然后由恒等映射可以得到有向圖。例如在圖1中,由圖(a)和(c)以源匯節(jié)點結合的方法可以得到圖(b)和(d)。</p><p>  (b)(c)(d)</p><p>  圖1 網絡編碼到猜測數問題的轉化</p><p>  定理2.1 [3] 信息流問題的解與有向圖上成功猜測的概率至少為的猜測策略一一對應,其中表示有向圖的頂點數。</p><

35、p><b>  證明:考慮有向圖</b></p><p>  設網絡的源節(jié)點和匯節(jié)點分別記為和</p><p>  由于網絡中無圈,所以可以對中間節(jié)點定義偏序,記為</p><p><b>  (2.8)</b></p><p>  下面考慮網絡的任意網絡編碼策略</p><

36、;p><b>  (2.9)</b></p><p>  其中、和分別表示源節(jié)點、中間節(jié)點和匯節(jié)點的信息。</p><p>  則與它對應的有向圖的猜測策略為,</p><p><b>  (2.10)</b></p><p>  顯然上述策略與一一對應。以下證明猜測策略下猜測成功的概率為當且

37、僅當信息流問題有解。</p><p>  猜測成功的概率為 信息流問題有解?!?lt;/p><p>  推論2.2 [3] 源節(jié)點和匯節(jié)點數均為的信息流問題可解當且僅當對應的有向圖的猜測數滿足。</p><p> ?。ㄈ╆P于猜測數的一些結論</p><p>  1. 有向圖的猜測數</p><p>  先考慮子圖和剖

38、分圖的猜測數。</p><p>  定理2.3設為有向圖的子圖,則有</p><p><b>  , (2.11)</b></p><p>  證明:設和分別為有向圖的最優(yōu)猜測策略與線性猜測策略。則和可視為的猜測策略和線性猜測策略。因此,有</p><p><b>  ,□</b></p&

39、gt;<p>  定理2.4 [6] 設為有向圖的子圖,則有</p><p><b>  (2.12)</b></p><p>  其中表示有向圖和的頂點之差。</p><p>  推論2.5設有向圖為由圖刪除一頂點得到的圖,即,則有</p><p><b>  (2.13)</b>&

40、lt;/p><p>  定理2.6 設有向圖為由圖剖分一點得到的圖,則有</p><p><b>  (2.14)</b></p><p>  證明:設且邊,并設為在圖的邊上添加一個頂點得到的圖,即。</p><p>  設為的最優(yōu)策略。令,其中和為</p><p><b>  (2.15)

41、</b></p><p>  則為的猜測策略,并且顯然有。</p><p><b>  因此,</b></p><p>  反之,設為的最優(yōu)策略。令</p><p><b>  (2.16)</b></p><p>  則為有向圖的一個策略,且</p>

42、<p><b>  因此,。</b></p><p><b>  故?!?lt;/b></p><p>  例2.3 設為頂點數為的有向圈,則有向圈的猜測數為</p><p><b>  (2.17)</b></p><p>  證明:當時,可以視為的剖分圖。由定理

43、2.3有</p><p><b>  ,(2.18)</b></p><p><b>  而為完全圖,因此</b></p><p><b>  (2.19)</b></p><p><b>  (2.20)</b></p><p>

44、;<b>  □</b></p><p>  下面考慮有向圖猜測數的上下界和線性猜測數的代數表示。</p><p>  定理2.7 [6] 設為有向圖,對有</p><p><b>  (2.21)</b></p><p>  其中表示有向圖中點不相交的圈數的最大值,表示有向圖中把變?yōu)闊o圈的最小刪除

45、邊數。</p><p>  定理2.8 [6] 設為有向圖,則有</p><p><b>  (2.22)</b></p><p>  其中表示有向圖的鄰接矩陣,表示階單位矩陣,表示當時必有。</p><p>  2. 無向圖的猜測數</p><p>  我們可以把無向圖視為雙向邊有向圖、無向圖的

46、猜測數定義為對應雙向邊有向圖的猜測數。下面利用圖論的一些概念計算猜測數的上下界。</p><p>  定義2.5 設為無向圖,節(jié)點集且,則稱為圖的導出子圖。如果其導出子圖為完全圖,則稱此子圖為圖的一個團,并記為。</p><p>  定義2.6 若有一團集覆蓋了圖的所有邊,即圖中每一條至少屬于一個,這時我們稱團集中的團的個數為團覆蓋數,記為。</p><p>  定

47、理2.8 [8] 設為無向圖,對任意有</p><p><b>  (2.23)</b></p><p>  其中為圖的獨立數,為圖的團覆蓋數。</p><p><b>  三.輪圖的猜測數</b></p><p> ?。ㄒ唬┯邢蜉唸D的猜測數</p><p>  在這一節(jié)中,

48、我們考慮有向圈上添加一個頂點并與它連接所有頂點,這類圖定義為輪圖。為了嚴格定義輪圖,先把有向圈用數學符號來表示,其表示如下</p><p><b>  ,其中,</b></p><p>  定義3.1 設為有向圖,其頂點集和邊集分別為</p><p><b>  ,(3.1)</b></p><p&g

49、t;  則稱有向圖為有向輪圖,并記為。</p><p>  記,它表示頂點的入出變化數。</p><p>  引理 設為有向輪圖,則有</p><p><b>  (3.2)</b></p><p>  證明:由定理2.5和例2.3有</p><p><b>  (3.3)□</

50、b></p><p>  定理3.1 有向輪圖的猜測數為當且僅當。</p><p><b>  證明: (必要性)</b></p><p>  反證法:假設,只需證明。</p><p>  此時,易證為的子圖(見圖2)。</p><p><b>  圖2 有向輪圖</b>

51、;</p><p><b>  的鄰接矩陣為</b></p><p><b>  (3.4)</b></p><p><b>  記 ,則且。</b></p><p>  由定理2.3和定理2.,8知,</p><p><b>  (3.5)&

52、lt;/b></p><p><b>  (充分性)</b></p><p>  當時,即n點的出度或入度為0。</p><p>  刪除頂點0,則變成有向無圈圖。由推論2.5知,。</p><p><b>  因此,。</b></p><p>  當時,刪除頂點,其中

53、為滿足且的點。</p><p>  則變成有向無圈圖,因此,。</p><p><b>  故?!?lt;/b></p><p>  推論3.2有向輪圖的猜測數為</p><p><b>  (3.6)</b></p><p>  證明:由定理3.2和引理顯然成立?!?lt;/

54、p><p> ?。ǘo向輪圖的猜測數</p><p>  類似于有向輪圖,我們可以考慮無向輪圖的猜測數。</p><p>  定義3.2 設為如下定義頂點集和邊集的無向圖,</p><p>  ,() (3.7)</p><p>  此時,稱為無向輪圖,記為。</p><p>  定理3.3 有

55、向輪圖的猜測數為</p><p><b>  (3.8)</b></p><p>  證明:分別當為奇數和偶數時考慮輪圖的猜測數。</p><p><b>  當為偶數時</b></p><p>  首先,中沒有頂點數大于3的完全子圖(團)。</p><p>  除掉頂點之后

56、,中沒有頂點數大于2的完全子圖(團)。</p><p>  因此,的團覆蓋數滿足</p><p><b>  (3.9)</b></p><p><b>  而為的-團覆蓋。</b></p><p><b>  從而,。</b></p><p>  下

57、面考慮的最大獨立數。</p><p>  由于頂點與其他所有點都相鄰,所以的包含頂點的獨立集的頂點數為1。設為獨立集,則。因此,。</p><p>  另外,為獨立集,且。</p><p><b>  從而,。</b></p><p><b>  由定理2.8知,。</b></p>&

58、lt;p><b>  當為奇數時</b></p><p>  類似于上述為偶數的情形,分別計算團覆蓋數和最大獨立數。</p><p>  中沒有頂點數大于3的完全子圖(團),而且除掉頂點之后中沒有頂點數大于2的完全子圖(團)。</p><p><b>  因此,。</b></p><p>  

59、所以,為最大數團覆蓋,即</p><p><b>  (3.10)</b></p><p>  設為獨立集,與上述為偶數的情形類似地可以證明</p><p><b>  (3.11)</b></p><p>  因此,()為最大獨立集,即</p><p><b> 

60、 (3.12)</b></p><p>  由定理2.8知,?!?lt;/p><p>  下面考慮時任意圖上加一個頂點并與此點連接所有頂點的情形。為此,先規(guī)定如下符號。</p><p>  設為無向圖,用表示頂點集為、邊集為的無向圖。</p><p>  定義3.11設為無向圖,為無向圖的一個猜測策略,</p><

61、;p>  則稱為的共軛策略,記為,其中表示維向量。</p><p><b>  引理 </b></p><p>  證明: 對任意,記,則有</p><p><b>  (3.13)</b></p><p><b>  反之,當時有,。</b></p>&l

62、t;p>  而且顯然有當且僅當。因此,?!?lt;/p><p>  由引理可以知道,當為最優(yōu)策略是也為最優(yōu)策略。</p><p>  定理3.5 設為無向圖,則有</p><p><b>  (3.14)</b></p><p>  證明:設為最優(yōu)策略,即。</p><p>  記,并稱為對稱

63、固定點集。</p><p>  不妨設(否則,以最優(yōu)策略代替)。</p><p><b>  上取如下策略,</b></p><p><b>  其中 ,</b></p><p><b>  (3.15)</b></p><p><b>  

64、則對有,,</b></p><p><b>  從而,。</b></p><p><b>  故 ?!?lt;/b></p><p><b>  無向輪圖的猜測數為</b></p><p><b>  (3.16)</b></p>&l

65、t;p>  證明:在文[8]中介紹了無向輪圖的猜測數為,并且最優(yōu)策略為</p><p>  ,其中(3.17)</p><p>  此時,按定理3.5證明構造輪圖的猜測策略,其為如下</p><p><b>  (3.18)</b></p><p><b>  其中,</b></p&g

66、t;<p>  表示第()頂點所得到的信息。則由推論2.5有,</p><p><b>  (3.19)</b></p><p><b>  故?!?lt;/b></p><p>  從例3.1可以猜想無向奇輪圖的猜測數等于奇圈的猜測數加1。</p><p>  定理3.6 無向輪圖的猜測

67、數為</p><p><b>  (3.20)</b></p><p>  證明:只需證明為奇數的情形。</p><p>  設為奇圈的最優(yōu)策略,其中 為頂點的局部策略。</p><p><b>  下面考慮上的策略</b></p><p><b>  (3.21)

68、</b></p><p><b>  , (3.22)</b></p><p><b>  (3.23)</b></p><p><b>  (3.24)</b></p><p><b>  則對任意和任意有</b></p>&

69、lt;p><b>  (3.25)</b></p><p><b>  (3.26)</b></p><p><b>  (3.27)</b></p><p><b>  (3.28)</b></p><p><b>  因此,,即有<

70、;/b></p><p><b>  (3.29)</b></p><p><b>  從而,。</b></p><p>  由推論2.5有,?!?lt;/p><p><b>  四.結束語</b></p><p>  由于確定圖的猜測數是NP-難問

71、題,而且猜測數的研究起步比較晚,目前還沒得到一種系統有效的計算方法。2006年S.Riis[3]提出猜測數問題之后,T.Wu等人從不同的角度出發(fā)研究了圖的猜測數問題。他們用圖的獨立數、團覆蓋數和圈填充數[5]給出了猜測數的上下界。此外,用熵[5]、猜測圖[7]和編碼圖[8]等新的概念把猜測數問題轉化為另一種問題,并且用此工具算出了一些特殊圖的猜測數。但是對很多圖,特別對無向奇圈尚未得到確切的猜測數值。</p><p&

72、gt;  目前,除了奇圈之外對其他簡單圖的猜測數已經得到了一定的結果,因此我們需要考慮笛卡爾積等圖的擴充圖的猜測數問題,。對于完全圖、二部圖、路、有向圈和無向偶圈之間笛卡爾積的猜測數,已經得到了非常好的結論。進一步,我們還可以考慮樹、Caylay圖、多部圖等圖和上述圖之間笛卡爾積的猜測數問題。</p><p>  本文中所考慮的輪圖為比較簡單的擴充圖,它是由一個圈添加一個頂點并連接所有頂點得到的圖。對于有向輪圖和

73、頂點數為奇數的輪圖,我們在第三章中給出了確切的猜測數,而對于頂點數為偶數的輪圖,證明了其猜測數等于奇圈的猜測數加一。</p><p>  猜測數方面仍然有非常大的研究空間,本人今后也將不斷開拓創(chuàng)新,為尋求一個解決猜測數問題的系統有效的方法做出貢獻。參考文獻</p><p>  [1] R.W. Yeung, Z. Zhang. Distributed Source Coding for S

74、atellite Communications. IEEE Transactions on Information Theory, vol.45 May 1999.</p><p>  [2] R. Ahlswede, N. Cai, N. Li, et al. Network information flow. IEEE Transactions on Information Theory, vol.46 J

75、uly 2000.</p><p>  [3] S.Riis. Utilizing public informations in network coding. General Theory of information Transfer and Combinatorics, Springer 2006.</p><p>  [4] S.Riis. Information flows, g

76、raphs and their guessing numbers. Electronic Journal of Combinatorics, 14(1) R44 (2006).</p><p>  [5] S.Riis. Graph entropy, network coding and guessing games. arXiv.org/pdf/0711.</p><p><b&g

77、t;  , 2007.</b></p><p>  [6] T.Wu, P.Cameron, S.Riis. On the guessing number of shift graphs. Journal of Diserete Algorithms, vol7(2) (2009).</p><p>  [7] M.Gadouleau, S.Riis. Graph-theore

78、tical constructions for graph entropy and network coding based communications. IEEE Transactions on Information Theory, 1T-57(10) (2011).</p><p>  [8] D.Christofids, K.Markstrom. The guessing number of undir

79、ected graphs. Electronic Journal of combinatorics, 18(2011).</p><p>  [9] L.Pippenger, N.Valiant. Shifting graphs and their applications. JACM, 23:423–432, 1976.</p><p>  [10] W.Imrich, S.Klavza

80、r, D.F.Rall. Topics in Graph Theory: Graphs and Their Cartesian Product. A K Peters, 2008, p219.</p><p>  [11] E.R.Scheinerman, D.H.Ullman. Fractional graph theory. John Wiley & Sons Inc, 1997, p240.<

81、/p><p>  [12] Sun Yun. Network Coding and Graph Entropy:[PhD thesis]. Queen Mary University of London, 2009.</p><p>  [13] R.Koetter, M.Medard. Beyond routing: An algebraic approach to network codi

82、ng. In Proceedings of the 2002 IEEE Infocom, 2002.</p><p>  [14] B.E.Tarjan, A.E.Trojanowski. Finding a maxium independent set. SIAM J.Comput, 6(3):537-546, 1977.</p><p>  [15] 蔣長浩. 圖論與網絡流. 中國林業(yè)

83、出版社. 2001年, 第一版, 174~194.</p><p><b>  致 謝</b></p><p>  在論文完成之際,我首先向關心幫助和指導我的指導老師金應烈教授表示衷心的感謝并致以崇高的敬意!金應烈老師作為一名優(yōu)秀的、經驗豐富的教師,具有豐富的數學知識和教學經驗,在整個論文討論和論文寫作過程中,對我進行了耐心的指導和幫助,提出嚴格要求,引導我不斷開闊

84、思路,為我答疑解惑,鼓勵我大膽創(chuàng)新,使我在這一段寶貴的時光中,既增長了知識、開闊了視野、鍛煉了心態(tài),又培養(yǎng)了嚴謹求實的治學方法和勇于探索的科研精神。值此論文完成之際,謹向我的導師致以最崇高的謝意!</p><p>  光陰似箭,轉眼間,四年的留學生活即將結束,依依不舍之情難以言表。要感謝的人太多,要說的話也很多。我會永遠記得在南開留學的美好時光。最后,我衷心地感謝在南開四年以來所有老師對我的大力栽培。</p

85、><p>  *Jg&6a*CZ7H$dq8KqqfHVZFedswSyXTy#&QA9wkxFyeQ^!djs#XuyUP2kNXpRWXmA&UE9aQ@Gn8xp$R#&#849Gx^Gjqv^$UE9wEwZ#Qc@UE%&qYp@Eh5pDx2zVkum&gTXRm6X4NGpP$vSTT#&ksv*3tnGK8!z89AmYWpazadNu##KN&

86、amp;MuWFA5uxY7JnD6YWRrWwc^vR9CpbK!zn%Mz849Gx^Gjqv^$UE9wEwZ#Qc@UE%&qYp@Eh5pDx2zVkum&gTXRm6X4NGpP$vSTT#&ksv*3tnGK8!z89AmYWpazadNu##KN&MuWFA5ux^Gjqv^$UE9wEwZ#Qc@UE%&qYp@Eh5pDx2zVkum&gTXRm6X4NGpP$vSTT

溫馨提示

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

評論

0/150

提交評論