广义b-基超立方体的控制参数及其圈积的Hamilton分解

论文摘要

互连网络是超级计算机的重要组成部分,其拓扑结构是指超大规模计算机系统中的元件（处理器）的连接模式.实际上,互连网络的拓扑结构就是图.互连网络的结构和性质是超级计算机研究的重要课题.在设计和选择互连网络的拓扑结构时,顶点度,Hamilton性,连通度,直径等指标对分析网络性能方面发挥了重要作用.本文讨论了广义b-基超立方体网络GCn（b）的控制数,乘积图GCn（b）×H的控制数,广义b-基超立方体网络GCn（b）的全控制数、独立控制数、连通控制数、完美控制数以及符号控制数与反符号控制数,笛卡尔乘积网络GCn（b）× Cm1 ×Cm2×2 ×…× 的Hamilton分解.主要结果如下:1.1993年,S.Lakshmivarahan,J.S.Jwo,S.K.Dhall 首次提出了著名的互连网络—广义b-基超立方体网络GCn（b）.在本文中（1）给出了当1<n≤5,b =3;1<n ≤ 3,b = 4时,广义b-基超立方体网络的控制数的具体值,以及当n ≥5,b = 3;n ≥ 4,b = 4时,广义b-基超立方体网络的控制数的界;（2）给出了当1<n ≤ 5,b=3;1<n≤3,b=4时,广义b-基超立方体网络的全控制数的具体值,以及当n≥6,b=3;n ≥4,b=4时,广义b-基超立方体网络的全控制数的界;（3）给出了当1<n≤5,b=3;1<n ≤ 3,b=4时,广义b-基超立方体网络的独立控制数的具体值,以及当n ≥4,b= 3;b=4时,广义b-基超立方体网络的独立控制数的界;（4）给出了当1<n≤ 4,b=3时,广义b-基超立方体网络的连通控制数的具体值,以及当5 ≤ n≤ 7,b=3时,广义b-基超立方体网络的连通控制数的界;（5）给出了当1<n≤4,b=3时,广义b-基超立方体网络的完美控制数的具体值,以及当n≥ 5,b=3时,广义b-基超立方体网络的完美控制数的界;（b）给出了当2 ≤n≤4,b=3;n=2,b=4时,广义b-基超立方体网络的符号控制数和反符号控制数的具体值,以及当n≥2,b=3;n ≥n≥2,b=4时,广义b-基超立方体网络的符号控制数和反符号控制数的界,并且给出了当n ≥ 2,b ≥ 3时,广义b-基超立方体网络的反符号控制数的界.2.19b3年,Vizing提出著名Vizing猜想:对任何两个图G和H,均有:γ（G ×H）≥γ（G）γ（H）.师海忠认为GCn（b）满足Vizing猜想.在本文中,证明了当1≤n≤6,b=2,3 时,GCn（b）满足Vizing猜想.3.师海忠设计了笛卡尔乘积网络GC×(Gm1 C× Gm2 ×…× Gmq,且提出如下猜想:笛卡尔乘积网络GCn（b）× Gm1 × Cm2×…×Cmq 是Hamilton可分解的,其中,GCn（b）是广义b-基超立方体,Cmj是mj长圈,j = 1,2,…,q.在本文中,证明了当 n = 1,1 ≤ b ≤ 6,q = 1,m1 =3,4;n=2,b = 2,3,q = 1,m1 =3,4 时,GCn（b）× Gm1 是Hamilton分解的.

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景
•   1.2 本文的主要工作
• 第2章 基本知识
•   2.1 图论的有关术语及重要定义
•   2.2 乘积图的概念
•   2.3 广义b-基超立方体的概念
•   2.4 控制参数的概念
• 第3章 广义b-基超立方体的点控制
• n（b）的基本性质'>  3.1 GC_n（b）的基本性质
• n（b）的控制数'>  3.2 GC_n（b）的控制数
• n（b）×H的控制数'>  3.3 乘积图GC_n（b）×H的控制数
• 第4章 广义b-基超立方体的另四类控制
• n（b）的全控制数'>  4.1 GC_n（b）的全控制数
• n（b）的独立控制数'>  4.2 GC_n（b）的独立控制数
• n（b）的连通控制数'>  4.3 GC_n（b）的连通控制数
• n（b）的完美控制数'>  4.4 GC_n（b）的完美控制数
• 第5章 广义b-基超立方体的符号控制与反符号控制
• n（b）的符号控制数'>  5.1 GC_n（b）的符号控制数
• n（b）的反符号控制数'>  5.2 GC_n（b）的反符号控制数
• n（b）×C_m的Hamilton分解'>第6章 GC_n（b）×C_m的Hamilton分解
• n（b）×C₃的Hamilton分解'>  6.1 GC_n（b）×C₃的Hamilton分解
• n（b）×C₄的Hamilton分解'>  6.2 GC_n（b）×C₄的Hamilton分解
• 第7章 结束语
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢

文章来源

类型: 硕士论文

作者: 杨进霞

导师: 师海忠

关键词: 广义基超立方体网络,控制数,全控制数,独立控制数,连通控制数,完美控制数,符号控制数,反符号控制数,圈积,分解

来源: 西北师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西北师范大学

分类号: O157.5

总页数: 100

文件大小: 1430K

下载量: 5