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

南 开 大 学本 科 生 毕 业 论 文(设 计)中文题目：关于轮图的猜测数外文题目：On the guessing number of wheel graphs学 号：0915104姓 名： 年 级：2009级学 院：数学科学学院系 别：应用数学系专 业：数学与应用数学完成日期：2013年5月1号指导教师： 关于南开大学本科生毕业论文(设计)的声明本人郑重声明：所呈交的学位论文(设计)，题目关于轮图的猜测数是本人在指导教师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、以公开发表或没有公开发表的作品内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年 月 日 本人声明：该学位论文是本人指导学生完成的研究成果，已经审阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性。 学位论文指导教师签名： 年 月 日摘 要现代社会可以说在很大程度上是通过各种网络来管理与控制的，因此用图论等数学工具分析网络问题是一项十分重要的课题。而图的猜测数是一个研究网络编码策略的有效工具。近年来很多学者试图利用图论、代数和信息论的方法研究图的猜测数，但目前尚未得到一种系统有效的方法来解决图的猜测数问题，特别对于无向圈的猜测数等问题目前还没有较好的结论。因此，本文针对圈的一种扩充图即轮图的猜测数进行了研究，并得到了有向轮图和无向轮图猜测数。关键词 猜测数;轮图;独立数;团覆盖数;AbstractIt can be said that modern society is managed and controlled with a variety of networks in a large extent, so analysis of network problem with mathematics is a very important task, while guessing number is efficient in considering strategy of network coding. In recent years, many scholars tried to do researches on the guessing numbers 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 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.Key Words guessing number; wheel graphs; independence number; clique cover;目 录摘 要IABSTRACTII目 录III一引言4二猜测数问题的简介6（一）猜测数问题的提出6（二）网络编码与猜测数8（三）关于猜测数的一些结论91. 有向图的猜测数92. 无向图的猜测数11三轮图的猜测数13（一）有向轮图的猜测数13（二）无向轮图的猜测数14四结束语19参考文献20致 谢22一 引 言最大流最小割定理决定了网络的最大吞吐量。在多播通信网络中，通过网络编码可使信息传播速率达到最大值。网络编码的诞生和发展为网络信息传输指明了一个新的研究方向。一个通信网络由一些通信节点和连接在某些节点之间的一些通信链路组成。网络通信的目的是要将网络中源节点产生的消息通过网络传输到汇节点。在传统的通信网络中，信息传输采用路由的机制，每个中间节点将收到的信息传给与它相邻的下一个节点。在2000年，A.Rhlswede等人提出了新的传输方案，让每个中间节点起到一个编码器的作用，将其收到的信息进行适当的编码后传输出去，这种方案叫做网络编码。1999年，香港中文大学的杨伟豪教授和美国南加州大学的张箴教授在一篇关于卫星通信网络的学术论文“Distributed Source Coding for Satellite Communications”IEEE Transcations on Information Theory1中首次提出了网络编码(Network coding)的概念。德国Bielefeld大学的Ahlswede教授，西安电子科技大学的蔡宁教授，以及香港中文大学的李硕彦教授和杨伟豪教授(2000)在论文“Network Information Flow” IEEE Transactions on Information Theory2中完全发展了网络编码的思想。他们以著名的蝴蝶网络(Butterfly Network)为例阐述了网络编码的基本原理。伦敦大学的S.Riis在2006年发表的论文“Utilizing public information in Network Coding” Springer3中首次提出了猜测数问题，并且证明了网络编码问题等价于对应有向图的猜测数问题。并在2007年发表的论文“Information flows, graphs and their guessing numbers”Electronic Journal of Combinations4中说明可以把线路复杂性理论(Circuit Complexity Theory)的核心问题和网络编码问题转化为有向图的猜测数问题。论文中还介绍了一种特殊图叫做钟图(Clock-graphs)，利用线性猜测策略求出了钟图的猜测数。同年在论文“Graph Entropy, Network Coding and Guessing games” 5中，S.Riis借用信息论中熵的概念研究了图的猜测数问题。这篇文章中定义了有向图的熵和几种类熵，并且证明任意图的猜测数等于其熵值，利用熵计算出有些图的猜测数(例如无向圈的猜测数与广义猜测数)。T.Wu等人(2009)发表的论文“On the guessing number of Shift graphs” Journal of Discrete Algorithms6中应用圈填充数等概念给出了有向图猜测数的上下界，并且应用这一结论计算了一种Cayley图叫做旋转图(Shift graphs)9猜测数的上下界。M.Gadouleau和S.Riis(2011)的论文“Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications” IEEE Transactions on Information Theory 7中得出了如下两个结论;第一是定义任意有向图的猜测图，并且证明任意有向图的猜测数等于其猜测图的独立数的对数。论文中利用猜测图给出几种有向图乘积10的猜测数和在不同编码集下猜测数之间的关系式。第二是找出了围长为的一系列有向图使其线性猜测数与其顶点数之比趋于1。D.Christofids和K.Markström(2011)在他们的论文“The guessing number of undirected graphs”Electronic Journal of Combinations8中专门讨论了无向图的猜测数问题，并利用无向图的(分数)团覆盖数和(分数)独立数11给出了无向图猜测数的上下界，证明了图的猜测数等于编码图的独立数的对数。同时，D.Christofids和K.Markström在这篇论文中提出了奇圈的猜测数问题，即和等尚未解决的问题。本文主要针对轮图的猜测数问题进行了研究。首先利用论文6,8的结论初步计算出轮图猜测数的上下界。其次，对于无向轮图，以构造一个猜测策略的方法得到了与奇圈猜测数的关系。二猜测数问题的简介（一）猜测数问题的提出先考虑一个合作游戏(A game of cooperation)，其规则如下：个人掷-面骰子(其中每一面的点数分别为)，然后把自己的值给别人观看。如果所有人都猜对了自己的值，则称猜测成功，否则就算猜测失败。在无策略的情况下，所有人猜对的概率为(2.1)假设每个人都知道其他个人的值(内部消息)。那么，我们可以采用以下策略使得上述概率达到最大值。令每个人都相信所有人的值之和被整除，此时所有人都可以计算出自己的值。在这一策略下，所有人猜对的概率等于所有人的值之和被整除的概率，即(2.2)我们把这游戏推广到一般有向图中;设为有向图，并把图中每一节点视为游戏参赛者。假设每一点的值均属于，其中。对于两个节点，假设当时知道的值，否则不知道的值。此时，希望所有人猜对的概率达到最大值。定义2.1 设(顶点集为，边集为)为有向图，记，此时映射称为顶点的猜测策略，其中表示节点的入度。并把向量函数称之为有向图的一个猜测策略，其中，。易知，猜测策略的总数为。定义2.2 设为有向图的一个猜测策略，称为猜测策略的固定点集。定义2.3 称为有向图的猜测数，此时等号成立的猜测策略称为最优策略，记为，其中表示固定点集的顶点数。称为有向图的线性猜测数，其中表示所有均为线性映射的策略。显然有，(2.3)下面证明上述最优策略为在合作游戏中所有人猜对的概率最大的策略。设为所有人的真值向量，则所有人猜对当且仅当 因此，猜测策略下所有人猜对的概率为(2.4)例2.1 完全图的猜测数为， (2.5)证明：首先证明。对任意，如果，则(2.6)因此，即。下面证明。我们取如下策略，其中 (2.7)则从而，即得。例2.2 设为无圈有向图，则（二）网络编码与猜测数这一节中我们将介绍网络编码与猜测数问题的对应关系。在论文3中证明了每个网络编码问题均可转化为有向图的猜测数问题。定义2.4 设给定的网络，为编码集()，如果利用网络编码可以实现源节点到所有汇节点的组播，则称信息流问题可解，并把这种策略称为信息流问题的解。在这一节中，我们主要考虑源节点和汇节点数相同的网络组播问题。我们先把网络的源节点和汇节点一一结合起来，然后由恒等映射可以得到有向图。例如在图1中，由图(a)和(c)以源汇节点结合的方法可以得到图(b)和(d)。 （a） (b)(c)(d)图1 网络编码到猜测数问题的转化定理2.1 3 信息流问题的解与有向图上成功猜测的概率至少为的猜测策略一一对应，其中表示有向图的顶点数。证明：考虑有向图设网络的源节点和汇节点分别记为和由于网络中无圈，所以可以对中间节点定义偏序，记为(2.8)下面考虑网络的任意网络编码策略(2.9)其中、和分别表示源节点、中间节点和汇节点的信息。则与它对应的有向图的猜测策略为，(2.10)显然上述策略与一一对应。以下证明猜测策略下猜测成功的概率为当且仅当信息流问题有解。 猜测成功的概率为 信息流问题有解。推论2.2 3 源节点和汇节点数均为的信息流问题可解当且仅当对应的有向图的猜测数满足。（三）关于猜测数的一些结论1. 有向图的猜测数先考虑子图和剖分图的猜测数。定理2.3设为有向图的子图，则有， (2.11)证明：设和分别为有向图的最优猜测策略与线性猜测策略。则和可视为的猜测策略和线性猜测策略。因此，有,定理2.4 6 设为有向图的子图，则有(2.12)其中表示有向图和的顶点之差。推论2.5设有向图为由图删除一顶点得到的图，即，则有(2.13)定理2.6 设有向图为由图剖分一点得到的图，则有(2.14)证明：设且边，并设为在图的边上添加一个顶点得到的图，即。设为的最优策略。令，其中和为(2.15)则为的猜测策略，并且显然有。因此，反之，设为的最优策略。令(2.16)则为有向图的一个策略，且因此，。故。例2.3 设为顶点数为的有向圈，则有向圈的猜测数为(2.17)证明：当时，可以视为的剖分图。由定理2.3有，(2.18)而为完全图，因此(2.19)(2.20)下面考虑有向图猜测数的上下界和线性猜测数的代数表示。定理2.7 6 设为有向图，对有(2.21)其中表示有向图中点不相交的圈数的最大值，表示有向图中把变为无圈的最小删除边数。定理2.8 6 设为有向图，则有(2.22)其中表示有向图的邻接矩阵，表示阶单位矩阵，表示当时必有。2. 无向图的猜测数我们可以把无向图视为双向边有向图、无向图的猜测数定义为对应双向边有向图的猜测数。下面利用图论的一些概念计算猜测数的上下界。定义2.5 设为无向图，节点集且，则称为图的导出子图。如果其导出子图为完全图，则称此子图为图的一个团，并记为。定义2.6 若有一团集覆盖了图的所有边，即图中每一条至少属于一个，这时我们称团集中的团的个数为团覆盖数，记为。定理2.8 8 设为无向图，对任意有(2.23)其中为图的独立数，为图的团覆盖数。三轮图的猜测数（一）有向轮图的猜测数在这一节中，我们考虑有向圈上添加一个顶点并与它连接所有顶点，这类图定义为轮图。为了严格定义轮图，先把有向圈用数学符号来表示，其表示如下，其中，定义3.1 设为有向图，其顶点集和边集分别为，(3.1)则称有向图为有向轮图，并记为。记，它表示顶点的入出变化数。引理 设为有向轮图，则有(3.2)证明：由定理2.5和例2.3有 (3.3)定理3.1 有向轮图的猜测数为当且仅当。证明： (必要性)反证法：假设，只需证明。此时，易证为的子图(见图2)。图2 有向轮图的邻接矩阵为(3.4)记 ，则且。由定理2.3和定理2.,8知，(3.5)(充分性)当时，即n点的出度或入度为0。删除顶点0,则变成有向无圈图。由推论2.5知，。因此，。当时，删除顶点，其中为满足且的点。则变成有向无圈图，因此，。故。推论3.2有向轮图的猜测数为(3.6)证明：由定理3.2和引理显然成立。（二）无向轮图的猜测数类似于有向轮图，我们可以考虑无向轮图的猜测数。定义3.2 设为如下定义顶点集和边集的无向图，() (3.7)此时，称为无向轮图，记为。定理3.3 有向轮图的猜测数为 (3.8)证明：分别当为奇数和偶数时考虑轮图的猜测数。1. 当为偶数时首先，中没有顶点数大于3的完全子图(团)。除掉顶点之后，中没有顶点数大于2的完全子图(团)。因此，的团覆盖数满足(3.9)而为的-团覆盖。从而，。下面考虑的最大独立数。由于顶点与其他所有点都相邻，所以的包含顶点的独立集的顶点数为1。设为独立集，则。因此，。另外，为独立集，且。从而，。由定理2.8知，。2. 当为奇数时类似于上述为偶数的情形，分别计算团覆盖数和最大独立数。中没有顶点数大于3的完全子图(团)，而且除掉顶点之后中没有顶点数大于2的完全子图(团)。因此，。所以，为最大数团覆盖，即(3.10)设为独立集，与上述为偶数的情形类似地可以证明(3.11)因此，()为最大独立集，即(3.12)由定理2.8知，。下面考虑时任意图上加一个顶点并与此点连接所有顶点的情形。为此，先规定如下符号。设为无向图，用表示顶点集为、边集为的无向图。定义3.11设为无向图，为无向图的一个猜测策略，则称为的共轭策略，记为，其中表示维向量。引理 证明: 对任意，记，则有(3.13)反之，当时有，。而且显然有当且仅当。因此，。由引理可以知道，当为最优策略是也为最优策略。定理3.5 设为无向图，则有(3.14)证明：设为最优策略，即。记，并称为对称固定点集。不妨设(否则，以最优策略代替)。上取如下策略,其中 ,(3.15)则对有，从而，。故 。例3.1 无向轮图的猜测数为(3.16)证明：在文8中介绍了无向轮图的猜测数为，并且最优策略为，其中(3.17)此时，按定理3.5证明构造轮图的猜测策略，其为如下(3.18)其中，表示第()顶点所得到的信息。则由推论2.5有，(3.19)故。从例3.1可以猜想无向奇轮图的猜测数等于奇圈的猜测数加1。定理3.6 无向轮图的猜测数为(3.20)证明：只需证明为奇数的情形。设为奇圈的最优策略，其中 为顶点的局部策略。下面考虑上的策略(3.21), (3.22)(3.23)(3.24)则对任意和任意有(3.25)(3.26)(3.27)(3.28)因此，即有(3.29)从而，。由推论2.5有，。四结束语由于确定图的猜测数是NP-难问题，而且猜测数的研究起步比较晚，目前还没得到一种系统有效的计算方法。2006年S.Riis3提出猜测数问题之后，T.Wu等人从不同的角度出发研究了图的猜测数问题。他们用图的独立数、团覆盖数和圈填充数5给出了猜测数的上下界。此外，用熵5、猜测图7和编码图8等新的概念把猜测数问题转化为另一种问题，并且用此工具算出了一些特殊图的猜测数。但是对很多图，特别对无向奇圈尚未得到确切的猜测数值。目前，除了奇圈之外对其他简单图的猜测数已经得到了一定的结果，因此我们需要考虑笛卡尔积等图的扩充图的猜测数问题，。对于完全图、二部图、路、有向圈和无向偶圈之间笛卡尔积的猜测数，已经得到了非常好的结论。进一步，我们还可以考虑树、Caylay图、多部图等图和上述图之间笛卡尔积的猜测数问题。本文中所考虑的轮图为比较简单的扩充图，它是由一个圈添加一个顶点并连接所有顶点得到的图。对于有向轮图和顶点数为奇数的轮图，我们在第三章中给出了确切的猜测数，而对于顶点数为偶数的轮图，证明了其猜测数等于奇圈的猜测数加一。猜测数方面仍然有非常大的研究空间，本人今后也将不断开拓创新，为寻求一个解决猜测数问题的系统有效的方法做出贡献。参考文献1 R.W. Yeung, Z. Zhang. Distributed Source Coding for Satellite Communications. IEEE Transactions on Information Theory, vol.45 May 1999.2 R. Ahlswede, N. Cai, N. Li, et al. Network information flow. IEEE Transactions on Information Theory, vol.46 July 2000.3 S.Riis. Utilizing public informations in network coding. General Theory of information Transfer and Combinatorics, Springer 2006.4 S.Riis. Information flows, graphs and their guessing numbers. Electronic Journal of Combinatorics, 14(1) R44 (2006).5 S.Riis. Graph entropy, network coding and guessing games. arXiv.org/pdf/0711.417541, 2007.6 T.Wu, P.Cameron, S.Riis. On the guessing number of shift graphs. Journal of Diserete Algorithms, vol7(2) (2009).7 M.Gadouleau, S.Riis. Graph-theoretical constructions for graph entropy and network coding based communications. IEEE Transactions on Information Theory, 1T-57(10) (2011).8 D.Christofids, K.Markstrom. The guessing number of undirected graphs. Electronic Journal of combinatorics, 18(2011).9 L.Pippenger, N.Valiant. Shifting graphs and their applications. JACM, 23:423432, 1976.10 W.Imrich, S.Klavzar, D.F.Rall. Topics in Graph Theory: Graphs and Their Cartesian Product. A K Peters, 2008, p219.11 E.R.Scheinerman, D.H.Ullman. Fractional graph theory. John Wiley & Sons Inc, 1997, p240.12 Sun Yun. Network Coding and Graph Entropy:PhD thesis. Queen Mary University of London, 2009.13 R.Koetter, M.Medard. Beyond routing: An algebraic approach to network coding. In Proceedings of the 2002 IEEE Infocom, 2002.14 B.E.Tarjan, A.E.Trojanowski. Finding a maxium independent set. SIAM J.Comput, 6(3):537-546, 1977.15 蒋长浩. 图论与网络流. 中国林业出版社. 2001年, 第一版, 174194.致 谢在论文完成之际，我首先向关心帮助和指导我的指导老师金应烈教授表示衷心的感谢并致以崇高的敬意！金应烈老师作为一名优秀的、经验丰富的教师，具有丰富的数学知识和教学经验，在整个论文讨论和论文写作过程中，对我进行了耐心的指导和帮助，提出严格要求，引导我不断开阔思路，为我答疑解惑，鼓励我大胆创新，使我在这一段宝贵的时光中，既增长了知识、开阔了视野、锻炼了心态，又培养了严谨求实的治学方法和勇于探索的科研精神。值此论文完成之际，谨向我的导师致以最崇高的谢意！光阴似箭，转眼间，四年的留学生活即将结束，依依不舍之情难以言表。要感谢的人太多，要说的话也很多。我会永远记得在南开留学的美好时光。最后，我衷心地感谢在南开四年以来所有老师对我的大力栽培。