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

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

本项目对近年来提出的度量互连网络可靠性参数—k-限制连通度和k-限制边连通度的优化和计算问题做了深入的研究。一方面，着重刻画了两种参数达到最大值时的极图的特征，给出判定这些极图的充分条件；另一方面，对在互连网络设计中的著名网络超立方体、 元 方体等确定两种参数以及相关的结构性质,并在此基础上对其可靠性进行分析和评价。迄今已完成学术论文6篇，正式发表3篇，录用1篇，其中SCI收录2篇，参加国内学术会议3人次，培养硕士生3人（已获学位1人）。已按申请书计划实现了预期目标.主要研究进展如下：. 在对k-限制边连通度的研究方面， 综合考虑了k-限制边连通度与图的多个典型参数—最小边度、最小度以及距离为2的点对的邻域的交集之间的关系，证明了一般图的k-限制边连通度最优和超级最优时的新的充分条件。. 在对k-限制连通度的研究方面，着重研究了k元n方体网络的k-限制连通度。利用k元n方体的正则性、传递性和递归结构，证明了3元n方体网络的k-限制连通度的计算公式，同时刻画了去掉最小k-限制割后3元n方体网络的连通分支的结构特征。另外，还研究了k元n方体网络的容错泛连通性（容错泛连通性是与图的k-限制连通度相关的、用来度量网络可靠性的一个重要指标）， 证明了具有2n-3个坏元素（点或边）的(2k+1)元n方体是[n(k+1)-1]-泛连通度的。. 在算法研究方面，注意到微粒群算法是一种求解大规模复杂问题的有效的智能算法。因此，它也可以作为求解大规模互连网络的k-限制连通度和k-限制边连通度问题的方法。我们提出了微粒群算法的一种新的适应度估计策略。在求解的同时，利用微粒群算法的进化模型以及同一代粒子之间的位置关系增加预测机制，减少适应函数的计算次数，从而加快搜索速度，提高计算效率，为实际的复杂优化设计问题求得较优解的同时节省时间成本。