图的彩虹连通数与距离

《图的彩虹连通数与距离》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中图分类号：UDC-学校代码：10055密级：公开薏越失法博士学位论文图的彩虹连通数与距离RAINBOWCO．NNECTIONM瓜忸ERANDDISTANCEOFGRAPHS评阅人箧鍪明刻挂真闰挂墓韭独壬毖胜贵南开大学研究生院二O一三年四月南开大学学位论文使用授权书根据《南开大学关于研究生学位论文收藏和利用管理办法》，我校的博士、硕士学位获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在《著作权法》规定范围内的学位论文使用权，即：(1)学位获得者必须按规定提交学位论文(包括纸质印刷本及电子版)，学校可以采

2、用影印、缩印或其他复制手段保存研究生学位论文，并编入《南开大学博硕士学位论文全文数据库》；(2)为教学和科研目的，学校可以将公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文摘以及论文全文浏览、下载等免费信息服务；(3)根据教育部有关规定，南开大学向教育部指定单位提交公开的学位论文；(4)学位论文作者授权学校向中国科技信息研究所及其万方数据电子出版社和中国学术期刊(光盘)电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。非公开学位论文，保密期限内不向外提交和提供服务

3、，解密后提交和服务同公开论文。论文电子版提交至校图书馆网站：h堑p；丛2Q2：!!三：2Q：l互3；墨鲤!』P亟篮丛nd丛jsP。本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。作者暨授权人签字：李恒哲2013年6月7日南开大学研究生学位论文作者信息论文题目图的彩虹连通数与距离姓名李恒哲学号1120100010答辩日期2013年5月30日论文类别博士一学历硕士口硕士专业学位口高校教师口同等学力硕士口院／系／所组合数

4、学中心专业应用数学联系电话13821190201Em蚰lhz2010@mail．nankai．edu．cn通信地址(邮编)：南开大学组合数学中，心(300071)·备注：是否批准为非公开论文+否注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写(一式两份)签字后交校图书馆，非公开学位论文须附《南开大学研究生申请非公开学位论文审批表》。南开大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出

5、贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：奎垣蜇2013年6月7日非公开学位论文标注说明(本页表中填写内容须打印)根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本说明为空白。论文题目申请密级口限制(≤2年)口秘密(≤10年)口机密(≤20年)保密期限20年月日至20年月日审批表编号批准B期20年月日南开大学学位评定委员会办公室盖章(有效)注：限制★2年(可少于2年)：秘密★10年(可少于10年)：机密★20年(可少于20年)中文摘要一个交

6、互网络通常可以抽象成一个图，其中点代表开关元件或交换器，边代表通信链路。一方面，为了防止黑客入侵，人们在每个链路上设置一个密码。另一方面，为了便于管理，密码的总数要求在满足下面的条件下尽可能的少：任意两个交换器可以通过一系列密码不同的链路来交换信息。这个问题可以抽象成一个图，并且通过彩虹连通数来研究。彩虹连通数是由Chartrand等人在2008弓I入的。一个图G=(V，E)的尼．边着色是一个映射c：E寸S，其中S是一个由k种颜色组成的集合，也就是说，把G的边用k种颜色来着。通常k种颜色的集合我们取为{1，2，．．．，足)。图G是一个边着色图，其中相邻的边可以着同一种颜色，如果一条路上

7、的任意两条边的颜色不同，那么这条路称为彩虹路。图G是一个足．边着色图。如果图G的任意两个顶点之间存在一条彩虹路，那么该着色称为七．彩虹边着色。如果一个图G有一个足一彩虹边着色，那么该图是七一彩虹边连通的。一个图G的彩虹连通数rc(C)是最小的整数k使得图G有一个k．彩虹边着色。对于整数n和k，让t(n，k)表示n个顶点七．彩虹连通图的最小边数。本论文共分七章。第一章，我们首先引入彩虹连通数的定义和研究背景。然后我们纵览一下本文的主要结果。由于直