一． 引 言
最大流最小割定理决定了网络的最大吞吐量。在多播通信网络中，通过网络编码可使信息传播速率达到最大值。网络编码的诞生和发展为网络信息传输指明了一个新的研究方向。
一个通信网络由一些通信节点和连接在某些节点之间的一些通信链路组成。网络通信的目的是要将网络中源节点产生的消息通过网络传输到汇节点。
在传统的通信网络中，信息传输采用路由的机制，每个中间节点将收到的信息传给与它相邻的下一个节点。在2000年，A.Rhlswede等人提出了新的传输方案，让每个中间节点起到一个编码器的作用，将其收到的信息进行适当的编码后传输出去，这种方案叫做网络编码。
1999年，香港中文大学的杨伟豪教授和美国南加州大学的张箴教授在一篇关于卫星通信网络的学术论文“Distributed Source Coding for Satellite Communications”IEEE Transcations on Information Theory[1]中首次提出了网络编码(Network coding)的概念。
德国Bielefeld大学的Ahlswede教授，西安电子科技大学的蔡宁教授，以及香港中文大学的李硕彦教授和杨伟豪教授(2000)在论文“Network Information Flow” IEEE Transactions on Information Theory[2]中完全发展了网络编码的思想。他们以著名的蝴蝶网络(Butterfly Network)为例阐述了网络编码的基本原理。
伦敦大学的S.Riis在2006年发表的论文“Utilizing public information in Network Coding” Springer[3]中首次提出了猜测数问题，并且证明了网络编码问题等价于对应有向图的猜测数问题。并在2007年发表的论文“Information flows, graphs and their guessing numbers”Electronic Journal of Combinations[4]中说明可以把线路复杂性理论(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 Algorithms[6]中应用圈填充数等概念给出了有向图猜测数的上下界，并且应用这一结论计算了一种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 Combinations[8]中专门讨论了无向图的猜测数问题，并利用无向图的(分数)团覆盖数和(分数)独立数[11]给出了无向图猜测数的上下界，证明了图的猜测数等于编码图的独立数的对数。同时，D.Christofids和K.Markstr?m在这篇论文中提出了奇圈的猜测数问题，即和等尚未解决的问题。
本文主要针对轮图的猜测数问题进行了研究。首先利用论文[6,8]的结论初步计算出轮图猜测数的上下界。其次，对于无向轮图，以构造一个猜测策略的方法得到了与奇圈猜测数的关系。
二．猜测数问题的简介
（一）猜测数问题的提出
先考虑一个合作游戏(A game of cooperation)，其规则如下：
个人掷-面骰子(其中每一面的点数分别为)，然后把自己的值给别人观看。如果所有人都猜对了自己的值，则称猜测成功，否则就算猜测失败。
在无策略的情况下，所有人猜对的概率为
(2.1)
假设每个人都知道其他个人的值(内部消息)。那么，我们可以采用以下策略使得上述概率达到最大值。
令每个人都相信所有人的值之和被整除，此时所有人都可以计算出自己的值。
在这一策略下，所有人猜对的概率等于所有人的值之和被整除的概率，即
(2.2)
我们把这游戏推广到一般有向图中;
设为有向图，并把图中每一节点视为游戏参赛者。假设每一点的值均属于，其中。对于两个节点，假设当时知道的值，否则不知道的值。此时，希望所有人猜对的概率达到最大值。
定义2.1 设 (顶点集为，边集为)为有向图，记，，此时映射称为顶点的猜测策略，其中表示节点的入度。并把向量函数称之为有向图的一个猜测策略，其中，，。
易知，猜测策略的总数为。
定义2.2 设为有向图的一个猜测策略，称为猜测策略的固定点集。
定义2.3 称为有向图的猜测数，此时等号成立的猜测策略称为最优策略，记为，其中表示固定点集的顶点数。
称gl(G,s)?maxlogsFix(Flinear)为有向图的线性猜测数，其中表示所有均为线性
Flinear映射的策略。 显然有，
(2.3)
下面证明上述最优策略为在合作游戏中所有人猜对的概率最大的策略。 设为所有人的真值向量，则所有人猜对当且仅当
\i,ci=fi(c)?F(c)=c?c?Fix(F)
因此，猜测策略下所有人猜对的概率为
Pr(win|F)?Fix(F)Snsg(G,s)?n
s(2.4)
例2.1 完全图的猜测数为
证明：首先证明。 对任意，如果，则
因此，，即。 下面证明。
我们取如下策略，其中
(2.6)
，
(2.5)
fi(c0,...,ci?1,ci?1,...,cn)??(c0?...?ci?1?ci?1?...?cn)
(2.7)
则Fix(F)??c??c0,...,cn?1?:c0?...?cn?1?0? 从而，即得。
□
例2.2 设为无圈有向图，则
（二）网络编码与猜测数
这一节中我们将介绍网络编码与猜测数问题的对应关系。在论文[3]中证明了每个网络编码问题均可转化为有向图的猜测数问题。
定义2.4 设给定的网络，为编码集()，如果利用网络编码可以实现源节点到所有汇节点的组播，则称信息流问题可解，并把这种策略称为信息流问题的解。
在这一节中，我们主要考虑源节点和汇节点数相同的网络组播问题。我们先把网络的源节点和汇节点一一结合起来，然后由恒等映射可以得到有向图。例如在图1中，由图(a)和(c)以源汇节点结合的方法可以得到图(b)和(d)。
（a）
(b)
(c)
(d)
图1 网络编码到猜测数问题的转化
定理2.1 [3] 信息流问题的解与有向图上成功猜测的概率至少为的猜测策略一一对应，其中表示有向图的顶点数。 证明：考虑有向图
设网络的源节点和汇节点分别记为和
由于网络中无圈，所以可以对中间节点定义偏序，记为
i1?i2?...?in?n1?n2?...?nm?o1?o2?...?on
(2.8)
下面考虑网络的任意网络编码策略
z1?f1(x1,x2,...,xn)z2?f1(x1,x2,...,xn,z1)..........zm?f1(x1,x2,...,xn,z1,z2,...,zm?1)x1out?g1(x1,x2,...,xn,z1,z2,...,zm)outx2?g2(x1,x2,...,xn,z1,z2,...,zm) (2.9)
..........outxn?gn(x1,x2,...,xn,z1,z2,...,zm)其中、和分别表示源节点、中间节点和汇节点的信息。 则与它对应的有向图的猜测策略为F*??f1,f2,...,fm,g1,g2...gn?，
realrealz1guess?f1(x1real,x2,...,xn)guessrealrealz2?f2(x1real,x2,...,xn,z1real)............
guessrealrealrealrealzm?fm(x1real,x2,...,xn,z1real,z2,...,zm?1)xguess1?g1(xreal1,xreal2,...,xrealn,zreal1,zreal2,...,zrealm) (2.10)
guessrealrealrealrealx2?g2(x1real,x2,...,xn,z1real,z2,...,zm)............guessrealrealrealrealxn?gn(x1real,x2,...,xn,z1real,z2,...,zm)
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库(最新版)南开大学数学科学学院毕业论文(2)在线全文阅读。
相关推荐：