中位图的测地数及其性质研究

《中位图的测地数及其性质研究》由会员分享，可在线阅读，更多相关《中位图的测地数及其性质研究（13页珍藏版）》请在金锄头文库上搜索。

1、第 1 页 共 13 页题 目 中位图的测地数及其性质研究 学生姓名 学号 所在学院 数学与计算机科学学院 专业班级 信息与计算科学专业 1101 班 指导教师 _ _ _完成地点 _2015 年 5 月 20 日第 2 页 共 13 页本 科 毕 业 论 文 任 务 书院(系) 数学与计算机科学学院 专业班级 信计 1101 班 学生姓名 一、毕业论文题目 中位图的测地数及其性质研究 二、毕业论文工作自 2015 年 3 月_ 10_日 起至 2014 年 6 月 20 日止三、毕业论文进行地点: 陕西理工学院 四、毕业论文内容要求：总结中位图的有关性质及其判断方法，研究中位图的测地数及其性

2、质要求：（1）论文内容要条理清楚、文字表达要准确、推理过程要正确无误；（2）论文格式要按学院要求的规范格式严格书写；（3）论文字数（包括符号）不少于 10000 字；（4）独立完成毕业论文，严禁弄虚作假和整篇抄袭他人的成果；论文的电子版必须自己动手输入文字和符号，所用的图像（或图形）也必须自己画，严禁复制粘贴他人的文字、符号和图像等指 导 教 师 系 (教 研 室 ) 系(教研室) 主任签名 批 准 日 期 接 受 设 计 任 务 开 始 执 行 日 期 学 生 签 名 第 3 页 共 13 页中位图的测地数及其性质研究(陕理工学院数学与计算机科学学院信息与计算科学专业 1101 班,陕西 汉

3、中 X)指导教师：摘要 在本文中考虑连通图 G 的 g(G)与 和 之间的关系,还给出 g(G)和gG相等的充分必要条件，较系统总结了 Chartrand，Harary 和 Zhang 等学者的研究结论2gGK关键词：中位图;测地数;测地数集;扩张; 有向图 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 sy

4、stem summarizes the findings Chartrand, Harary and Zhang and other scholars.Keywords: bitmap; geodetic number; geodetic number set; expansion; digraph第 4 页 共 13 页目录1 引言 .52 和 之间的关系 .5,gGS3 的下界 .84 图的笛卡儿积测地数 .105.中位图与测地数 2 .11参考文献 .13第 5 页 共 13 页1 引言凸性是几何学，拓扑学和函数分析学的基本概念 1设 C 足度量空间（x，d）的一个点集，如果对于 C 中

5、任意两点 x 和 y，连接 x 和 y 的每条测地线（最短的弧，曲线和路）完全位于 C 中，那么称点集 C 是凸的在图论，数学的一个部门，中位图是一个无向图，其中每三个顶点的 a，b，和 c 具有一个独特的中位数：一个顶点 M（a，b，c）属于最短每对之间的路径的 a，b 和 c。众所周知，图论中的度量空间是 ，这里 V(G)是图 G 的点集，d（u，v）VGd，（简记为 d）是 之间的最短路的边数在 Buckley 和 Harary 所著的书 2中，首先讨论了uv图的凸性；Harary 和 Nieminen 在文献 3做了进一步的研究在连通图 G 中，子集的凸包就是包含 S 的最小凸集，凸包

6、等于 V(G)的最小点集的基数称为 G 的包数，SVG此概念被 Everett 和 Seidman4引入，相关研究见文献57 对于图 G(或有向图 D)的任意两点 u 和 v， 测地线是在 u 和 v 之间(或从 u 到 v)的最短路，设 是位于 测地线上的所有点的集合，对于点集 S，用 I(S)表示所有Iuv（ ， ） 的并，这里 如果， ，则点集 称为图 G 的测地（ ， ） ,IVGV集图 G(或有向图 D)的测地数是 G(或 D)的测地集的最小基数，并且我们把这样的测地集称为最小测地集，图 G 的定向图是 G 的每一条边赋予一个方向后所得到的有向图 G 的测地谱G 的下测地数 ，而上测

