南开大学数学科学学院论文.docx
- 文档编号:15901233
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:41
- 大小:472.44KB
南开大学数学科学学院论文.docx
《南开大学数学科学学院论文.docx》由会员分享,可在线阅读,更多相关《南开大学数学科学学院论文.docx(41页珍藏版)》请在冰点文库上搜索。
南开大学数学科学学院论文
(此文档为word格式,下载后您可任意编辑修改!
)
南开大学
本科生毕业论文(设计)
中文题目:
关于轮图的猜测数
外文题目:
Ontheguessingnumberofwheelgraphs
系别:
应用数学系
专业:
数学与应用数学
关于南开大学本科生毕业论文(设计)的声明
年月日
本人声明:
该学位论文是本人指导学生完成的研究成果,已经审阅过论文的全部内容,并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性。
年月日
摘要
现代社会可以说在很大程度上是通过各种网络来管理与控制的,因此用图论等数学工具分析网络问题是一项十分重要的课题。
而图的猜测数是一个研究网络编码策略的有效工具。
近年来很多学者试图利用图论、代数和信息论的方法研究图的猜测数,但目前尚未得到一种系统有效的方法来解决图的猜测数问题,特别对于无向圈的猜测数等问题目前还没有较好的结论。
因此,本文针对圈的一种扩充图即轮图的猜测数进行了研究,并得到了有向轮图和无向轮图猜测数。
关键词猜测数;轮图;独立数;团覆盖数;
Abstract
Itcanbesaidthatmodernsocietyismanagedandcontrolledwithavarietyofnetworksinalargeextent,soanalysisofnetworkproblemwithmathematicsisaveryimportanttask,whileguessingnumberisefficientinconsideringstrategyofnetworkcoding.
Inrecentyears,manyscholarstriedtodoresearchesontheguessingnumbersusingthepowerfulmathematicaltechnique,suchasgraphtheory,algebraandinformationtheory.Buttheresearchontheguessingnumbersofcircles,andgotguessingnumberofwheelgraphs.
KeyWordsguessingnumber;wheelgraphs;independencenumber;cliquecover;
目录
摘要I
AbstractII
目录III
一.引言4
二.猜测数问题的简介6
(一)猜测数问题的提出6
(二)网络编码与猜测数8
(三)关于猜测数的一些结论9
1.有向图的猜测数9
2.无向图的猜测数11
三.轮图的猜测数13
(一)有向轮图的猜测数13
(二)无向轮图的猜测数14
四.结束语19
参考文献20
致谢22
一.引言
最大流最小割定理决定了网络的最大吞吐量。
在多播通信网络中,通过网络编码可使信息传播速率达到最大值。
网络编码的诞生和发展为网络信息传输指明了一个新的研究方向。
一个通信网络由一些通信节点和连接在某些节点之间的一些通信链路组成。
网络通信的目的是要将网络中源节点产生的消息通过网络传输到汇节点。
在传统的通信网络中,信息传输采用路由的机制,每个中间节点将收到的信息传给与它相邻的下一个节点。
在2000年,A.Rhlswede等人提出了新的传输方案,让每个中间节点起到一个编码器的作用,将其收到的信息进行适当的编码后传输出去,这种方案叫做网络编码。
德国Bielefeld大学的Ahlswede教授,西安电子科技大学的蔡宁教授,以及香港中文大学的李硕彦教授和杨伟豪教授(2000)在论文“NetworkInformationFlow”IEEETransactionsonInformationTheory[2]中完全发展了网络编码的思想。
他们以著名的蝴蝶网络(ButterflyNetwork)为例阐述了网络编码的基本原理。
伦敦大学的S.Riis在2006年发表的论文“UtilizingpublicinformationinNetworkCoding”Springer[3]中首次提出了猜测数问题,并且证明了网络编码问题等价于对应有向图的猜测数问题。
并在2007年发表的论文“Informationflows,graphsandtheirguessingnumbers”ElectronicJournalofCombinations[4]中说明可以把线路复杂性理论(CircuitComplexityTheory)的核心问题和网络编码问题转化为有向图的猜测数问题。
论文中还介绍了一种特殊图叫做钟图(Clock-graphs),利用线性猜测策略求出了钟图的猜测数。
同年在论文“GraphEntropy,NetworkCodingandGuessinggames”[5]中,S.Riis借用信息论中熵的概念研究了图的猜测数问题。
这篇文章中定义了有向图的熵和几种类熵,并且证明任意图的猜测数等于其熵值,利用熵计算出有些图的猜测数(例如无向圈的猜测数与广义猜测数)。
T.Wu等人(2009)发表的论文“OntheguessingnumberofShiftgraphs”JournalofDiscreteAlgorithms[6]中应用圈填充数等概念给出了有向图猜测数的上下界,并且应用这一结论计算了一种Cayley图叫做旋转图(Shiftgraphs)[9]猜测数的上下界。
M.Gadouleau和S.Riis(2011)的论文“Graph-TheoreticalConstructionsforGraphEntropyandNetworkCodingBasedCommunications”IEEETransactionsonInformationTheory[7]中得出了如下两个结论;第一是定义任意有向图的猜测图,并且证明任意有向图的猜测数等于其猜测图的独立数的对数。
论文中利用猜测图给出几种有向图乘积[10]的猜测数和在不同编码集下猜测数之间的关系式。
第二是找出了围长为的一系列有向图使其线性猜测数与其顶点数之比趋于1。
D.Christofids和K.Markström(2011)在他们的论文“Theguessingnumberofundirectedgraphs”ElectronicJournalofCombinations[8]中专门讨论了无向图的猜测数问题,并利用无向图的(分数)团覆盖数和(分数)独立数[11]给出了无向图猜测数的上下界,证明了图的猜测数等于编码图的独立数的对数。
同时,D.Christofids和K.Markström在这篇论文中提出了奇圈的猜测数问题,即和等尚未解决的问题。
本文主要针对轮图的猜测数问题进行了研究。
首先利用论文[6,8]的结论初步计算出轮图猜测数的上下界。
其次,对于无向轮图,以构造一个猜测策略的方法得到了与奇圈猜测数的关系。
二.猜测数问题的简介
(一)猜测数问题的提出
先考虑一个合作游戏(Agameofcooperation),其规则如下:
个人掷-面骰子(其中每一面的点数分别为),然后把自己的值给别人观看。
如果所有人都猜对了自己的值,则称猜测成功,否则就算猜测失败。
在无策略的情况下,所有人猜对的概率为
(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.Riis[3]提出猜测数问题之后,T.Wu等人从不同的角度出发研究了图的猜测数问题。
他们用图的独立数、团覆盖数和圈填充数[5]给出了猜测数的上下界。
此外,用熵[5]、猜测图[7]和编码图[8]等新的概念把猜测数问题转化为另一种问题,并且用此工具算出了一些特殊图的猜测数。
但是对很多图,特别对无向奇圈尚未得到确切的猜测数值。
目前,除了奇圈之外对其他简单图的猜测数已经得到了一定的结果,因此我们需要考虑笛卡尔积等图的扩充图的猜测数问题,。
对于完全图、二部图、路、有向圈和无向偶圈之间笛卡尔积的猜测数,已经得到了非常好的结论。
进一步,我们还可以考虑树、Caylay图、多部图等图和上述图之间笛卡尔积的猜测数问题。
本文中所考虑的轮图为比较简单的扩充图,它是由一个圈添加一个顶点并连接所有顶点得到的图。
对于有向轮图和顶点数为奇数的轮图,我们在第三章中给出了确切的猜测数,而对于顶点数为偶数的轮图,证明了其猜测数等于奇圈的猜测数加一。
猜测数方面仍然有非常大的研究空间,本人今后也将不断开拓创新,为寻求一个解决猜测数问题的系统有效的方法做出贡献。
参考文献
[2]R.Ahlswede,N.Cai,N.Li,etal.Networkinformationflow.IEEETransactionsonInformationTheory,vol.46July2000.
[3]S.Riis.Utilizingpublicinformationsinnetworkcoding.GeneralTheoryofinformationTransferandCombinatorics,Springer2006.
[4]S.Riis.Informationflows,graphsandtheirguessingnumbers.ElectronicJournalofCombinatorics,14
(1)R44(2006).
[5]S.Riis.Graphentropy,networkcodingandguessinggames.arXiv.orgpdf0711.
2007.
[6]T.Wu,P.Cameron,S.Riis.Ontheguessingnumberofshiftgraphs.JournalofDisereteAlgorithms,vol7
(2)(2009).
[7]M.Gadouleau,S.Riis.Graph-theoreticalconstructionsforgraphentropyandnetworkcodingbasedcommunications.IEEETransactionsonInformationTheory,1T-57(10)(2011).
[8]D.Christofids,K.Markstrom.Theguessingnumberofundirectedgraphs.ElectronicJournalofcombinatorics,18(2011).
[9]L.Pippenger,N.Valiant.Shiftinggraphsandtheirapplications.JACM,23:
423–432,1976.
[10]W.Imrich,S.Klavzar,D.F.Rall.TopicsinGraphTheory:
GraphsandTheirCartesianProduct.AKPeters,2008,p219.
[11]E.R.Scheinerman,D.H.Ullman.Fractionalgraphtheory.JohnWiley&SonsInc,1997,p240.
[12]SunYun.NetworkCodingandGraphEntropy:
[PhDthesis].QueenMaryUniversityofLondon,2009.
[13]R.Koetter,M.Medard.Beyondrouting:
Analgebraicapproachtonetworkcoding.InProceedingsofthe2002IEEEInfocom,2002.
[14]B.E.Tarjan,A.E.Trojanowski.Findingamaxiumindependentset.SIAMJput,6(3):
1977.
[15]蒋长浩.图论与网络流.中国林业出版社.2001年,第一版,174~194.
致谢
光阴似箭,转眼间,四年的留学生活即将结束,依依不舍之情难以言表。
要感谢的人太多,要说的话也很多。
我会永远记得在南开留学的美好时光。
最后,我衷心地感谢在南开四年以来所有老师对我的大力栽培。
毕业论文通用格式分类号:
无锡职业技术学院
毕业设计(论文)
题目(团队课题要注明“团队”二字)
英文并列题目
所在团队
答辩委员会主任主答辩人
二零15年3月
毕业设计(论文)开题报告
毕业设计(论文)任务书
年月日
设计类建议格式一:
封面
开题报告
任务书
摘要、关键词(含中英文)
目录
第一章序言
1.1XXX
1.2XXX
……
第二章XXX工艺设计
2.1XXX
2.2XXX
……
第三章XXX参数确定及计算
3.1XXX
3.2XXX
……
第四章XXX夹具设计
4.1XXX
4.2XXX
……
第N-1章XXX
N-1.1XXX
N-1.2XXX
……
第N章结论
小结与致谢
参考文献
毕业设计附录目录:
1.机械加工工艺流程图
2.机械加工工艺过程卡
3.机械加工工艺工艺卡
4.机械加工工艺工序卡
5.被加工零件图
6.夹具装配图
7.夹具零件图
8.其他系统图
9.其他原理图
10.零件三维造型图
11.夹具三维造型
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 南开大学 数学 科学学院 论文