南开大学数学科学学院毕业论文

南 开 大 学

本 科 生 毕 业 论 文(设 计)

中文题目：关于轮图的猜测数

外文题目：On the gueing number of wheel graphs

学

号：0915104 姓

名：赵贤秀 年

级：2009级 学

院：数学科学学院 系

别：应用数学系 专

业：数学与应用数学 完成日期：2013年5月1号 指导教师：金应烈教授

关于南开大学本科生毕业论文(设计)的声明

本人郑重声明：所呈交的学位论文(设计)，题目《关于轮图的猜测数》是本人在指导教师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、以公开发表或没有公开发表的作品内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。

学位论文作者签名：

年

月

日

本人声明：该学位论文是本人指导学生完成的研究成果，已经审阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性。

学位论文指导教师签名：

年

月

日

摘

要

现代社会可以说在很大程度上是通过各种网络来管理与控制的，因此用图论等数学工具分析网络问题是一项十分重要的课题。而图的猜测数是一个研究网络编码策略的有效工具。

近年来很多学者试图利用图论、代数和信息论的方法研究图的猜测数，但目前尚未得到一种系统有效的方法来解决图的猜测数问题，特别对于无向圈的猜测数等问题目前还没有较好的结论。因此，本文针对圈的一种扩充图即轮图的猜测数进行了研究，并得到了有向轮图和无向轮图猜测数。

关键词 猜测数;轮图;独立数;团覆盖数;

I

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 gueing number is efficient in considering strategy of network coding.

In recent years, many scholars tried to do researches on the gueing numbers using the powerful mathematical technique, such as graph theory, algebra and information theory.But the research on the gueing 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 gueing number of wheel graphs which is a expansion of circles, and got gueing number of wheel graphs.

Key Words gueing number; wheel graphs; independence number; clique cover;

II

目

录

摘

要 .................................................................................................I ABSTRACT .......................................................................................II 目

录 ..............................................................................................III 一．引言 ............................................................................................4 二．猜测数问题的简介 ....................................................................6

（一）猜测数问题的提出 ..................................6

（二）网络编码与猜测数 ..................................8

（三）关于猜测数的一些结论 ..............................9

1.有向图的猜测数 ................................................9

2.无向图的猜测数 ...............................................11

三．轮图的猜测数 ..........................................................................13

（一）有向轮图的猜测数 .................................13

（二）无向轮图的猜测数 .................................14

四．结束语 ......................................................................................19 参考文献 ..........................................................................................20 致

谢 ..............................................................................................22

III

一． 引 言

最大流最小割定理决定了网络的最大吞吐量。在多播通信网络中，通过网络编码可使信息传播速率达到最大值。网络编码的诞生和发展为网络信息传输指明了一个新的研究方向。

一个通信网络由一些通信节点和连接在某些节点之间的一些通信链路组成。网络通信的目的是要将网络中源节点产生的消息通过网络传输到汇节点。

在传统的通信网络中，信息传输采用路由的机制，每个中间节点将收到的信息传给与它相邻的下一个节点。在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 gueing numbers”Electronic Journal of Combinations[4]中说明可以把线路复杂性理论(Circuit Complexity Theory)的核心问题和网络编码问题转化为有向图的猜测数问题。论文中还介绍了一种特殊图叫做钟图(Clock-graphs)，利用线性猜测策略求出了钟图的猜测数。

同年在论文“Graph Entropy, Network Coding and Gueing games” [5]中，S.Riis借用信息论中熵的概念研究了图的猜测数问题。这篇文章中定义了有向图的熵和几种类熵，并且证明任意图的猜测数等于其熵值，利用熵计算出有些图的猜测数(例如无向圈C5的猜测数与广义猜测数)。

T.Wu等人(2009)发表的论文“On the gueing 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]的猜测数和在不同编码集下猜测数之间的关系式。第二是找出了围长为l(l3)的一系列有向图使其线性猜测数与其顶点数之比趋于1。

D.Christofids和K.Markström(2011)在他们的论文“The gueing number of undirected graphs”Electronic Journal of Combinations[8]中专门讨论了无向图的猜测数问题，并利用无向图的(分数)团覆盖数和(分数)独立数[11]给出了无向图猜测数的上下界，证明了图的猜测数等于编码图的独立数的对数。同时，D.Christofids和K.Markström在这篇论文中提出了奇圈的猜测数问题，即g(C2k1,2)(k3)和g(C2k1,3)(k4)等尚未解决的问题。

