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

强正则图和高效无向网络图的构造

作　者: 袁晓莉
导　师: 郭大昌
学　校: 广东工业大学
专　业: 应用数学
关键词: 强正则图谱能量超能量度直径 Cayley图 Abelian群半直积群
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 37次
引　用: 0次
阅　读: 论文下载

内容摘要

本文分为两个部分：第一个部分是对强正则图的研究，另一部分讨论的是图论群论在网络中的应用，即组合网络图论的研究。设无向图G是度为k的正则图，如果它满足：每对相邻点都有λ个共同的领域点，每对不相邻点有u个共同的领域点。我们称图G是具有参数（n，k，λ，u）的强正则图。它的特征值具有如下性质：其中有一个特征值是度数k，它的重数取决于图的连通分支数。另外两个特征值分别是方程x²-（λ-u）x-（k-u）=0的两个根为θ，T。其重数m_θ，m_T满足这样的等式：m_θ+m_T=n-1，k+m_θθ+m_TT=0．前一部分二章，主要研究结论在第二章．第二章第一节给出了强正则图的定义和简单性质．第二节首先介绍了两类简单的分类：conference图&非conference图．并分别对他们的参数的性质进行了研究，给出了conference图的充分条件．本原&非本原强正则图．发现mK_r和它的补图都是非本原强正则图，刚好mK_r的补图就是完全多部图K_m（r）．利用非本原图的性质，我们可以得到K_m（r）的谱以及它的参数．并发觉这族参数与图可以唯一相互确定．然后研究的是超能量强正则图．通过和同门的共同研究，利用超能量循环图的研究，给出了一类超能量强正则图，具有参数（4n+1，2n，n-1，n）的强正则图并在下节中列出了所有点数不超过25个的超能量强正则图．我发现可从K_m（r）构造出一种类似的图表示为K_m（r）^，它也是超能量图，并可表示为K_m和K_r直积的形式．并以图表的形式列出了所有点数不超过25个的强正则图，并对其进行研究．第三章是属于第二部分的，在这一部分本章集中讨论了构造最大的（△，D）点传递图的方法来构造高效无向网络图，其中以Cayley图为主，构造群以Abelian群，半直积群为主。

全文目录

摘要  4-5
ABSTRACT  5-7
目录  7-9
CONTENTS  9-11
第一章绪论  11-17
  1.1 研究背景和本文安排  11-13
  1.2 准备工作  13-17
    1.2.1 群论定义  13
    1.2.2 图论定义  13-17
      1.2.2.1 图  13-14
      1.2.2.2 邻接矩阵  14-17
第二章强正则图  17-31
  2.1 基本知识  17-21
  2.2 主要结论  21-31
    2.2.1 完全图K_(m(r))的谱  21-22
    2.2.2 超能量图  22-29
      2.2.2.1 超能量图K_(m(r))^  22-24
      2.2.2.2 超能量强正则图  24-29
    2.2.3 小的强正则图  29-31
第三章高效无向网络图的构造  31-37
  3.1 问题提出  31
    3.1.1 图的度和直径问题  31
    3.1.2 相关问题  31
  3.2 高效无向网络图  31-37
    3.2.1 Cayley图的特性  32-33
    3.2.2 Moore和Abelian边界问题  33-36
    3.2.3 Cayley图的构造方法(证明是点传递图)  36-37
结论  37-38
参考文献  38-41
攻读学位期间发表的论文  41-43
致谢  43

强正则图和高效无向网络图的构造

内容摘要

全文目录

相似论文