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

南 开 大 学 本 科 生 毕 业 论 文(设 计) 中文题目：关于轮图的猜测数 外文题目：on the guessing number of wheel graphs 学 号：0915104 姓 名： 年 级：2009 级 学 院：数学科学学院 系 别：应用数学系 专 业：数学与应用数学 完成日期：2013 年 5 月 1 号 指导教师： 关于南开大学本科生毕业论文(设计)的声明 本人郑重声明：所呈交的学位论文(设计)，题目关于轮图的猜测数 是本人在指导教师指导下，进行研究工作所取得的成果。除文中已经注明引用 的内容外，本学位论文的研究成果不包含任何他人创作的、以公开发表或没有 公开发表的作品内容。对本论文所涉及的研究工作做出贡献的其他个人和集体， 均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年 月 日 本人声明：该学位论文是本人指导学生完成的研究成果，已经审阅过论文 的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确 性。 学位论文指导教师签名： 年 月 日 i 摘 要 现代社会可以说在很大程度上是通过各种网络来管理与控制的，因此用图 论等数学工具分析网络问题是一项十分重要的课题。而图的猜测数是一个研究 网络编码策略的有效工具。 近年来很多学者试图利用图论、代数和信息论的方法研究图的猜测数，但 目前尚未得到一种系统有效的方法来解决图的猜测数问题，特别对于无向圈的 猜测数等问题目前还没有较好的结论。因此，本文针对圈的一种扩充图即轮图 的猜测数进行了研究，并得到了有向轮图和无向轮图猜测数。 关键词 猜测数;轮图;独立数;团覆盖数; ii abstract 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 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; iii 目 录 摘 要 .i abstract.ii 目 录 iii 一引言 4 二猜测数问题的简介 6 （一）猜测数问题的提出 6 （二）网络编码与猜测数 8 （三）关于猜测数的一些结论 9 1. 有向图的猜测数 9 2. 无向图的猜测数 .11 三轮图的猜测数 13 （一）有向轮图的猜测数 .13 （二）无向轮图的猜测数 .14 四结束语 19 参考文献 20 致 谢 22 4 一 引 言 最大流最小割定理决定了网络的最大吞吐量。在多播通信网络中，通过网 络编码可使信息传播速率达到最大值。网络编码的诞生和发展为网络信息传输 指明了一个新的研究方向。 一个通信网络由一些通信节点和连接在某些节点之间的一些通信链路组成。 网络通信的目的是要将网络中源节点产生的消息通过网络传输到汇节点。 在传统的通信网络中，信息传输采用路由的机制，每个中间节点将收到的 信息传给与它相邻的下一个节点。在 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 借用信息论中熵的概念研究了图的猜测数问题。这篇文章中定义了有向 图的熵和几种类熵，并且证明任意图的猜测数等于其熵值，利用熵计算出有些 5 图的猜测数(例如无向圈 的猜测数与广义猜测数)。5c 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的猜测数和在不同编码集下猜测数之间的关系式。 第二是找出了围长为 的一系列有向图使其线性猜测数与其顶点数之比趋(3)l 于 1。 d.christofids 和 k.markstrm(2011)在他们的论文“the guessing number of undirected graphs”electronic journal of combinations8中专门讨论了无向图的猜 测数问题，并利用无向图的(分数)团覆盖数和(分数)独立数11给出了无向图猜 测数的上下界，证明了图的猜测数等于编码图的独立数的对数。同时， d.christofids 和 k.markstrm 在这篇论文中提出了奇圈的猜测数问题，即 和 等尚未解决的问题。21(,)3kgc21(,3)kgc(4 本文主要针对轮图的猜测数问题进行了研究。首先利用论文6,8的结论初 步计算出轮图猜测数的上下界。其次，对于无向轮图，以构造一个猜测策略的 方法得到了与奇圈猜测数的关系。 6 二猜测数问题的简介 （一）猜测数问题的提出 先考虑一个合作游戏(a game of cooperation)，其规则如下： 个人掷 -面骰子(其中每一面的点数分别为 )，然后把自己的值ns 0,1.-s 给别人观看。如果所有人都猜对了自己的值，则称猜测成功，否则就算猜测失 败。 在无策略的情况下，所有人猜对的概率为 (2.1)pr()1/nwis 假设每个人都知道其他 个人的值(内部消息)。那么，我们可以采用以下n 策略使得上述概率达到最大值。 令每个人都相信所有人的值之和被 整除，此时所有人都可以计算出自己的s 值。 在这一策略下，所有人猜对的概率等于所有人的值之和被 整除的概率，即s (2.2)pr()1/wins 我们把这游戏推广到一般有向图中; 设 为有向图，并把图中每一节点视为游戏参赛者。假设每一点的(,)gve 值均属于 ，其中 。对于两个节点 ，假设012.,ss2,34.,s,vwv 当 时 知道 的值，否则 不知道 的值。此时，希望所有人猜对的(,)vwvvw 概率达到最大值。 定义 2.1 设 (顶点集为 ，边集为 )为有向图，,)gve01,.nvev 记 ， ，此时映射 称为顶点 的猜测策略，其0,12.ss2:jdjfsjv 中 表示节点 的入度。并把向量函数 称之为有向图jdjv12(,.):nffs 的一个猜测策略，其中 ， ，g12(),).ncfc01,.ncc 。nv 7 易知，猜测策略的总数为 。1 njjds 定义 2.2 设 为有向图 的一个猜测策略，f(,)gve 称为猜测策略 的固定点集。ix():()ncscf 定义 2.3 称 为有向图 的猜测数，此时等号成立的猜g,maxlogi()sfs g 测策略称为最优策略，记为 ，其中 表示固定点集的顶点数。ptix() 称 为有向图 的线性猜测数，其中 表示所有(,)ali()linerl slinearfgs linearf 均为线性映射的策略。if 显然有， (2.3)g(,),lgss 下面证明上述最优策略为在合作游戏中所有人猜对的概率最大的策略。 设 为所有人的真值向量，则所有人 猜对当且仅当01,.ncc iv i,cifi(c)f(c)cfix() 因此，猜测策略 下所有人猜对的概率为 (2.4) g(,)ix()pr(|)gsnnwis 例 2.1 完全图 的猜测数为k1n ， (2.5)g(,)(,)1lnss2s 证明：首先证明 。,n 对任意 ，如果 ，则1012,.cs01,.fix()nc (2.6)12nf 因此， ，即 。()fixsg(k,)s 下面证明 。g,n 我们取如下策略 ，其中01(,.):znssff=zss 8 (2.7)0101(,.,.,)()iiniinfcccc(01)i 则 01):nfx 从而 ，即得 。 1(nisg(k,)s 例 2.2 设 为无圈有向图，则dg(,)0lds （二）网络编码与猜测数 这一节中我们将介绍网络编码与猜测数问题的对应关系。在论文3中证明 了每个网络编码问题均可转化为有向图的猜测数问题。 定义 2.4 设 给定的网络， 为编码集( )，如果利用网络编码可以实现源nsss 节点到所有汇节点的组播，则称信息流问题 可解，并把这种策略称为信息,n 流问题 的解。,s 在这一节中，我们主要考虑源节点和汇节点数相同的网络组播问题。我们 先把网络 的源节点和汇节点一一结合起来，然后由恒等映射可以得到有向图n 。例如在图 1 中，由图(a) 和(c) 以源汇节点结合的方法可以得到图(b)和(d)。g （a） (b) (c) (d) 图 1 网络编码到猜测数问题的转化 定理 2.1 3 信息流问题 的解与有向图 上成功猜测的概率至少为,nsng 的猜测策略一一对应，其中 表示有向图 的顶点数。1nnodesg nnodes n 证明：考虑有向图 (,)nve 设网络 的源节点和汇节点分别记为 和12,.ni12,.no 9 由于网络 中无圈，所以可以对中间节点定义偏序，记为n (2.8)121212.nmniino 下面考虑网络 的任意网络编码策略 12,.mfffg (2.9) 12211221121221212(,.),.(,.,.,),.,.,.(,.,.,)nmnmout noutnnmzfxzzfxgxzxxz 其中 、 和 分别表示源节点、中间节点和(1)i)iz(outi 汇节点的信息。 则与它对应的有向图 的猜测策略为 ，ng*1212,.,.mnfffg (2.10) 1122 1121211(,.,)(,.,.,)guesreallrealnlguesreallreallrealrelmnmzfxxzzfxxzz212121212,.,.,(,.,.,)guesreallreallrealrelnguesreallreallrealreln nmxxzz 显然上述策略 与 一一对应。以下证明猜测策略下猜测成功的概率为f* 当且仅当信息流问题有解。1ms 猜测成功的概率为 1ms1prms中 间 节 点 都 猜 对 信息流问题 有解。 pr(|,)guesralguesraljjiixz,ns 推论 2.2 3 源节点和汇节点数均为 的信息流问题 可解当且仅当对应的n 有向图 的猜测数满足 。ngg(,)gs 10 （三）关于猜测数的一些结论 1. 有向图的猜测数 先考虑子图和剖分图的猜测数。 定理 2.3 设 为有向图 的子图，则有hg ， (2.11)g(,)(,)sg(,)(,)llhsg2s 证明：设 和 分别为有向图 的最优猜测策略与线性猜测策略。则 和 可fl fl 视为 的猜测策略和线性猜测策略。因此，有g , 2g(,)loix()g)hsgs2()logfix(),)l lls 定理 2.4 6 设 为有向图 的子图，则有 (2.12)(,)(,)()shv 其中 表示有向图 和 的顶点之差。()vg 推论 2.5 设有向图 为由图 删除一顶点得到的图，即 ，则有ggv (2.13)g(,)(,)g(,)1ss 定理 2.6 设有向图 为由图 剖分一点得到的图，则有 (2.14)(,)(,)s 证明：设 且边 ，并设 为在图 的边 上添加一个,()uvvg,uveg(,)uv 顶点 得到的图，即 。w(), (),()wew 设 为 的最优策略。令 ，其中 和 为,.uvff,.uwvfffv (2.15)(), (.)wuvfxfx 则 为 的猜测策略，并且显然有 。gii( 因此， g(,)(,)s 反之，设 为 的最优策略。令.uwvffg (2.16)(,)(),.uvwufxfx 11 则 为有向图 的一个策略，且,.uvffg 因此， 。g(,)(,)s 故 。 g 例 2.3 设 为顶点数为 的有向圈，则有向圈的猜测数为ncn (2.17)g(,)(,)1lnssc 证明：当 时， 可以视为 的剖分图。由定理 2.3 有2m1mm ， (2.18)(,)(,)ss1(,)g(,)llmssc 而 为完全图，因此2ck (2.19)21g(,)(,).(,)nnsssc (2.20)g1ll lc 下面考虑有向图猜测数的上下界和线性猜测数的代数表示。 定理 2.7 6 设 为有向图，对 有d0,1s(2)s (2.21)()lgd 其中 表示有向图 中点不相交的圈数的最大值， 表示有向图 中把() ()d 变为无圈的最小删除边数。 定理 2.8 6 设 为有向图，则有d (2.22)g(,)max(rnk()minrak()ddl aas ii 其中 表示有向图 的邻接矩阵， 表示 阶单位矩阵， 表示当da da 时必有 。0ija0ija 2. 无向图的猜测数 我们可以把无向图视为双向边有向图、无向图的猜测数定义为对应双向边 有向图的猜测数。下面利用图论的一些概念计算猜测数的上下界。 12 定义 2.5 设 为无向图，节点集 且 ，则称(,)gvev()()ev 为图 的导出子图。如果其导出子图为完全图，则称此子图为图(, 的一个团，并记为 。()nkn 定义 2.6 若有一团集 覆盖了图 的所有边，即图 中每一条至少属| gg 于一个 ，这时我们称团集中的团的个数为团覆盖数，记为 。n cp() 定理 2.8 8 设 为无向图，对任意 有(,)gve2s (2.23)cpg(,)()gn 其中 为图 的独立数， 为图 的团覆盖数。() 13 三轮图的猜测数 （一）有向轮图的猜测数 在这一节中，我们考虑有向圈上添加一个顶点并与它连接所有顶点，这类 图定义为轮图。为了严格定义轮图，先把有向圈用数学符号来表示，其表示如 下 ，其中 ，(,)ncve0,12.n(, 1mod )|0-1eini 定义 3.1 设 为有向图，其顶点集和边集分别为(,)d ， (3.1)0,12.n 10, 1mod )|0-(, )(, )niini ni或 则称有向图 为有向轮图，并记为 。(,)ve)whelg 记 ，它表示顶点 的入出 | (1od ,), 1kinineinn 变化数。 引理 设 为有向轮图，则有()whelg (3.2)1g(),2whelgns 证明：由定理 2.5 和例 2.3 有 (3.3) (,)(),g(,)12wheln nsscc 定理 3.1 有向轮图的猜测数为 当且仅当 。gl k 证明： (必要性) 反证法：假设 ，只需证明 。2k(),2whelgns 此时，易证 为 的子图(见图 2)。(4)whelglk 14 图 2 有向轮图 (4)whelg 的邻接矩阵为(4)2whelgk (3.4)(4) 01001whelga 记 ，则 且 。 01001as(4)whelgarank()2ai 由定理 2.3 和定理 2.,8 知， (3.5)g(),g(4),g(4),rank()2whel whellwhelgnsssa (充分性) 当 时，即 n 点的出度或入度为 0。0k 删除顶点 0,则 变成有向无圈图。由推论 2.5 知， 。v()whel g(),1whelgns 因此， 。g(,=1helgs 当 时，删除顶点 ，其中 为满足 且 的点。1km(,)nme(1od,)e 则 变成有向无圈图，因此， 。()whelngwhelg 故 。 g=lg 推论 3.2 有向轮图的猜测数为 (3.6)1:g()2whel kgn当当 证明：由定理 3.2 和引理显然成立。 （二）无向轮图的猜测数 类似于有向轮图，我们可以考虑无向轮图的猜测数。 15 定义 3.2 设 为如下定义顶点集和边集的无向图，(,)dve ， ( ) (3.7)0,12.vn10, 1mod )|0-, )niini2 此时，称 为无向轮图，记为 。(,)()whelg 定理 3.3 有向轮图的猜测数为 (3.8) g(),/21 1)/2()/whellgnsn n： 当 为 偶 数当： 为 奇 数 证明：分别当 为奇数和偶数时考虑轮图的猜测数。 1. 当 为偶数时 首先， 中没有顶点数大于 3 的完全子图(团)。()whelgn 除掉顶点 之后， 中没有顶点数大于 2 的完全子图(团)。whelcn 因此， 的团覆盖数满足()whel (3.9)cp()13)/2/whelgn 而 为 的 -团覆盖。 /20,12,niin(whel/ 从而， 。cp()/whel 下面考虑 的最大独立数。lgn 由于顶点 与其他所有点都相邻，所以 的包含顶点 的独立集的顶点数()whelgnn 为 1。设 为独立集，则 。因此， ()s, 1 mod)isis都 有 。/2n 另外， 为独立集，且 。|0, 1./2in/2n 从而， 。()whelg 由定理 2.8 知， 。g(),(1)/1hels 2. 当 为奇数时n 类似于上述 为偶数的情形，分别计算团覆盖数和最大独立数。 16 中没有顶点数大于 3 的完全子图(团)，而且除掉顶点 之后()whelgn n 中没有顶点数大于 2 的完全子图(团)。lc 因此， 。()1)/1/whelnn 所以， 为最大数团覆盖，即 /20,heligi (3.10)cp()(1)/2whelgn 设 为独立集，与上述 为偶数的情形类似地可以证明()sn (3.11)/()/s 因此， ( )为最大独立集，即2|0,1.()21in2sn (3.12)/whelg 由定理 2.8 知， 。 ()/g(),()1ls 下面考虑 时任意图上加一个顶点并与此点连接所有顶点的情形。为此，2s 先规定如下符号。 设 为无向图，用 表示顶点集为 、边集为(,)gvegvvv 的无向图。|uv 定义 3.11 设 为无向图， 为无向图 的一个猜测策略，(,)f(2)s 则称 为 的共轭策略，记为 ，其中 表示 维向量。()nhxfx1 fn1 引理 ixi() 证明: 对任意 ，记 ，则有n1 (3.13)()()()n nfxxfx11 反之，当 时有， 。ixix 而且显然有 当且仅当 。因此， 。 yyi()ix()f 由引理可以知道，当 为最优策略是 也为最优策略。ff 17 定理 3.5 设 为无向图，则有(,)gven (3.14)21glo3g(,2)g(,)1ngv 证明：设 为最优策略，即 。1,.nfff 2lofix() 记 ，并称 为对称固定点集。mix()|xxm 不妨设 (否则，以最优策略 代替 )。/2 上取如下策略 ,1ngv121,.nhh 其中 ,11111(.):0(,.,.,),.,iiniinifxxhx ()in (3.15)120:f()m(,.)ixnnxx 则对 有， ，fi)x,i(h,1() 从而， 。x(2i()3f)/2h 故 。1 22g,logxlogix(log3(,)log31ngv g 例 3.1 无向轮图 的猜测数为(5)whel (3.16)2(),l51helg 证明：在文8中介绍了无向轮图 的猜测数为 ，并且最优策略为5c52g()loc ，其中 (3.17)15(,.)ff 0(,)i xyfxy当 时其 他 此时，按定理 3.5 证明构造轮图 的猜测策略，其为如下5whelg (3.18)1(,.)ff 其中 ，5150 fix(,.) ) xxfx当 当 660 ,)1i xyfy当 时否 则 表示第 ( )顶点所得到的信息。则由推论 2.5 有，6,yi (3.19)22 52log51lfixg(),2g(,)log5whelgc 18 故 。 2g(5),log1whelg 从例 3.1 可以猜想无向奇轮图的猜测数等于奇圈的猜测数加 1。 定理 3.6 无向轮图的猜测数为 (3.20) g(),/21 :g(,)whelnsgc当 为 偶 数当 为 奇 数 证明：只需证明 为奇数的情形。n 设 为奇圈 的最优策略，其中 01,.pff()nwhel1,iifx 为顶点 的局部策略。ii 下面考虑 上的策略()whelgn01(,.,npff） (3.21)1,) 3iiniifxxi , (3.22)010(,)(nfx23121(,(,)nnnnfxfx (3.23)1202)nnfx (3.24)011(,.(,nfx 则对任意 和任意 有1,.)fi)nxxp,.as (3.25)1(, 3ii iiifafx (3.26)23123212,)(,)nnnnnnfxafx (3.27)1021021(,fxaa (3.28)0 1(,.)nnnfxax 因此， ，即有121,. fi(p (3.29)i()s 从而， 。1g(),logxlogix(g(,)whelss ngn cs 由推论 2.5 有， 。 1(),(,)hel nc 19 四结束语 由于确定图的猜测数是 np-难问题，而且猜测数的研究起步比较晚，目前 还没得到一种系统有效的计算方法。2006 年 s.riis3提出猜测数问题之后， t.wu 等人从不同的角度出发研究了图的猜测数问题。他们用图的独立数、团覆 盖数和圈填充数5给出了猜测数的上下界。此外，用熵5、猜测图7和编码图 8等新的概念把猜测数问题转化为另一种问题，并且用此工具算出了一些特殊 图的猜测数。但是对很多图，特别对无向奇圈 尚未得到确切的猜测数值。21nc 目前，除了奇圈之外对其他简单图的猜测数已经得到了一定的结果，因此 我们需要考虑笛卡尔积等图的扩充图的猜测数问题， 。对于完全图、二部图、路、 有向圈和无向偶圈之间笛卡尔积的猜测数，已经得到了非常好的结论。进一步， 我们还可以考虑树、caylay 图、多部图等图和上述图之间笛卡尔积的猜测数问 题。 本文中所考虑的轮图为比较简单的扩充图，它是由一个圈添加一个顶点并 连接所有顶点得到的图。对于有向轮图和顶点数为奇数的轮图，我们在第三章 中给出了确切的猜测数，而对于顶点数为偶数的轮图，证明了其猜测数等于奇 圈的猜测数加一。 猜测数方面仍然有非常大的研究空间，本人今后也将不断开拓创新，为寻 求一个解决猜测数问题的系统有效的方法做出贡献。 20 参考文献 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. arx/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.gadou