關(guān)于輪圖的猜測(cè)數(shù)畢業(yè)論文

1、<p><b>　　南 開 大 學(xué)</b></p><p>　　本 科 生 畢 業(yè) 論 文(設(shè) 計(jì))</p><p>　　中文題目：關(guān)于輪圖的猜測(cè)數(shù)</p><p>　　外文題目：On the guessing number of wheel graphs</p><p><b>　　學(xué) 號(hào)：&

2、lt;/b></p><p><b>　　姓 名： </b></p><p>　　年 級(jí)：2009級(jí)</p><p>　　學(xué) 院：數(shù)學(xué)科學(xué)學(xué)院</p><p>　　系 別：應(yīng)用數(shù)學(xué)系</p><p>　　專 業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué)</p><p&

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

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

5、過論文的全部?jī)?nèi)容，并能夠保證題目、關(guān)鍵詞、摘要部分中英文內(nèi)容的一致性和準(zhǔn)確性。</p><p>　　學(xué)位論文指導(dǎo)教師簽名：</p><p>　　年 月 日</p><p><b>　　摘 要</b></p><p>　　現(xiàn)代社會(huì)可以說在很大程度上是通過各種網(wǎng)絡(luò)來管理與控制的，因此用圖論等數(shù)學(xué)工具分析網(wǎng)絡(luò)問

6、題是一項(xiàng)十分重要的課題。而圖的猜測(cè)數(shù)是一個(gè)研究網(wǎng)絡(luò)編碼策略的有效工具。</p><p>　　近年來很多學(xué)者試圖利用圖論、代數(shù)和信息論的方法研究圖的猜測(cè)數(shù)，但目前尚未得到一種系統(tǒng)有效的方法來解決圖的猜測(cè)數(shù)問題，特別對(duì)于無向圈的猜測(cè)數(shù)等問題目前還沒有較好的結(jié)論。因此，本文針對(duì)圈的一種擴(kuò)充圖即輪圖的猜測(cè)數(shù)進(jìn)行了研究，并得到了有向輪圖和無向輪圖猜測(cè)數(shù)。</p><p>　　關(guān)鍵詞 猜測(cè)數(shù);輪圖;獨(dú)

7、立數(shù);團(tuán)覆蓋數(shù);</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>　　二．猜測(cè)數(shù)問題的簡(jiǎn)介6</p><p>　?。ㄒ唬┎聹y(cè)數(shù)問題的提出6</p><p>　?。ǘ┚W(wǎng)絡(luò)編碼與猜測(cè)數(shù)8</p><p>　　（三）關(guān)于猜測(cè)數(shù)的一些結(jié)論9</p><p>

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

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

15、輸指明了一個(gè)新的研究方向。</p><p>　　一個(gè)通信網(wǎng)絡(luò)由一些通信節(jié)點(diǎn)和連接在某些節(jié)點(diǎn)之間的一些通信鏈路組成。網(wǎng)絡(luò)通信的目的是要將網(wǎng)絡(luò)中源節(jié)點(diǎn)產(chǎn)生的消息通過網(wǎng)絡(luò)傳輸?shù)絽R節(jié)點(diǎn)。</p><p>　　在傳統(tǒng)的通信網(wǎng)絡(luò)中，信息傳輸采用路由的機(jī)制，每個(gè)中間節(jié)點(diǎn)將收到的信息傳給與它相鄰的下一個(gè)節(jié)點(diǎn)。在2000年，A.Rhlswede等人提出了新的傳輸方案，讓每個(gè)中間節(jié)點(diǎn)起到一個(gè)編碼器的作用，將其

