图的k-限制连通度和k-限制边连通度的优化研究

项目名称： 图的k-限制连通度和k-限制边连通度的优化研究

项目编号： No.11126076

项目类型： 专项基金项目

立项/批准年度： 2012

项目学科： 金属学与金属工艺

项目作者： 原军

作者单位： 太原科技大学

项目金额： 3万元

中文摘要： 随着社会信息化进程的加速，计算机网络规模急剧扩展，计算机网络的可靠性问题日益凸显. 计算机网络的可靠性可以用其拓扑图的连通度和边连通度来度量. k-限制连通度和k-限制边连通度是传统的图的连通度和边连通度概念的推广。由于它能更精确的度量网络的可靠性，近年来得到了广泛的关注. 本项目拟从两方面对图的k-限制连通度和k-限制边连通度进行研究. 一方面，通过讨论k-限制连通度和k-限制边连通度与图的其它参数之间的关系以及k-限制连通度和k-限制边连通度最优时子图的结构特征，获得一般图的k-限制连通度和k-限制边连通度最优时的充分条件和必要条件. 另一方面，拟研究重要的网络模型超立方体及其变形网络的k-限制连通度和k-限制边连通度. 利用超立方体及其变形网络的正则性、传递性和递归结构，研究其极大k限制连通性、极大k限制边连通性和超级k限制边连通性.

中文关键词： 互连网络；图；可靠性；限制连通度；限制边连通度

英文摘要：

英文关键词： interconnection networks；graphs；reliability；restricted connectivity；restricted edge connectivity