学位论文 > 优秀研究生学位论文题录展示

几类有向图的强直径和强半径

作　者: 武艳艳
导　师: 杨爱民
学　校: 山西大学
专　业: 应用数学
关键词: 顶点扩张图强定向强直径强半径
分类号: O157.5
类　型: 硕士论文
年　份: 2013年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

无向图G中两点u,v之间的距离是G中最短的(u,υ)路的长.无向图G的直径是指G中任意两个顶点之间距离的最大者.类似地,有向图D中点u到点υ的距离指让到υ的最短路的长度.另外Chartrand et al定义了有向图D中两个点u υ之间的强距离sd(u.υ)是包含u,v的D的强连通子图的最小弧数.有向图D中点υ的强偏心距se(υ)定义为υ到V(D)中任意一点的强距离的最大值.有向图D的强直径指D中任意一个点强偏心距的最大值,类似地,有向图D的强半径指D中任意一个点强偏心距的最小值.给定一个无向图G,将G的每条边{χ,y}用弧χy或yx替代后得到的有向图称为G的定向图.若连通图G在定向后是强连通的,则称该定向为G的强定向.使得G的所有定向图中强直径最大的定向称为G的最大强直径定向,其最大强直径记为SDIAM(G)在G的所有可能的强定向中,强直径最小的定向称为G的最小强直径定向,其最小强直径记为sdiam(G)同理,强半径的定向类似.对于无向图和有向图的直径,许多学者已经研究得出大量结果.对于有向图而言,有关强直径和强半径概念的提出较迟,而且关于其研究结果的文献还很少,因而研究难度也较大.本文主要研究了几个特殊有向图的强直径及其强半径的界.本文分为四章,主要内容如下：第一章是预备知识,介绍了一些本文中将要用到的图论方面的基本概念和术语.第二章简要介绍了关于强直径和强半径目前的研究结果.第三章的第一部分首先讨论了圈的2顶点扩张图的最大强直径的界,并有如下结论：设H是阶n≥3的圈.令G=H(2),则有不等式SDIAM≥n+2特别地研究了奇圈的2顶点扩张图的最小强直径的定向.得到如下结论：设H是阶n>3的圈,其中n为奇数.令G=H(2).则有结果sdiam(G)≤n第二部分首先讨论了5圈添加弦后构成的弦图的2顶点扩张图的最小强直径的一个上界,并有如下结论：5圈添加弦构成的弦图记为H,令G=H(2),则有sdiam(G)≤5接着讨论了6圈添加弦后构成的弦图的2顶点扩张图的最小强直径的一个上界,并成立结论：6圈添加弦构成的弦图记为H,令G=H(2),则有sdiam(G)≤6一般地,将n圈添加弦构成的弦图记为H,令G=H(2).则有sdiam(G)≤n.第四章则讨论了最小强直径与最小强半径相等的特殊图类.主要结果如下：(1)令G=C3(2),那么sdiam(G)=srad(G).(2)令G=C4(2)那么sdium(G)=srad(G).(3)设H是4圈添加弦后构成的弦图,令G=H(2),那么sdiam(G)=srad(G).

全文目录

摘要  6-8
ABSTRACT  8-10
引言  10-12
第一章预备知识  12-14
第二章有向图的强直径和强半径的相关结果  14-16
第三章圈和弦图的2顶点均匀扩张图的强直径的界  16-28
第四章最小强直径等于最小强半径的一些特殊图类  28-33
结论  33-34
参考文献  34-37
发表文章目录  37-38
致谢  38-39
个人简况及联系方式  39-41

几类有向图的强直径和强半径

内容摘要

全文目录

相似论文