关于几类强乘积图的转发指数研究

作     者：钱伟民 

作者单位：青海师范大学 

学位级别：硕士

导师姓名：李峰

授予年度：2024年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：网络 强乘积 图 点转发指数 边转发指数 

摘      要：大规模集成电路技术的突破,使得具有多处理系统的超级计算机快速发展。与此同时,对多处理系统内通信网络的性能要求逐渐增高。目前,通信网络的性能主要会受到该网络拓扑的直接影响,因此,对新网络拓扑的构造以及性能的评估变得至关重要。在网络拓扑的构造方面,强乘积方法被认为是一种有效的策略,它主要以具有不同特点的网络拓扑(线性总线型网络拓扑、完全型网络拓扑、星型网络拓扑等)为基础拓扑,来构造新的网络拓扑。更为重要的是,该方法构造的新网络拓扑可保留自身基础拓扑的部分优良性质,例如Cayley性,Hamilton性、正则性等。在网络性能的评估方面,转发指数被认为是一个重要的指标,它主要以度量网络的负载情况来评估通信网络的性能。由于网络拓扑的构造和性能的评估完全可以通过图的形式来进行。因此,为了探索利用强乘积方法构造高性能通信网络的新思路,同时也为了拓展转发指数的研究范围,本文结合强乘积方法构造了几类特殊强乘积图,并对这些特殊强乘积图的转发指数进行了研究和分析。本文主要内容如下: (1)以多条无向路、多个无向圈、多个有向圈、多个轮图、多个Petersen图分别为基础图,结合强乘积方法,构造出了五类特殊强乘积图。然后,通过数学归纳法和反证法,给出了这五类特殊强乘积图的点转发指数和边转发指数的下界。 (2)以完全图和星图为基础图,结合强乘积方法构造了一类特殊强乘积图。然后,利用构造法和分类讨论法,刻画出了这类特殊强乘积图的边转发指数的上界。 (3)以无向圈和完全图为基础图,结合强乘积方法构造出了一类特殊强乘积图。然后,通过极值法、分类讨论法和构造法,不仅刻画出了这类特殊强乘积图的边转发指数的上界,而且更为重要的是,确定了这类特殊强乘积图的点转发指数。