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

题 目 中位图的测地数及其性质研究 学生姓名 学号 所在学院 数学与计算机科学学院 专业班级 信息与计算科学专业1101班 指导教师 _ _ _完成地点 _2015 年 5 月 20 日本科毕业论文任务书院(系) 数学与计算机科学学院 专业班级 信计1101班 学生姓名 一、毕业论文题目 中位图的测地数及其性质研究 二、毕业论文工作自 2015 年 3 月_ 10_日 起至 2014 年 6 月 20 日止三、毕业论文进行地点: 陕西理工学院 四、毕业论文内容要求：总结中位图的有关性质及其判断方法，研究中位图的测地数及其性质要求：（1）论文内容要条理清楚、文字表达要准确、推理过程要正确无误；（2）论文格式要按学院要求的规范格式严格书写；（3）论文字数（包括符号）不少于10000字；（4）独立完成毕业论文，严禁弄虚作假和整篇抄袭他人的成果；论文的电子版必须自己动手输入文字和符号，所用的图像（或图形）也必须自己画，严禁复制粘贴他人的文字、符号和图像等指 导 教 师 系(教 研 室) 系(教研室)主任签名 批准日期 接受设计任务开始执行日期 学生签名 第 2 页 共 13 页中位图的测地数及其性质研究(陕理工学院数学与计算机科学学院信息与计算科学专业1101班,陕西 汉中 723000x)指导教师： 摘要 在本文中考虑连通图g的g(g)与和之间的关系,还给出g(g)和相等的充分必要条件，较系统总结了chartrand，harary和zhang等学者的研究结论 关键词：中位图;测地数;测地数集;扩张; 有向图 abstract:consider the relationship herein connected graph g of g (g) and between and also given g (g) and the necessary and sufficient conditions being equal, than the system summarizes the findings chartrand, harary and zhang and other scholars. keywords: bitmap; geodetic number; geodetic number set; expansion; digraph目录1引言52 和之间的关系53 的下界84 图的笛卡儿积测地数105.中位图与测地数211参考文献131引言凸性是几何学，拓扑学和函数分析学的基本概念1设c足度量空间（x，d）的一个点集，如果对于c中任意两点x和y，连接x和y的每条测地线（最短的弧，曲线和路）完全位于c中，那么称点集c是凸的在图论，数学的一个部门，中位图是一个无向图，其中每三个顶点的a，b，和c具有一个独特的中位数：一个顶点m（a，b，c）属于最短每对之间的路径的a，b和c。众所周知，图论中的度量空间是，这里v(g)是图g的点集，d（u，v）（简记为d）是之间的最短路的边数在buckley和harary所著的书2中，首先讨论了图的凸性；harary和nieminen在文献3做了进一步的研究在连通图g中，子集的凸包就是包含s的最小凸集，凸包等于v(g)的最小点集的基数称为g的包数，此概念被everett和seidman4引入，相关研究见文献57对于图g(或有向图d)的任意两点u和v，测地线是在u和v之间(或从u到v)的最短路，设是位于测地线上的所有点的集合，对于点集s，用i(s)表示所有的并，这里如果，则点集称为图g的测地集图g(或有向图d)的测地数是g(或d)的测地集的最小基数，并且我们把这样的测地集称为最小测地集，图g的定向图是g的每一条边赋予一个方向后所得到的有向图g的测地谱g的下测地数，而上测地数关于图的测地数和测地谱的概念，被文献2，8所引入，相关研究见文献811本文首先讨论的问题是：对于任意图g,是否成立？一个图的测地数是否一定在它的测地谱中？我们的主要结果是：对于任意满足条件的两个正整数m和n，存在点数为n和边数为m的连通图g，使得；我们给出了的一些下界，并提出猜想：对任意图g，；还证明了g(g)和相等的充分必要条件，从而推广了文献10中的相关结论由于，这里是g和h的并，因此，在以下各节中我们仅考虑连通图2 和之间的关系我们先介绍证明所需要的一些概念和引理一个有向图的源（汇）就是进度（出度）为零的点，易知下列引理：引理2.113在任意图中，度为1的点属于它的任何测地集；在任意有向图中，它的源和汇属于它的任何测地集引理2.28设g是阶数至少为2的连通图，如果它的点集能分成：，使得它的每一点都在路上，其中，则设是一条长度为k的路，和称为p的端点，而称为p的内部点设s和t是两个不相交的子集若u和v都属于s，则称u-v测地线是基于s上的测地线；若，则称测地线是基于s和t之间的测地线，基于s的测地线族f是基于s上的测地线的集合，使得图g的每一点都位于f中的某条测地线上，显然，s是的测地集的充分必要条件是存在一个基于s的测地线族f引理2.315 设g是一个非平凡图，s是g的一个最小测地集，则对基于s上的测地线族f和，在f中都存在一个测地线，其中证明 假设结论不成立，则f是基于的测地族，即是g的一个测地集，这与s是最小测地集矛盾现在我们来讨论具有的图(注意就意味着显然，对于阶的图g，有和，因此，若则在文献8中，我们知道：完全图（即在完全图中删去某条边）和完全部图,的测地谱都为设是阶的树，如果有1个叶子（即1度点），那么（见文献13和（见文献8），因此有下列结论：定理2.415 设g是树，完全图和完全r-部图，那么下面的定理是文献8的主要结论，它是关于具有的图g的存在性的定理2.58 对于满足的两个整数m和n，存在一个n阶和m条边的图g，使得.因此，我们能得到下面的定理：定理2.615 对于满足的两个整数m和n，存在一个n阶和m条边的图g，使得.对于具有的图，有定理2.715 如果证明 的充分必要条件是存在，使得v(g)的每一点都位于的最短路上，这说明v(g)可分解成，使得g中的每一点都位于的最短路上，这里.根据引理2.2，因此设g和h是两个图，u和v分别是g和h中的两点，g和h在点u和v的和表示为，它满足和;g和h在u和v的联表示为，它是由收缩边uv所得到的图，定理2.815 设和分别是两个非平凡图g和h的最小测地集，若和 ，则，证明 我们现在证明首先证明测地线一定经过u和v，所以在测地线或测地线上的点一定位于测地线上，因为和，故s是的一个测地集，从而其次证明设是的最小测地集，其中因为测地线都经过u和v，所以和，从而和，因此.类似可证下面的定理告诉我们如何由两个较小的图构造一个较大的图g，具有：定理2.915 设g和h是两个非平凡的连通图，如果，并且和，那么证明 由于，我们可得到g的一个定向图满足和h的一个定向图h满足根据引理2.1，u属于的任意最小测地集和v属于的任意最小测地集必要时，可以反向或的每条边的方向因此，设u是g的汇和v是h的源，同时把uv定向为从u到v，就得到的定向图d.现在证明，再根据定理2.8得，于是证明了.因为和，故只要证明是d的最小测地集即可假设f是g中基于的测地线族和k是h中基于的测地线族根据引理2.3，对于，在f中存在一条测地线；对于，在k中存在一条测地线注意到位于测地线或测地线上的点一定位于测地线上显然，对于，在g中，不位于测地线上的点一定位于基于上的某条测地线上；同样，对于，在h中，不位于测地线上的点一定位于基于上的某条测地线上，因此是d的一个测地集，假设存在的一个最小测地集s，使得，令和，显然有，是g的一个测地集，是h的一个测地集，因而，要么，要么.这与或矛盾同理可证.现在考虑具有的图g由定理2.4和2.7可知：对于n阶和e(g)边的连通图g，如果，那么但是，若g具有和，则存在图g，使得如图1所示图1 在图1中，易知由引理2.1，是h的唯一测地集假设存在一个h的定向图d，使得，因为在h的任意定向图中，x，y和z一定是源或汇，故由引理2.1，是d唯一的测地集注意到x，y和z不可能都是源或汇不妨假设x是汇，y和z是源（必要时，可反向d的每条边）因为d没有其他的源和汇，所以u，v，w是进度和出度都为1的点因此在d中至多有一条测地线和测地线，从而u,v和w至少有一点不在测地线上，也不在测地线上，这与假设矛盾，这说明从图1可以得到与定理2.6相对应的定理定理2.1015 对于满足的两个正整数m和n，存在一个n阶和m条边的图g，使得证明 对于满足的两个正整数m和n，我们将对m进行归纳证明一个更一般的结论：存在一个n阶和m条边的连通图g，满足下面4个条件：在图1中的h是g的导出子图，并且在中的任一点都与x和y相邻接；和;在g中，x和x的距离不少于1，且在路上的内部点的度都是2；和.对于，图1中的h显然满足条件令，则结论也成立假设对于，结论成立即存在一个阶和条边的连通图g满足：在图1中的h是g的导出子图，并且在中的任一点都与x和y相邻接；和在g中，x和x的距离不少于1，且在路上的内部点的度都是2；和在g中，若x和x的距离大于1，则由g得到g的方法如下：(1)在g中，删去点x，同时将与x邻接的点记为x；(2)加一个仅与x和可y邻接的新点显然，所得的新图g满足条件 因为，由引理2.1知是g唯一的测地集当然存在一条基于s的测地线经过此新点，因此类似于在图1中讨论的那样，我们有，故新图g满足条件(c4)如果x和x的距离仅为1，因为g的边数为所以在中存在两个不邻接的点b和c，连接b和c就得到新图g类似地，可以验证该新图g满足条件由归纳假设知，结论成立3 的下界由上述讨论可知：对于n阶图g，有，并且有许多图可以达到这个界，如：完全图、完全r-部图和树现在我们来讨论的下界对于一个连通图g，如果h是g的一个不含奇圈的最大子图，则称h为g的最大二部子图定理3.1 15 对于n阶连通图g，若h是g的最大二部子图，则证明 显然h是g的一个生成子图，因为h是二部图，所以可以定向e(h)中的每条边，使得v(h)中的点要么是源要么是汇然后再将e(g)e(h)中的每条边任意定向加到h中，直到将e(g)e（h）中所有边加到h中为止注意，我们每加一条边到h中至多减少一个源或汇，因此.由此推出下列结果：推论3.215 g是礼阶连通图，设o(g)是g的奇圈数，则.定理3.1及其推论3.2蕴涵着上测地数)和图g中的奇圈数有关，因此当g是n阶二部图时，有显然，奇圈能达到定理3.1和推论3.2的下界假设和是两个奇圈且，则读者容易验证和在u和v的和也可以达到定理3.1和推论3.2的下界定理3.315 如果g是一个直径为d的连通图，那么.而且当且仅当g是一条路r证明 假设，其中从u(即根)开始对g进行广度搜索，得到一个以u为根的生成树t.设是在树中第i层点的集合根u是中唯一的点，v在d层中对于，要么x，y在同一层中，要么.当i为偶数时，将边xy的方向定为从x到y，其中；当i为奇数时，边xy的方向定为从y到x；对中的边任意定向，其中是的导出子图.对于g这样的定向图，它的任意一个测地集s，都有否则，假设存在某个i使得，显然，并且在中的任意点不可能位于任何一条测地线上，其中因此显然，路,的直径为n-1，并且，下面证明：如果g是n阶连通图，其直径为，那么g是路首先，断言，它与中的任意一点关联否则，设k是一个最小的数，使得和满足.显然但是，存在，使得不妨设k是奇数，象上面一样定向和之间边的方向在中与y关联的边均定向为背离y，则是源；在中与z关联的边均定向为指向z，则是汇，不论如何定向其他边，对于定向图的任意最小测地集s，都有和假设，则w邻接中的所有点由于在定向图中从w到z的距离是1，故x不在测地线上类似地，x也不在测地线上，因此，这是一个矛盾，设l是使得的最小的数，则若l不存在，则g就是若，对于上述定向图的最小测地集s，设，不妨假设l是奇数，因为y与中的所有点关联，所以y-x测地线仅经过x和y，由于x与中的所有点关联，故z-x测地线仅经过z和x，因此的其他点不在中，这是矛盾，故，即g是由定理3.3有推论3.415 如果g是一个n4阶的连通图，那么证明 若g是，则；若g的直径是1，则g是完全图，因此所以我们假设g既不是也不是设g的直径是，根据定理3.3得.文献10给出：如果g是n阶和直径为d的连通图，那么再利用定理3.3的结果可得下列结论：推论3.5 15 设g是一个n阶和直径为d的连通图，若，则4 图的笛卡儿积测地数在这一节给出与相等的充分必要条件，从而推广了文献10中的相关结论可以看成是g的2个拷贝和按下列原则构造而成：是的边，其中;同时我们称和互为对应点，文献10给出一个有用的观察：在中，如果，那么测地线完全位于中在文献10中，chartrand等证明了：如果g是非平凡的连通图，那么.同时他们也给出了g(g)和相等的一个充分条件定理4.115 设g是一个阶数至少为3的连通图，如果g包含一个含有点x的最小测地集s，使得g中的每一点都位于g中某条测地线上，其中，那么.文献10已经给出：当或3时，定理4.1的条件是充分且必要的但是，存在具有的图，它不满足定理4.1的假设条件(见文献10中的图5和图6).而当时，不知道定理4.1的条件是否是充分必要的下面将给出g(g)和相等的充分必要条件，在展示这一节的主要结果之前，我们需要介绍一些新的概念设s是g的测地集，f是基于s的测地线族，若满足下列(a1)和(a2)两个条件，则称s相对于f可分解成：(a1) 和是两个非空集合，并且和；(a2)如果存在一点不位于基于和之间的任何测地线上，那么v同时位于基于的测地线和基于的测地线上定理4.2 15 如果g是一个非平凡图，那么的充分必要条件是g中存在一个最小的测地集s和基于s的测地线族f，使得s相对于f可分解成.证明 充分性：设是由g的两个拷贝和构成的，假设s是的最小测地集，并存在基于s的测地线族f，使得s相对于f可分解成设是中对应于的点的集合，令，则.下面我们将证明是的测地集设v是g的点，若v位于测地线上，这里，则v位于测地线上，其中u是中与u的对应点由于在中，故在中与v对应的点v也位于测地线上如果v不位于基于和之间的任一条测地线上，那么由条件知v位于基于的测地线上，同时v也位于基于的测地线上，因此在中与v对应的点v位于基于的测地线上，故对于中的任意点都位于基于的测地线上所以又因为（见文献10），所以.必要性：设是的最小的测地集，这里由文献10中的观察可得，设，其中是中对应于的点的集合，因为是的测地集，所以v位于测地线上，这里若，则v位于基于的某条测地线上；不妨设，注意到在中，其中y是中与可y的对应点，因而v也位于中测地线上，故s是的测地集又因为，那么和，故条件成立，现在证明存在基于s的测地线族f，使得条件成立令f是中基于s的测地线族并满足基于和之间测地线尽可能多.如果存在点不位于f中基于和之间任一条测地线上，那么v一定位于基于的某条测地线上.我们断定与v对应的点也位于f中基于的测地线上.否则，v 位于f中基于和之间的测地线上，这说明我们能在和之间加一条新的测地线到f，中使得v位于这条新测地线上.这与f是基于和之间最多的测地线的测地线族矛盾.设基于s的测地线族f是f在中的像，因此若v不位于f中基于和之间的任一条测地线上，则v位于f中基于的测地线，也位于f中基于的测地线上故条件成立，最后，我们给出具有的图，它满足定理4.2的假设条件，但是它不满足定理4.1的假设条件(见图2).图2 在图2中，因为g含有4个1度点，即，从而，而s是g的一个测地集，故观察到s中没有点具有定理4.1的性质，现在我们说明g满足定理4.2的条件，因此.事实上，设和，中除让以u外的所有点都位于基于和之间的测地线上；而u位于测地线上，也位于测地线上5.中位图与测地数2本节中，我们证明了中位数图与测地数数字2的第二个和第三个也保持在局部立方体的更一般的情况我们先从中间图g与g（g）= 2使用外围扩展过程定理5.1. 16设g是一个中位数图，从不同然后g（g）= 2，当且仅当g可通过获得从外围扩展的序列，使得在每个外围扩展步骤凸子p上对于其中执行具有某一最小测地集合一个非空交集 证明：因为g是一个中位图，可以通过外围扩展的一个序列获得以这种方式我们得到的平均曲线图 = ，的= g，其中 = （）和是一个外围的子图对于i1，2，.，k-1假设g（g）= g（）= 2然后引理4意味着g（）= 2，由于每一非平凡图的测地数为至少2因此g（g）= g（）和具有非空交集与一些最小测地集的由定理6通过重复相同的参数的结果如下为相反的，我们使用的诱导上的外围扩展步骤的数量假设g = （h，p）通过归纳假设g（h）= 2由于p与一些最小测地集h的非空交集，说a，b，我们有一个分区s = = ab，因此g条件（h）= g（g）和g（g）= 2对于部分立方体以下两个表征与测地数2，我们将介绍两种对极顶点部分立方体而第一个类型属于偏立方体的度量性，第二个也有一个几何 avor从主要定理它将遵循，其实这两个概念相吻合设g是一个图等比例地嵌入到一个超立方体顶点u和v是在部分称为对映立方体g如果他们的距离等于多少g.的-classes 由eppstein的结果12每一个局部立方体可以等距嵌入到一个n维网格表示通过从投影到其中为z的的第个副本图的顶点g的一个投影，等距嵌入到，是一种离散区间它是集和之间的所有的正整数通过表示该区间为路径长度，我们可以解释等距嵌入到作为 一个等距嵌入的路径.笛卡尔积我们说的顶点u和v的图g说明这是等长嵌入顷对映相对于如果下面引理断言，每一个对应的一个副本中只有一个单位区间引理5.2. 16设g是一个局部的立方体图，等距嵌入到，让ab，x ye（g）然后，abx y并且仅当存在使得的证明：假设网络首先是和是图g的边缘这是在关系由于g被嵌入等距进入存在一个唯一索引我这样和对于所有.我们可以假设没有损失一般性的那个中，且x（这意味着自abx y）由于g是等距，g中的顶点之间的距离对应的距离，从它们的嵌入坐标导出因此，因为x，我们得出通过一个类似的参数由于| | = 1，我们得到和中为相反的，假定ab和x y是边缘，使得存在一个索引i的那么显然与对于所有在下面的等式，我们表示了个协调顶点v的： 其中中间排等式由=0通过争论以同样的方式，我们也从中获得d（b，x）=d（a，x）+1因此d（a，y）+ d（b，x）=2 + d（b，y）+ d（a，x），所以ab x y引理5.3 16.假设连接一个边e的端部顶点但不包含它包含了一个边缘的， 引理5.4 16.令p是在中位数为图g则p的路径是一个测地数线，当且仅当所有在p横亘在两两分开-classes边缘 定理5.5 16.设g是一个局部的立方体，从不同那么下面断言是等价的： （）g（g）=2; （）存在顶点a和b是对映在部分立方体g组; （）g可等距嵌入到的这样一种方式，存在对映顶点a和b相对于的证明： （）（ii）：假设g是用g（g）= 2的局部立方体和令s = a，b是最小测地集首先，我们权利要求，对于每个，有一个a，b-测地数包含在f.边缘让u和v是相邻顶点和u vf.自a，b是测地数测量组，u和v两者必须位于最短路径间a和b如果它们位于在相同的a，b-测地数线则显然也边缘外于它现在考虑的情况下，当u和v趴在不同的a，b-测地线让q和r是这些测地线的部分从a到u和从a到v，分别再由q或r包含的边缘f和证明 若g仅包含一个a，b-测地数线，然后由权利要求这个测需要包含在每个的边缘现在，假设任意f边缘uv位于一个的a，b-测地数线而且，还有另一种的a，b-测地数线没有边缘uv的，并连同是连接顶点u和v因此，通过本步行包含随e边e是测地数，e可以证明，从而e包含在我们得出的任何的a，b-测地数线包含来自每个边缘a和b是对应在局部立方体g. （）（iii）：由于g是一个局部立方体，我们从eppstein的定理使得g可以等距嵌入到导出路径的笛卡尔乘积1，2，.，n，其中二是一个路径的长度我让a和b是在对映的顶点局部cubeg，即dg的（a，b）等于-classes ing.by引理12we推断dg的数（a，b）= d1 + d2 + . + dn，暗示a和b是对映相对于zn （）（i）：假设一个非平凡局部立方体g达到等距嵌入到个这样的方式，存在顶点a和b是对映相对于令b =很显然，每个b的顶点从而得到每个顶点位于一些的a，b-测地数线的b.由于g是b的等距子图，对于每一个xv（g），我们有这意味着存在a和b之间在g中经过x的最短路径因而a，b是最小测地集并证明是完整 表征的几何解释（三）以上是部分立方体g有测地数集合a，b当且仅若g可等距嵌入到中，在的方块得到顶点的凸闭合这样的方式a和b中包含整个g.参考文献1 bonnesens t, fenchel w. theorie der konvexen korper. berlin: springer, 19342 buckley f, harary f. distance in graphs. redwood city, ca: addison-wesley, 19903 harary f, nieminen j. convexity in graph. j differential geom, 1981, 16: 185-1904 everett m g, seidman s b. the hull number of a graph, discrete math, 1985, 57: 185-1905 chartrand g, harary f, zhang p. on hull number of a graph. ars combin, 2000, 20: 181-1896 chartrand g, zhang p. the forcing hull number of a graph. j co