本文主要针对轮图的猜测数问题进行了研究。首先利用论文[6,8]的结论初步计算出轮图猜测数的上下界。其次，对于无向轮图，以构造一个猜测策略的方法得到了与奇圈猜测数的关系。

二．猜测数问题的简介

（一）猜测数问题的提出

先考虑一个合作游戏(A game of cooperation)，其规则如下：

n个人掷s-面骰子(其中每一面的点数分别为0,1,....,s-1)，然后把自己的值给别人观看。如果所有人都猜对了自己的值，则称猜测成功，否则就算猜测失败。

在无策略的情况下，所有人猜对的概率为

Pr(win)1/sn (2.1) 假设每个人都知道其他n1个人的值(内部消息)。那么，我们可以采用以下策略使得上述概率达到最大值。

令每个人都相信所有人的值之和被s整除，此时所有人都可以计算出自己的值。

在这一策略下，所有人猜对的概率等于所有人的值之和被s整除的概率，即

Pr(win)1/s

(2.2) 我们把这游戏推广到一般有向图中; 设G(V,E)为有向图，并把图中每一节点视为游戏参赛者。假设每一点的值均属于S0,1,2,...,s1，其中s2,3,4,...,。对于两个节点v,wV，假设当(v,w)E时v知道w的值，否则v不知道w的值。此时，希望所有人猜对的概率达到最大值。

定义2.1 设G(V,E)(顶点集为Vv0,v1,...,vn1，边集为EVV)为有向图，记S0,1,2,...,s1，s2，此时映射fj:SdjS称为顶点vj的猜测策略，其中dj表示节点vj的入度。并把向量函数F(f1,f2,...,fn):SnSn称之为有向图G的一个猜测策略，其中F(c)(f1(c),f2(c),...,fn(c))， cc0,c1,...,cn1，nV。易知，猜测策略的总数为s

dj1nj。

定义2.2 设F为有向图G(V,E)的一个猜测策略，Fix(F){cSn:F(c)c}称为猜测策略F的固定点集。

定义2.3 称g(G,s)maxlogsFix(F)为有向图G的猜测数，此时等号成立的猜

F测策略称为最优策略，记为Fopt，其中Fix(F)表示固定点集的顶点数。 称gl(G,s)maxlogsFix(Flinear)为有向图G的线性猜测数，其中Flinear表示所有Flinearfi均为线性映射的策略。 显然有，

g(G,s)glG,s

(2.3) 下面证明上述最优策略为在合作游戏中所有人猜对的概率最大的策略。 设cc0,c1,...,cn1为所有人的真值向量，则所有人vi猜对当且仅当

\"i,ci=fi(c)ÛF(c)=cÛcÎFix(F)

因此，猜测策略F下所有人猜对的概率为 Pr(win|F)Fix(F)Snsg(G,s)n

s(2.4) 例2.1 完全图Kn(n1)的猜测数为 g(Kn,s)gl(Kn,s)n1， s2

(2.5) 证明：首先证明g(Kn,s)n1。

对任意c0,c1,...,cn2Sn1，如果c0,c1,...,cn1Fix(F)，则

cn1fn1c0,c1,...,cn2

(2.6)

因此，Fix(F)sn1，即g(Kn,s)n1。 下面证明g(Kn,s)n1。

n我们取如下策略F(f0,f1,...,fn1):ZnsZs，其中S=Zs

fi(c0,...,ci1,ci1,...,cn)(c0...ci1ci1...cn) (0in1)

(2.7) 则Fix(F)cc0,...,cn1:c0...cn10

从而Fix(F)sn1，即得g(Kn,s)n1。 例2.2 设D为无圈有向图，则g(D,s)gl(D,s)0

□

（二）网络编码与猜测数

这一节中我们将介绍网络编码与猜测数问题的对应关系。在论文[3]中证明了每个网络编码问题均可转化为有向图的猜测数问题。

定义2.4 设N给定的网络，S为编码集(Ss)，如果利用网络编码可以实现源节点到所有汇节点的组播，则称信息流问题N,S可解，并把这种策略称为信息流问题N,S的解。

在这一节中，我们主要考虑源节点和汇节点数相同的网络组播问题。我们先把网络N的源节点和汇节点一一结合起来，然后由恒等映射可以得到有向图GN。例如在图1中，由图(a)和(c)以源汇节点结合的方法可以得到图(b)和(d)。

（a）

(b)

(c)

(d)

