关于轮图的猜测数毕业论文

《关于轮图的猜测数毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、关于轮图的猜测数毕业论文目录摘要IABSTRACTII目录III一．引言4二．猜测数问题的简介6（一）猜测数问题的提出6（二）网络编码与猜测数8（三）关于猜测数的一些结论91.有向图的猜测数92.无向图的猜测数11三．轮图的猜测数13（一）有向轮图的猜测数13（二）无向轮图的猜测数14四．结束语19参考文献20致谢2219一．引言最大流最小割定理决定了网络的最大吞吐量。在多播通信网络中，通过网络编码可使信息传播速率达到最大值。网络编码的诞生和发展为网络信息传输指明了一个新的研究方向。一个通信网络由一些通信节点和

2、连接在某些节点之间的一些通信链路组成。网络通信的目的是要将网络中源节点产生的消息通过网络传输到汇节点。在传统的通信网络中，信息传输采用路由的机制，每个中间节点将收到的信息传给与它相邻的下一个节点。在2000年，A.Rhlswede等人提出了新的传输方案，让每个中间节点起到一个编码器的作用，将其收到的信息进行适当的编码后传输出去，这种方案叫做网络编码。1999年，香港中文大学的杨伟豪教授和美国南加州大学的张箴教授在一篇关于卫星通信网络的学术论文“DistributedSourceCodingforSatellit

3、eCommunications”IEEETranscationsonInformationTheory[1]中首次提出了网络编码(Networkcoding)的概念。德国Bielefeld大学的Ahlswede教授，西安电子科技大学的蔡宁教授，以及香港中文大学的李硕彦教授和杨伟豪教授(2000)在论文“NetworkInformationFlow”IEEETransactionsonInformationTheory[2]中完全发展了网络编码的思想。他们以著名的蝴蝶网络(ButterflyNetwork)为例阐

4、述了网络编码的基本原理。伦敦大学的S.Riis在2006年发表的论文“UtilizingpublicinformationinNetworkCoding”Springer[3]中首次提出了猜测数问题，并且证明了网络编码问题等价于对应有向图的猜测数问题。并在2007年发表的论文“Informationflows,graphsandtheirguessingnumbers”ElectronicJournalofCombinations[4]中说明可以把线路复杂性理论(CircuitComplexityTheory)

5、的核心问题和网络编码问题转化为有向图的猜测数问题。论文中还介绍了一种特殊图叫做钟图(Clock-graphs)，利用线性猜测策略求出了钟图的猜测数。同年在论文“GraphEntropy,NetworkCodingandGuessinggames”[5]中，S.Riis借用信息论中熵的概念研究了图的猜测数问题。这篇文章中定义了有向图的熵和几种类熵，并且证明任意图的猜测数等于其熵值，利用熵计算出有些图的猜测数(例如无向圈的猜测数与广义猜测数)。19T.Wu等人(2009)发表的论文“Ontheguessingnum

6、berofShiftgraphs”JournalofDiscreteAlgorithms[6]中应用圈填充数等概念给出了有向图猜测数的上下界，并且应用这一结论计算了一种Cayley图叫做旋转图(Shiftgraphs)[9]猜测数的上下界。M.Gadouleau和S.Riis(2011)的论文“Graph-TheoreticalConstructionsforGraphEntropyandNetworkCodingBasedCommunications”IEEETransactionsonInformation

7、Theory[7]中得出了如下两个结论;第一是定义任意有向图的猜测图，并且证明任意有向图的猜测数等于其猜测图的独立数的对数。论文中利用猜测图给出几种有向图乘积[10]的猜测数和在不同编码集下猜测数之间的关系式。第二是找出了围长为的一系列有向图使其线性猜测数与其顶点数之比趋于1。D.Christofids和K.Markström(2011)在他们的论文“Theguessingnumberofundirectedgraphs”ElectronicJournalofCombinations[8]中专门讨论了无向图的猜

8、测数问题，并利用无向图的(分数)团覆盖数和(分数)独立数[11]给出了无向图猜测数的上下界，证明了图的猜测数等于编码图的独立数的对数。同时，D.Christofids和K.Markström在这篇论文中提出了奇圈的猜测数问题，即和等尚未解决的问题。本文主要针对轮图的猜测数问题进行了研究。首先利用论文[6,8]的结论初步计算出轮图猜测数的上下界。其次，对于无向轮图，以构造一个猜测策略的方