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

有向图连通度的下界

作　者: 杨开云
导　师: 王世英
学　校: 山西大学
专　业: 应用数学
关键词: 定向图有向二部图度序列连通度边连通度
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 11次
引　用: 0次
阅　读: 论文下载

内容摘要

多处理机系统的互联网拓扑通常以有向图或无向图为数学模型,用（有向图或无向图）中的顶点集来表示多处理机系统中的所有处理机,用边集或弧集来表示系统中处理机之间的通信线路.对互联网的性能一个关键要求是希望网络的可靠性（容错性）好,这对应于图论的术语来说,就是希望图的连通度和边连通度尽可能的大.在第一章第一节,我们给出本文将用到的图论方面的主要术语、记号.在第二节,我们介绍了本文将要用到的基本的概念和结论.本文第二章的主要研究了一类特殊的有向图-定向图连通度的下界,给出了定向图、定向二部图的连通度的下界:（1）设D是一个n阶定向图,连通度为κ,度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ.且k为整数）,则（2）设D是一个n阶定向二部图,连通度为κ,度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则（3）设D是一个团数ω（D）≤p的n阶定向图,连通度为κ,它的度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则第三章主要是给出了有向图连通度的下界:（1）设D是一个n阶的有向图,连通度为κ,它的度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则（2）设D是一个n阶有向二部图,连通度为κ,它的度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则第四章主要研究了有向图边连通度的下界:（1）设D是一个团数为ω（D）≤p的n阶定向图,边连通度为λ,最小度为δ,度序列为（d₁,d₂,…,d_n）.若λ＜δ,则（2）设D是一个n阶有向图,边连通度为λ,最小度为δ,度序列为（d₁,d₂,…,d_n）.若λ＜δ,则

全文目录

中文摘要  6-8
英文摘要  8-10
引言  10-12
第一章预备知识  12-15
  1.1 图论的有关术语、符号  12-13
  1.2 基本概念和结论  13-15
第二章定向图连通度的下界  15-23
第三章有向图连通度的下界  23-30
第四章有向图边连通度的下界  30-33
结束语  33-34
参考文献  34-36
发表文章目录  36-37
致谢  37-38
个人简况  38-39

有向图连通度的下界

内容摘要

全文目录

相似论文