16、收到的信息進(jìn)行適當(dāng)?shù)木幋a后傳輸出去，這種方案叫做網(wǎng)絡(luò)編碼。</p><p>　　1999年，香港中文大學(xué)的楊偉豪教授和美國南加州大學(xué)的張?bào)鸾淌谠谝黄P(guān)于衛(wèi)星通信網(wǎng)絡(luò)的學(xué)術(shù)論文“Distributed Source Coding for Satellite Communications”IEEE Transcations on Information Theory[1]中首次提出了網(wǎng)絡(luò)編碼(Network codi

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

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

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

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

21、圈填充數(shù)等概念給出了有向圖猜測(cè)數(shù)的上下界，并且應(yīng)用這一結(jié)論計(jì)算了一種Cayley圖叫做旋轉(zhuǎn)圖(Shift graphs)[9]猜測(cè)數(shù)的上下界。</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]中得出了如下兩個(gè)結(jié)論;第一是定義任意有向圖的猜測(cè)圖，并且證明任意有向圖的猜測(cè)數(shù)等于其猜測(cè)圖的獨(dú)立數(shù)的對(duì)數(shù)。論文中利用猜測(cè)圖給出幾種有向圖乘積[10]的猜測(cè)數(shù)和在不同編碼集下猜測(cè)數(shù)之間的關(guān)系式。第二是找出了圍長為的一系列有向圖使其線性猜測(cè)數(shù)與其頂點(diǎn)數(shù)之比趨于1。</p><p>　　D.Christofids和K.Markström(

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

24、和等尚未解決的問題。</p><p>　　本文主要針對(duì)輪圖的猜測(cè)數(shù)問題進(jìn)行了研究。首先利用論文[6,8]的結(jié)論初步計(jì)算出輪圖猜測(cè)數(shù)的上下界。其次，對(duì)于無向輪圖，以構(gòu)造一個(gè)猜測(cè)策略的方法得到了與奇圈猜測(cè)數(shù)的關(guān)系。</p><p>　　二．猜測(cè)數(shù)問題的簡(jiǎn)介</p><p>　　（一）猜測(cè)數(shù)問題的提出</p><p>　　先考慮一個(gè)合作游戲(A g

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

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

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

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

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

30、略下所有人猜對(duì)的概率為</p><p><b>　　(2.4)</b></p><p>　　例2.1 完全圖的猜測(cè)數(shù)為</p><p><b>　　， (2.5)</b></p><p><b>　　證明：首先證明。</b></p><p><b

31、>　　對(duì)任意，如果，則</b></p><p><b>　　(2.6)</b></p><p><b>　　因此，，即。</b></p><p><b>　　下面證明。</b></p><p>　　我們?nèi)∪缦虏呗?，其?lt;/p><p>

32、;<b>　　(2.7)</b></p><p><b>　　則</b></p><p><b>　　從而，即得?！?lt;/b></p><p>　　例2.2 設(shè)為無圈有向圖，則</p><p>　?。ǘ┚W(wǎng)絡(luò)編碼與猜測(cè)數(shù)</p><p>　　這一節(jié)中我們

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

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

35、p><b>　　證明：考慮有向圖</b></p><p>　　設(shè)網(wǎng)絡(luò)的源節(jié)點(diǎn)和匯節(jié)點(diǎn)分別記為和</p><p>　　由于網(wǎng)絡(luò)中無圈，所以可以對(duì)中間節(jié)點(diǎn)定義偏序，記為</p><p><b>　　(2.8)</b></p><p>　　下面考慮網(wǎng)絡(luò)的任意網(wǎng)絡(luò)編碼策略</p><

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

37、僅當(dāng)信息流問題有解。</p><p>　　猜測(cè)成功的概率為 信息流問題有解?！?lt;/p><p>　　推論2.2 [3] 源節(jié)點(diǎn)和匯節(jié)點(diǎn)數(shù)均為的信息流問題可解當(dāng)且僅當(dāng)對(duì)應(yīng)的有向圖的猜測(cè)數(shù)滿足。</p><p>　?。ㄈ╆P(guān)于猜測(cè)數(shù)的一些結(jié)論</p><p>　　1. 有向圖的猜測(cè)數(shù)</p><p>　　先考慮子圖和剖

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

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

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

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

42、<p><b>　　因此，。</b></p><p><b>　　故?！?lt;/b></p><p>　　例2.3 設(shè)為頂點(diǎn)數(shù)為的有向圈，則有向圈的猜測(cè)數(shù)為</p><p><b>　　(2.17)</b></p><p>　　證明：當(dāng)時(shí)，可以視為的剖分圖。由定理

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>　　下面考慮有向圖猜測(cè)數(shù)的上下界和線性猜測(cè)數(shù)的代數(shù)表示。</p><p>　　定理2.7 [6] 設(shè)為有向圖，對(duì)有</p><p><b>　　(2.21)</b></p><p>　　其中表示有向圖中點(diǎn)不相交的圈數(shù)的最大值，表示有向圖中把變?yōu)闊o圈的最小刪除

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

