平衡超立方体网络和Kn(?)del图的消圈数研究

发布时间：2023-03-26 19:52

　　当今的超级计算机包括成千上万的处理器,它们都是大规模并行系统。互连网络是设计超级计算机过程中必不可少的组成部分,在很大程度上决定并行计算机的性能。在选择互连网络时,如何选择一个合适且高效的互连网络拓扑结构是现在急需解决的问题。在这样的背景下,广大学者相继设计了各式各样的网络拓扑结构。但是如何衡量一个网络的优劣,且衡量这个网络拓扑结构优劣需要参考什么参数的问题相继出现。人们希望通过比较这些互连网络拓扑结构图的相关参数来找出一种较优的互连方式,从而设计出更好的计算机系统。消圈数,也称反馈数,是衡量网络拓扑结构性能优劣的重要参数之一。它作为图论研究中最经典的问题之一,已经在计算机科学、互连网络和通信等领域中有极其重要的应用。求解图的消圈数问题属于NP-hard问题。但到目前为止已经给出消圈数的图类还较少,甚至已给出较好消圈数界的图类也不多。尤其是一些较复杂的图类(包括有重要应用前景的互连网络拓扑结构图)的消圈数问题还有待进一步解决。本文将求解图的消圈数问题转化为构造图的含有尽可能多的顶点的可递推无圈子图的问题,采用数学构造与计算机分支限界搜索交互的方法,通过反复交互来完成数学构造,最后用数学...

【文章页数】：80 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景及意义
    1.2 消圈数问题的研究现状
    1.3 研究内容与文章结构
第二章 基础理论概述
    2.1 基础概念
        2.1.1 图论的基本概念
        2.1.2 图的消圈集
    2.2 互连网络拓扑结构设计的基本方法
        2.2.1 笛卡尔乘积方法
        2.2.2 Cayley方法
        2.2.3 线图方法
第三章 平衡超立方体网络的消圈数研究
    3.1 平衡超立方体网络的定义与性质
    3.2 平衡超立方体网络的无圈点集构造
        3.2.1 当n≤5时无圈点集的构造
        3.2.2 当n≥6时无圈点集的构造
    3.3 平衡超立方体网络的消圈数
    3.4 小结
第四章 Kn(?)del图的消圈数研究
    4.1 Kn(?)del图的定义与性质
    4.2 Kn(?)del图的无圈点集构造
        4.2.1 特殊情况无圈点集的构造
        4.2.2 W_5,n无圈点集的构造
    4.3 Kn(?)del图的消圈数
    4.4 小结
第五章 Goldberg Snarks及其相关图的消圈数研究
    5.1 Goldberg Snarks及其相关图的定义
    5.2 Goldberg Snarks及其相关图的无圈点集构造
        5.2.1 G_n和Gn
*的无圈点集的构造
        5.2.2 TG_n和TGn
*的无圈点集的构造
    5.3 Goldberg Snarks及其相关图的消圈数
    5.4 小结
结论与展望
参考文献
攻读硕士学位期间发表的学术论文
致谢



本文编号：3771611

suoshi