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

来源 :山西大学 | 被引量 : 0次 | 上传用户:toneygao
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
无向图G中两点u,v之间的距离是G中最短的(u,v)路的长.无向图G的直径是指G中任意两个顶点之间距离的最大者.类似地,有向图D中点u到点v的距离指u到v的最短路的长度.另外,Chartrand et al.定义了有向图D中两个点u,v之间的强距离sd(u,v)是包含u,v的D的强连通子图的最小弧数.有向图D中点v的强偏心距se(v)定义为v到V(D)中任意一点的强距离的最大值.有向图D的强直径指D中任意一个点强偏心距的最大值,类似地,有向图D的强半径指D中任意一个点强偏心距的最小值.给定一个无向图G,将G的每条边{x,y}用弧xy或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=C(2)3,那么sdiam(G)=srad(G).(2)令G=C(2)4,那么sdiam(G)=srad(G).(3)设H是4圈添加弦后构成的弦图,令G=H(2),那么sdiam(G)=srad(G).
其他文献
本文主要研究了分数维拉普拉斯型Hénon型方程基态解(又称最低能量解)的存在性与部分Hénon型方程组基态解的渐近性.全文共分四章.   在第一章中,我们介绍了分数维拉普拉斯型
零和问题主要研究对象是有限Abel群上的零和序列.在研究零和问题时,常常考虑的是加法群。Davenport常数是零和理论发展的起点之一,对零和理论的发展也有很重要的意义,本文许多问
本文的第二章利用经验似然方法研究了响应变量在随机缺失(MAR)机制下,线性回归模型中当协变量随机时误差方差的经验似然估计.在一定条件下,证明了该估计的渐近正态性,且得出了误差e的分布不对称时,该估计的渐进方差比传统最小二乘估计的渐近方差小.本文的第三章构造了未利用附加信息以及利用附加信息时,线性回归模型中当协变量随机时误差方差的经验似然比统计量,并且证明了上述两种似然比统计量的渐近分布为X2分布,
学位
非负矩阵分解算法(NMF)是一种无监督模式识别.将该算法应用在核磁共振数据处理中,NMF对因子矩阵进行随机初始化会造成解不稳定的问题,在实际应用中常常需要进行多次实验,然后找
分布参数控制系统的状态空间是一个无限维空间,系统在每一瞬间的状态是一个函数,因而分布参数系统的应用面更广,研究时所用的数学工具更复杂.近年来,分布参数控制系统理论已成为
据了解,乌干达卡万达国家农业研究实验室的研究人员已筛选出抗枯萎病、线虫及象鼻虫的香蕉新品种。近10多年来细菌性枯萎病一直威胁着乌干达香蕉产业,有的果园甚至遭受毁灭性
公共物品对策是经济学中一个重要研究领域,社会网络的结构性和地域性都会影响公共物品提供的动机。社会中的每个个体做出决策时都会被他的邻居或朋友所影响。论文介绍了近几年
本文研究了二阶周期哈密顿系统在原点附近的多解问题,共分三章.   在第一章中,我们主要介绍了哈密顿系统研究的历史背景与相关成果,阐述了寻找周期解时所遇到的困难以及克服
20世纪60年代中期,在中国发行了一本小红书——《毛主席语录》,它的发行速度  之迅猛,发行量之大,近乎一夜之间攀居世界之首。据报载,仅“文化大革命”几年之内,国内就出版了30多种文字,500多种版本,总印数以亿计算。以“毛主席语录”为主体,在中国大地掀起的浩瀚的红色海洋呼啸澎湃。大街小巷几乎所有的建筑物,里里外外必须悬挂大红色的“毛主席语录”牌。  军队是红海洋的源头,《毛主席语录》的发源地,因
腐败,古已有之,“亚腐败”属新名词。“亚腐败”,有关专家这样解释:一些党员干部的不良行为虽还不到腐败那个火候,但已接近腐败的边缘,再发展下去,就和腐败接轨了。也就是思