46、猜測(cè)數(shù)定義為對(duì)應(yīng)雙向邊有向圖的猜測(cè)數(shù)。下面利用圖論的一些概念計(jì)算猜測(cè)數(shù)的上下界。</p><p>　　定義2.5 設(shè)為無向圖，節(jié)點(diǎn)集且，則稱為圖的導(dǎo)出子圖。如果其導(dǎo)出子圖為完全圖，則稱此子圖為圖的一個(gè)團(tuán)，并記為。</p><p>　　定義2.6 若有一團(tuán)集覆蓋了圖的所有邊，即圖中每一條至少屬于一個(gè)，這時(shí)我們稱團(tuán)集中的團(tuán)的個(gè)數(shù)為團(tuán)覆蓋數(shù)，記為。</p><p>　　定

47、理2.8 [8] 設(shè)為無向圖，對(duì)任意有</p><p><b>　　(2.23)</b></p><p>　　其中為圖的獨(dú)立數(shù)，為圖的團(tuán)覆蓋數(shù)。</p><p><b>　　三．輪圖的猜測(cè)數(shù)</b></p><p>　?。ㄒ唬┯邢蜉唸D的猜測(cè)數(shù)</p><p>　　在這一節(jié)中，

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

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

50、b></p><p>　　定理3.1 有向輪圖的猜測(cè)數(shù)為當(dāng)且僅當(dāng)。</p><p><b>　　證明： (必要性)</b></p><p>　　反證法：假設(shè)，只需證明。</p><p>　　此時(shí)，易證為的子圖(見圖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>　　當(dāng)時(shí)，即n點(diǎn)的出度或入度為0。</p><p>　　刪除頂點(diǎn)0,則變成有向無圈圖。由推論2.5知，。</p><p><b>　　因此，。</b></p><p>　　當(dāng)時(shí)，刪除頂點(diǎn)，其中

53、為滿足且的點(diǎn)。</p><p>　　則變成有向無圈圖，因此，。</p><p><b>　　故?！?lt;/b></p><p>　　推論3.2有向輪圖的猜測(cè)數(shù)為</p><p><b>　　(3.6)</b></p><p>　　證明：由定理3.2和引理顯然成立。□</

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

55、向輪圖的猜測(cè)數(shù)為</p><p><b>　　(3.8)</b></p><p>　　證明：分別當(dāng)為奇數(shù)和偶數(shù)時(shí)考慮輪圖的猜測(cè)數(shù)。</p><p><b>　　當(dāng)為偶數(shù)時(shí)</b></p><p>　　首先，中沒有頂點(diǎn)數(shù)大于3的完全子圖(團(tuán))。</p><p>　　除掉頂點(diǎn)之后

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

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

58、lt;p><b>　　當(dāng)為奇數(shù)時(shí)</b></p><p>　　類似于上述為偶數(shù)的情形，分別計(jì)算團(tuán)覆蓋數(shù)和最大獨(dú)立數(shù)。</p><p>　　中沒有頂點(diǎn)數(shù)大于3的完全子圖(團(tuán))，而且除掉頂點(diǎn)之后中沒有頂點(diǎn)數(shù)大于2的完全子圖(團(tuán))。</p><p><b>　　因此，。</b></p><p>　　

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

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

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

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

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

64、則對(duì)有，，</b></p><p><b>　　從而，。</b></p><p><b>　　故 。□</b></p><p><b>　　無向輪圖的猜測(cè)數(shù)為</b></p><p><b>　　(3.16)</b></p>&l

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

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

67、數(shù)為</p><p><b>　　(3.20)</b></p><p>　　證明：只需證明為奇數(shù)的情形。</p><p>　　設(shè)為奇圈的最優(yōu)策略，其中 為頂點(diǎn)的局部策略。</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>　　則對(duì)任意和任意有</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>　　四．結(jié)束語</b></p><p>　　由于確定圖的猜測(cè)數(shù)是NP-難問

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

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

73、頂點(diǎn)數(shù)為奇數(shù)的輪圖，我們?cè)诘谌轮薪o出了確切的猜測(cè)數(shù)，而對(duì)于頂點(diǎn)數(shù)為偶數(shù)的輪圖，證明了其猜測(cè)數(shù)等于奇圈的猜測(cè)數(shù)加一。</p><p>　　猜測(cè)數(shù)方面仍然有非常大的研究空間，本人今后也將不斷開拓創(chuàng)新，為尋求一個(gè)解決猜測(cè)數(shù)問題的系統(tǒng)有效的方法做出貢獻(xiàn)。參考文獻(xiàn)</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] 蔣長浩. 圖論與網(wǎng)絡(luò)流. 中國林業(yè)

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

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