图1 网络编码到猜测数问题的转化

定理2.1 [3] 信息流问题N,S的解与有向图GN上成功猜测的概率至少为1sGNnodesn的猜测策略一一对应，其中GNnodes表示有向图GN的顶点数。

证明：考虑有向图GN(V,E)

设网络N的源节点和汇节点分别记为i1,i2,...,in和o1,o2,...,on 由于网络N中无圈，所以可以对中间节点定义偏序，记为 i1i2...inn1n2...nmo1o2...on

(2.8)

下面考虑网络N的任意网络编码策略Ff1,f2,...,fm,g1,g2...gn

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)其中xi(1in)、zi(1im)和xiout(1in)分别表示源节点、中间节点和汇节点的信息。

则与它对应的有向图GN的猜测策略为F*f1,f2,...,fm,g1,g2...gn，

realrealz1guef1(x1real,x2,...,xn)guerealrealz2f2(x1real,x2,...,xn,z1real)............guerealrealrealrealzmfm(x1real,x2,...,xn,z1real,z2,...,zm1)xgue1g1(xreal1,xreal2,...,xrealn,zreal1,zreal2,...,zrealm) (2.10) guerealrealrealrealx2g2(x1real,x2,...,xn,z1real,z2,...,zm)............guerealrealrealrealxngn(x1real,x2,...,xn,z1real,z2,...,zm)显然上述策略F与F*一一对应。以下证明猜测策略下猜测成功的概率为1sm当且仅当信息流问题有解。

猜测成功的概率为1sm Pr中间节点都猜对1sm

