毕业设计（论文）-中位图的测地数及其性质研究

《毕业设计（论文）-中位图的测地数及其性质研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、题目中位图的测地数及其性质研究学生姓名学号所在学院数学与计算机科学学院专业班级信息与计算科学专业1101班指导教师________完成地点___2015年5月20日第2页共13页本科毕业论文任务书院(系)数学与计算机科学学院专业班级信计1101班学生姓名一、毕业论文题目中位图的测地数及其性质研究二、毕业论文工作自2015年3月_10__日起至2014年6月20日止三、毕业论文进行地点:陕西理工学院四、毕业论文内容要求：总结中位图的有关性质及其判断方法，研究中位图的测地数及其性质．要求：（1）论文内容要条理清楚、文字表达要准确、推理过程要正确无误；（2）论文格式要按学院要

2、求的规范格式严格书写；（3）论文字数（包括符号）不少于10000字；（4）独立完成毕业论文，严禁弄虚作假和整篇抄袭他人的成果；论文的电子版必须自己动手输入文字和符号，所用的图像（或图形）也必须自己画，严禁复制粘贴他人的文字、符号和图像等．指导教师系(教研室)系(教研室)主任签名批准日期接受设计任务开始执行日期学生签名第2页共13页中位图的测地数及其性质研究(陕理工学院数学与计算机科学学院信息与计算科学专业1101班,陕西汉中X)指导教师：[摘要]在本文中考虑连通图G的g(G)与和之间的关系,还给出g(G)和相等的充分必要条件，较系统总结了Chartrand，Harary

3、和Zhang等学者的研究结论．[关键词]：中位图;测地数;测地数集;扩张;有向图Abstract:ConsidertherelationshiphereinconnectedgraphGofg(G)andbetweenandalsogiveng(G)andthenecessaryandsufficientconditionsbeingequal,thanthesystemsummarizesthefindingsChartrand,HararyandZhangandotherscholars.  Keywords:bitmap;geodeticnumber;geodet

4、icnumberset;expansion;digraph第13页共13页目录1引言52和之间的关系53的下界84图的笛卡儿积测地数105.中位图与测地数211参考文献13第13页共13页1引言凸性是几何学，拓扑学和函数分析学的基本概念[1]．设C足度量空间（x，d）的一个点集，如果对于C中任意两点x和y，连接x和y的每条测地线（最短的弧，曲线和路）完全位于C中，那么称点集C是凸的．在图论，数学的一个部门，中位图是一个无向图，其中每三个顶点的a，b，和c具有一个独特的中位数：一个顶点M（a，b，c）属于最短每对之间的路径的a，b和c。众所周知，图论中的度量空间是，这里V

5、(G)是图G的点集，d（u，v）（简记为d）是之间的最短路的边数．在Buckley和Harary所著的书[2]中，首先讨论了图的凸性；Harary和Nieminen在文献[3]做了进一步的研究．在连通图G中，子集的凸包就是包含S的最小凸集，凸包等于V(G)的最小点集的基数称为G的包数，此概念被Everett和Seidman[4]引入，相关研究见文献[5—7]．对于图G(或有向图D)的任意两点u和v，测地线是在u和v之间(或从u到v)的最短路，设是位于测地线上的所有点的集合，对于点集S，用I(S)表示所有的并，这里如果，，则点集称为图G的测地集．图G(或有向图D)的测地数

6、是G(或D)的测地集的最小基数，并且我们把这样的测地集称为最小测地集，图G的定向图是G的每一条边赋予一个方向后所得到的有向图．G的测地谱．G的下测地数，而上测地数．关于图的测地数和测地谱的概念，被文献[2，8]所引入，相关研究见文献[8—11]．本文首先讨论的问题是：对于任意图G,是否成立？一个图的测地数是否一定在它的测地谱中？我们的主要结果是：对于任意满足条件的两个正整数m和n，存在点数为n和边数为m的连通图G，使得；我们给出了的一些下界，并提出猜想：对任意图G，；还证明了g(G)和相等的充分必要条件，从而推广了文献[10]中的相关结论．由于，这里是G和H的并，因此，

7、在以下各节中我们仅考虑连通图．2和之间的关系我们先介绍证明所需要的一些概念和引理．一个有向图的源（汇）就是进度（出度）为零的点，易知下列引理：引理2.1[13]在任意图中，度为1的点属于它的任何测地集；在任意有向图中，它的源和汇属于它的任何测地集．引理2.2[8]设G是阶数至少为2的连通图，如果它的点集能分成：，使得它的每一点都在路上，其中，则．设是一条长度为k的路，和称为P的端点，而称为P的内部点．设S和T是两个不相交的子集．若u和v都属于S，则称u-v测地线是基于S上的测地线；若，则称测地线是基于S和T之间的测地线，基于S的测地线族F