7、地数:SgD是 的 定 向 图 ming关于图的测地数和测地谱的概念，被文献2，8 所引入，相关研究见maxS文献8 11本文首先讨论的问题是：对于任意图 G, 是否成立？一个图的测地数是否一定在它的测地谱中？我们的主要结果是：对于任意满足条件 9492nm的两个正整数 m 和 n，存在点数为 n 和边数为 m 的连通图 G，使得 ；我gG们给出了 的一些下界，并提出猜想：对任意图 G， ；还证明了 g(G)gG 和 相等的充分必要条件，从而推广了文献10 中的相关结论2K由于 ，这里 是 G 和 H 的并，因此，在以下各节中Hg我们仅考虑连通图2 和 之间的关系,gS我们先介绍证明所需要的一

8、些概念和引理一个有向图的源（汇）就是进度（出度）为零的点，易知下列引理：引理 2.113在任意图中，度为 1 的点属于它的任何测地集；在任意有向图中，它的源和汇属于它的任何测地集引理 2.28设 G 是阶数至少为 2 的连通图，如果它的点集能分成：，使得它的每一点都在 路上，其中 ，则01,rxVyKxy0iixVr2S设 是一条长度为 k 的路， 和 称为 P 的端点，而 称为:kPvvL0vk121,kvKP 的内部点设 S 和 T 是两个不相交的子集若 u 和 v 都属于 S，则称 u-v 测地线是基于 S上的测地线；若 ，则称 测地线是基于 S 和 T 之间的测地线，基于 S 的测地,

9、u线族 F 是基于 S 上的测地线的集合，使得图 G 的每一点都位于 F 中的某条测地线上，显然，S 是的测地集的充分必要条件是存在一个基于 S 的测地线族 F引理 2.315 设 G 是一个非平凡图，S 是 G 的一个最小测地集，则对基于 S 上的测地线族 F 和 ，在 F 中都存在一个 测地线，其中 xx-uu证明 假设结论不成立，则 F 是基于 的测地族，即 是 G 的一个测地集，Sx第 6 页 共 13 页这与 S 是最小测地集矛盾现在我们来讨论具有 的图(注意 就意味着gGSgGS显然，对于 阶的图 G，有 和gG2n2,3nK，因此，若 则 在文献8中，我们知2,3nK,3K道：完

10、全图 （即在完全图中删去某条边）和完全 部图er,的测地谱都为 设 是 阶12,1212rn rrLL且 ,nT2的树，如果 有 1 个叶子（即 1 度点），那么 （见文献13和nTgl（见文献8），因此有下列结论：,Sl定理 2.415 设 G 是树 ，完全图 和完全 r-部图nTn，那么 12,1212rn rrKN且 GS下面的定理是文献8的主要结论，它是关于具有 的图 G 的存在性23,， ， n的定理 2.58 对于满足 1nm2的两个整数 m 和 n，存在一个 n 阶和 m 条边的图 G，使得 .S23n， ，因此，我们能得到下面的定理：定理 2.615 对于满足 12n的两个整数

11、 m 和 n，存在一个 n 阶和 m 条边的图 G，使得 .gS对于具有 的图，有gG2定理 2.715 如果 gS， 那 么证明 的充分必要条件是存在 ，使得 V(G)的每一点都 xyV，位于 的最短路上，这说明 V(G)可分解成 ，使得 G 中的每一点都xy 01,rK位于 的最短路上，这里 .根据引理01rxyL()ii2.2， ，因此 2SgS设 G 和 H 是两个图，u 和 v 分别是 G 和 H 中的两点，G 和 H 在点 u 和 v 的和表示为，它满足 和 ;GuvV()uVE Euv和 H 在 u 和 v 的联表示为 ，它是由 收缩边 uv 所得到的图，vouv定理 2.815 设 和 分别是两个非平凡图 G 和 H 的最小测地集，若 和 12 1S2u，则，ugg2v .证明 我们现在证明 首先证明uvg1212gGH2SSvxuvg u