realguerealx|zz,i)1信息流问题N,S有解。 Pr(xguejjii□

推论2.2 [3] 源节点和汇节点数均为n的信息流问题N,S可解当且仅当对应的有向图GN的猜测数满足g(G,s)n。

（三）关于猜测数的一些结论

1.有向图的猜测数

先考虑子图和剖分图的猜测数。 定理2.3设H为有向图G的子图，则有 g(H,s)g(G,s)，gl(H,s)gl(G,s) (s2)

(2.11) 证明：设F和Fl分别为有向图H的最优猜测策略与线性猜测策略。则F和Fl可视为G的猜测策略和线性猜测策略。因此，有

g(H,s)log2Fix(F)g(G,s),gl(H,s)log2Fix(Fl)gl(G,s) 定理2.4 [6] 设H为有向图G的子图，则有

□

g(G,s)g(H,s)V(G)V(H) (2.12) 其中V(G)V(H)表示有向图G和H的顶点之差。

推论2.5设有向图G为由图G删除一顶点得到的图，即GG\\v，则有 g(G,s)g(G,s)g(G,s)1

(2.13) 定理2.6 设有向图G为由图G剖分一点得到的图，则有

g(G,s)g(G,s)

(2.14) 证明：设u,vV(G)且边(u,v)E(G)，并设G为在图G的边(u,v)上添加一个顶点w得到的图，即V(G)V(G)w, E(G)E(G)\\(u,v)(u,w),(v,w)。

和fv为 ,fv,...，其中fw设Ffu,fv...为G的最优策略。令Ffu,fw

(xu)xu, fvfv(xw,...) fw(2.15) 则F为G的猜测策略，并且显然有Fix(F)Fix(F)。 因此，g(G,s)g(G,s)

,fv,...为G的最优策略。令 反之，设Ffu,fw

(xu),... fv(xu,...)fvfw(2.16)

则Ffu,fv...为有向图G的一个策略，且 因此，g(G,s)g(G,s)。

故g(G,s)g(G,s)。 □

例2.3 设Cn为顶点数为n的有向圈，则有向圈的猜测数为

g(Cn,s)gl(Cn,s)1

(2.17) 证明：当m2时，Cm1可以视为Cm的剖分图。由定理2.3有 g(Cm1,s)g(Cm,s)，gl(Cm1,s)gl(Cm,s)

(2.18) 而C2K2为完全图，因此

g(Cn,s)g(Cn1,s)...g(C2,s)1 gl(Cn,s)gl(Cn1,s)...gl(C2,s)1

(2.19) (2.20)

□

下面考虑有向图猜测数的上下界和线性猜测数的代数表示。 定理2.7 [6] 设D为有向图，对S0,1(s2)有 (D)gl(D,s)g(D,s)(D)

(2.21) 其中(D)表示有向图D中点不相交的圈数的最大值，(D)表示有向图D中把D变为无圈的最小删除边数。

定理2.8 [6] 设D为有向图，则有 gl(D,s)max(nrank(IA))nminrank(IA)

AADAAD(2.22)

I表示n阶单位矩阵，AAD表示当aij0时其中AD表示有向图D的邻接矩阵，D必有aij0。

2.无向图的猜测数

我们可以把无向图视为双向边有向图、无向图的猜测数定义为对应双向边有向图的猜测数。下面利用图论的一些概念计算猜测数的上下界。

定义2.5 设G(V,E)为无向图，节点集VV且E(V)E(V)(VV)，则称G(V,E(V))为图G的导出子图。如果其导出子图为完全图，则称此子图为图G的一个团，并记为Kn(nN)。

定义2.6 若有一团集Kn|nN覆盖了图G的所有边，即图G中每一条至少属于一个Kn，这时我们称团集中的团的个数为团覆盖数，记为cp(G)。 定理2.8 [8] 设G(V,E)为无向图，对任意s2有 ncp(G)g(G,s)n(G)

(2.23) 其中(G)为图G的独立数，cp(G)为图G的团覆盖数。

三．轮图的猜测数

（一）有向轮图的猜测数

在这一节中，我们考虑有向圈上添加一个顶点并与它连接所有顶点，这类图定义为轮图。为了严格定义轮图，先把有向圈用数学符号来表示，其表示如下 Cn(V,E)，其中V0,1,2,...,n1，E(i, i1 mod n)|0in-1 定义3.1 设D(V,E)为有向图，其顶点集和边集分别为

n1V0,1,2,...,n，E(i, i1 mod n)|0in-1(i, n) 或 (n, i) (3.1)

i0则称有向图D(V,E)为有向轮图，并记为Gwheel(n)。

记k{ i|(n,i)E, (i1mod n, n)E, 0in1}，它表示顶点n的入出变化数。 引理 设Gwheel(n)为有向轮图，则有

1g(Gwheel(n),s)2

(3.2) 证明：由定理2.5和例2.3有



g(,)1Gg(),C)nsg(, )Cnsw(heenls(3.3) □

定理3.1 有向轮图的猜测数为g(Gwheel(n),s)1当且仅当k1。 证明： (必要性)

反证法：假设k2，只需证明g(Gwheel(n),s)2。

此时，易证Gwheel(4)(k2)为Gwheel(n)(k2)的子图(见图2)。

图2 有向轮图Gwheel(4)

Gwheel(4)(k2)的邻接矩阵为

01000001100001001

01001010

AG(4)wheel(3.4) 01记 A00000001001101000s1，则AAG且rank(IA)2。 wheel(4)00s101由定理2.3和定理2.,8知，

 g(Gwheel(n),s)g(Gwheel(4),s)gl(Gwheel(4),s)4rank(A)2 (充分性)

(3.5) 当k0时，即n点的出度或入度为0。

V删除顶点0,则Gwheel(n)变成有向无圈图。由推论2.5知，g(Gwheel(n),s)1。

因此，g(Gwheel(n),s)=1。

当k1时，删除顶点m，其中m为满足(n,m)E且(m1modn,n)E的点。

则Gwheel(n)变成有向无圈图，因此，g(Gwheel(n))1。 故g(Gwheel(n))=1。

推论3.2有向轮图的猜测数为

1:当k1g(Gwheel(n))

2:当k2□

(3.6)

□ 证明：由定理3.2和引理显然成立。

（二）无向轮图的猜测数

类似于有向轮图，我们可以考虑无向轮图的猜测数。

定义3.2 设D(V,E)为如下定义顶点集和边集的无向图，

n1V0,1,2,...,n，E(i, i1 mod n)|0in-1(i, n)(n2) (3.7)

i0此时，称D(V,E)为无向轮图，记为Gwheel(n)。 定理3.3 有向轮图的猜测数为

(n1)/2g(Gwheel(n),s)(n1)/21 ： 当n为奇数 g(Gwheel(n),s)n/21 ： 当n为偶数(3.8) 证明：分别当n为奇数和偶数时考虑轮图的猜测数。 1.当n为偶数时

首先，Gwheel(n)中没有顶点数大于3的完全子图(团)。

除掉顶点n之后，CnGwheel(n)\\{n}中没有顶点数大于2的完全子图(团)。 因此，Gwheel(n)的团覆盖数满足

n/22cp(Gwheel(n))(n13)/21n/2

(3.9)

而{2i,2i1}{n2,n1,n}为Gi0wheel(n)的n/2-团覆盖。

从而，cp(Gwheel(n))n/2。 下面考虑Gwheel(n)的最大独立数。

由于顶点n与其他所有点都相邻，所以Gwheel(n)的包含顶点n的独立集的顶点数为1。设S (nS)为独立集，则iS, 都有i1 (mod n)S。因此，Sn/2。 另外，S{2i|i0, 1, ..., n/21}为独立集，且Sn/2。 从而，(Gwheel(n))n/2。

由定理2.8知，g(Gwheel(n),s)(n1)n/2n/21。 2.当n为奇数时

类似于上述n为偶数的情形，分别计算团覆盖数和最大独立数。

Gwheel(n)中没有顶点数大于3的完全子图(团)，而且除掉顶点n之后CnGwheel(n)\\{n}中没有顶点数大于2的完全子图(团)。 因此，Gwheel(n)(n13)/21(n1)/2。

n/22所以，Gwheel(n) {2i,2i1}{n1,n}为最大数团覆盖，即

i0cp(Gwheel(n))(n1)/2

(3.10) 设S(nS)为独立集，与上述n为偶数的情形类似地可以证明

Sn/2(n1)/2

(3.11) 因此，S{2i|i0,1,...,(n1)/21}(S(n1)/2)为最大独立集，即

(Gwheel(n))(n1)/2

(3.12)

□ 由定理2.8知，(n1)/2g(Gwheel(n),s)(n1)/21。

下面考虑s2时任意图上加一个顶点并与此点连接所有顶点的情形。为此，先规定如下符号。

设G(V,E)为无向图，用GG{v}表示顶点集为VV{v}、边集为EE(u,v)|uV的无向图。

定义3.11设G(V,E)为无向图，F为无向图G(s2)的一个猜测策略， 则称H(X)1nF(1nX)为F的共轭策略，记为F，其中1n表示n维向量。 引理 Fix(F)Fix(F)

证明: 对任意XFix(F)，记X1nX，则有 F(X)1nF(1nX)1nF(X)1nXX

(3.13) 反之，当XFix(F)时有，XFix(F)。

而且显然有XY当且仅当XY。因此，Fix(F)Fix(F)。 由引理可以知道，当F为最优策略是F也为最优策略。

□

定理3.5 设G(V,E)(Vn)为无向图，则有 g(G,2)log231g(G{vn1},2)g(G,2)1

(3.14) 证明：设Ff1,f2,...,fn为最优策略，即g(G,2)log2Fix(F)。 记MXFix(F)|F(X)X，并称M为对称固定点集。 不妨设MFix(F)/2(否则，以最优策略F代替F)。

Gvn1上取如下策略Hh1,h2,...,hn1,

fi(x1,...,xi1,xi1,...,xn):xn10其中hi(x1,...,xi1,xi1,...,xn1)

(1in),

f(x,...,x,x,...,x):x1i1i1nn1i1

0:XFix(F)\\M hn1(x1,x2,...,xn)1:XFix(F)\\M(3.15) 则对XFix(F)有，X,0Fix(H)，X,1Fix(H) 从而，Fix(H)2Fix(F)M3Fix(F)/2。

故 g(Gvn1,2)log2Fix(H)log2Fix(H)log231g(G,2)log231。□ 例3.1 无向轮图Gwheel(5)的猜测数为

g(Gwheel(5),2)log251

(3.16) 证明：在文[8]中介绍了无向轮图C5的猜测数为g(C5)log25，并且最优策略为

1 当xy0时 F(f1,...,f5)，其中fi(x,y)0 其 他 (3.17) 此时，按定理3.5证明构造轮图Gwheel(5)的猜测策略，其为如下

F(f1,...,f5,f)

(3.18) 0 当xyx6时0 当X(x1,...,x5)Fix(F)其中f(x1,...,x5)，fi(x,y,x6)

1 否 则 1 当X15XFix(F) x,y,x6表示第i(1i5)顶点所得到的信息。则由推论2.5有， log251log2Fix(F)g(Gwheel(5),2)g(C5,2)1log251

(3.19)

故g(Gwheel(5),2)log251。

从例3.1可以猜想无向奇轮图的猜测数等于奇圈的猜测数加1。 定理3.6 无向轮图的猜测数为

□

g(Gwheel(n),s)n/21 : 当n为偶数g(Gwheel(n),s)g(Cn,s)1 : 当n为奇数 (3.20) 证明：只需证明n为奇数的情形。

设Pf0,f1,...,fn1为奇圈CnGwheel(n)\\{n}的最优策略，其中fixi1,xi1

0in1为顶点i的局部策略。

下面考虑Gwheel(n)上的策略P(f0,f1,...,fn1,fn） fi(xi1,xi1,xn)fi(xi1,xi1) , 1in3

(3.21)

f0(x1,xn1,xn)f0(x1,xn1xn), fn2(xn3,xn1,xn)fn2(xn3,xn1xn) (3.22) fn1(x0,xn2,xn)fn1(x0,xn2)xn fn(x0,x1,...,xn1)fn1(x0,xn2)xn1

(3.23) (3.24)

则对任意x(x0,x1,...,xn1)Fix(P)和任意a0,1,...,s1有

fi(xi1,xi1,xn1a)fi(xi1,xi1)xi , 1in3

fn2(xn3,a,xn1a)fn2(xn3,axn1a)fn2(xn3,xn1)xn2 fn1(x0,xn2,xn1a)fn1(x0,xn2)xn1axn1xn1aa

fn(x0,x1,...,a)fn1(x0,xn2)axn1a

(3.25) (3.26) (3.27) (3.28)

因此，xx0,x1,...,xn2,a,xn1aFix(P)，即有

Fix(P)sFix(P)

(3.29)

从而，g(Gwheel(n),s)logsFix(P)1logsFix(P)1g(Cn1,s)。 由推论2.5有，g(Gwheel(n),s)1g(Cn1,s)。

□

四．结束语

由于确定图的猜测数是NP-难问题，而且猜测数的研究起步比较晚，目前还没得到一种系统有效的计算方法。2006年S.Riis[3]提出猜测数问题之后，T.Wu等人从不同的角度出发研究了图的猜测数问题。他们用图的独立数、团覆盖数和圈填充数[5]给出了猜测数的上下界。此外，用熵[5]、猜测图[7]和编码图[8]等新的概念把猜测数问题转化为另一种问题，并且用此工具算出了一些特殊图的猜测数。但是对很多图，特别对无向奇圈C2n1尚未得到确切的猜测数值。

目前，除了奇圈之外对其他简单图的猜测数已经得到了一定的结果，因此我们需要考虑笛卡尔积等图的扩充图的猜测数问题，。对于完全图、二部图、路、有向圈和无向偶圈之间笛卡尔积的猜测数，已经得到了非常好的结论。进一步，我们还可以考虑树、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 gueing numbers.Electronic Journal of Combinatorics, 14(1) R44 (2006).[5] S.Riis.Graph entropy, network coding and gueing games.arXiv.org/pdf/0711.417541, 2007.[6] T.Wu, P.Cameron, S.Riis.On the gueing 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 gueing number of undirected graphs.Electronic Journal of combinatorics, 18(2011).[9] L.Pippenger, N.Valiant.Shifting graphs and their applications.JACM, 23:423–432, 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年, 第一版, 174~194.

21

致

谢

在论文完成之际，我首先向关心帮助和指导我的指导老师金应烈教授表示衷心的感谢并致以崇高的敬意！金应烈老师作为一名优秀的、经验丰富的教师，具有丰富的数学知识和教学经验，在整个论文讨论和论文写作过程中，对我进行了耐心的指导和帮助，提出严格要求，引导我不断开阔思路，为我答疑解惑，鼓励我大胆创新，使我在这一段宝贵的时光中，既增长了知识、开阔了视野、锻炼了心态，又培养了严谨求实的治学方法和勇于探索的科研精神。值此论文完成之际，谨向我的导师致以最崇高的谢意！

光阴似箭，转眼间，四年的留学生活即将结束，依依不舍之情难以言表。要感谢的人太多，要说的话也很多。我会永远记得在南开留学的美好时光。最后，我衷心地感谢在南开四年以来所有老师对我的大力栽培。

22

南开大学生命科学学院本科生

南开大学滨海学院毕业论文

数学科学学院本科生毕业论文规范3

数学科学学院

南开大学生命科学学院研究生招生简介

地理科学学院毕业论文工作计划

徐州师大数学科学学院函授本科毕业论文要求

内蒙古师范大学数学科学学院数学与应用数学毕业论文题目

南开大学数学建模A题

数学科学学院迎新晚会策划书

《南开大学数学科学学院毕业论文.doc》

将本文的Word文档下载到电脑，方便编辑。

推荐度：

点击下载文档