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

图的超级限制边连通性和边连通度的下界

作　者: 吴丽鸿
导　师: 王世英
学　校: 山西大学
专　业: 应用数学
关键词: 网络限制边连通度超级限制边连通性直径下界
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 31次
引　用: 0次
阅　读: 论文下载

内容摘要

多处理机系统的互连网络拓扑通常以（有向或无向）图为数学模型．设G是无向简单连通图，F是G的一个边割，如果G-F不含孤立点，则称F是G的一个限制边割．最小限制边割所含的边数称为G的限制边连通度．限制边连通度作为边连通度的推广，是计算机互连网络可靠性的一个重要度量．超级限制边连通性是比限制边连通度更精确的一个网络可靠性指标．一个图是超级限制边连通的，如果它的任一最小限制边割都孤立一条有最小边度的边．本文主要研究了直径为2的图的超级限制边连通性和有向图的边连通度的下界．在第一章第一节我们给出本文将用到的图论方面的术语、记号．在第二节我们介绍了关于边连通性方面的基本概念和基本结论．本文第二章研究了几类直径为2的图的超级限制边连通性．在第一节我们给出后文将要用到的几个简单事实，并简略总结了直径为2的图的连通性方面的已有结论．在第二节，直径为2的图为超级限制边连通的几个充分条件被给出，具体是：（1）设G是阶为v（≥4）的一个图．若对G的任意一对不相邻顶点x，t，都有|N（x）∩N（y）|≥3；对任意一对相邻的点u，v，都有|N（u）∩N（v）|≥2，那么图G是超级限制边连通的，除非G属于一类特殊的图．（2）设G是阶为v（≥4）的一个图．若对图G的任意一对不相邻顶点u，v满足G[M（u）∩N（v）]中至少包含三条边，那么图G是超级限制边连通的，除非G属于一类特殊的图．（3）设G是阶为v（≥13）的一个图．若对G中的任意两个不相邻的顶点u，v，有|N（u）∩N（v）|≥3且最小边度ξ（G）≤（?）v/2」+2，则图G是超级限制边连通的．（4）设G是阶为v（≥10）的一个图且最小度δ（G）≥3．若对它的任意两个相邻顶点x，y，有|N（x）∩N（y）|≤1；对它的任意两个不相邻顶点u，v，有|N（u）∩N（v）1≥2，则G是超级限制边连通的．本文第三章研究了有向图，定向图，定向二部图的边连通度的下界．结论如下：（5）设D是阶为v（≥4）的一个强连通有向图，边连通度为λ（D），最小度为δ（D），最小弧度为ξ（D）．若λ（D）<δ（D），则（6）设D是阶为v（≥6）的一个强连通定向图，边连通度为λ（D），最小度为δ（D），度序列为d₁≥d₂≥…≥d_v．若λ（D）≤δ（D）-k（1≤k≤δ（D）且k为整数），则（7）设D是阶为v（≥6）的一个强连通定向二部图，边连通度为λ（D），最小度为δ（D），度序列为d₁≥d₂≥…≥d_v．若λ（D）≤δ（D）-k（1≤k≤δ（D）且k为整数），则

全文目录

中文摘要  6-8
英文摘要  8-10
引言  10-11
第一章预备知识  11-14
  §1.1 图论的有关术语、符号  11-12
  §1.2 边连通性方面的基本概念和基本结论  12-14
第二章直径为2的图的超级限制边连通性  14-33
  §2.1 相关结论  14-15
  §2.2 主要结果  15-33
第三章有向图的边连通度的下界  33-37
结论  37-38
参考文献  38-40
发表文章  40-41
致谢  41-42
个人简况  42-43

图的超级限制边连通性和边连通度的下界

内容摘要

全文目录

相似论文