若干网络的拓扑结构特征,高阶限制边连通度和容错连通控制集

本项目研究网络的结构特征与高阶限制边连通度，新型互连网络拓扑-广义斐波那契立方的距离特性和序结构,无线网络拓扑-单位圆盘图的容错连通控制集的近似算法，是个具有实际背景的研究课题，涉及图论，可靠性理论，组合最优化，以及算法和复杂性等数学理论。具体地，本项目研究极大m-限制边连通图和超级m-限制边连通图所具有的结构性质和各种简单可行的判断条件，计算各种特殊图类或网络的m-限制边连通度和超m-限制边连通性，为更加准确地度量网络可靠性、找到具有较高可靠性和有效性的网络拓扑结构提供理论依据；建立广义斐波那契立方图和平面二部图的完美匹配的Z-变换图及相应分配格之关系，以此揭示广义斐波那契立方图所拥有超立方的优越网络性能；图的容错连通控制集在无线网络的路由中起着虚拟中枢链路的作用，探索单位圆盘图上的可容错连通控制集的更高连通度和更好近似比的近似算法。

本项目研究了网络的结构特征，高阶限制连通度、匹配排除数和约束数等网络容错性和稳定性指标，新型互连网络拓扑-广义和扩展斐波那契立方的距离特性,超立方及其变种的Hamilton圈的嵌入特性，无线网络拓扑-单位圆盘图的容错连通控制集的近似算法等，完成了项目的研究工作，取得了很好的研究进展. 在高阶限制连通性方面，揭示了非完全的超限制边连通图的最小度顶点集的导出子图的结构性质，给出了直径和邻域等条件下最优和超限制高阶边连通性图的充分条件，特别地表明了直径2、围长5、阶不小于6的图都是3阶限制边连通最优图，给出了一般点传递图的超级高阶限制边连通性图的围长和度条件，计算出了增广k元n维立方和平衡超立方的低阶限制连通度. 在超立方的各种子网上，给出了Fibonacci (p, r)-立方成为平面二部图的Z-变换图的完整刻画，与理论化学中的共振图建立了联系，分别给出了Fibonacci (p, r)-立方是median图和能等距离嵌入超立方的判别条件，对带有禁用子列的广义Fibonacci立方也研究了其等距离嵌入问题；在特定Hamilton圈存在和嵌入方面，表明平衡超立方具有超-Hamilton laceability，扩展Fibonacci立方体具有偶泛圈性，特别研究了Ruskey和Savage问题，即图的匹配能否扩张成Hamilton圈的问题，证明n维超立方中的每一个大小不超过3n-10的匹配可以扩张成一个Hamilton圈，及其容错Hamilton圈扩张的结果。在网络性能指标上，我们研究了图的匹配排除数和约束数，它们可衡量网络容错性和稳定性，近年来在国际学术领域比较活跃. 我们证明了二部图上的反凯库勒问题是NP-完备的，提出了高阶限制匹配排除问题, 并证明了它们也是NP-完备的，计算出了平衡超立方和高维网格的匹配排除数；得到了完全图与路的强乘积图的约束数表达式，给出了一般图与树的强乘积图的约束数的紧上界. 在容错连通控制集方面，一般图和单位圆盘图上寻找最小连通控制集是NP-完备的, 我们对单位圆盘图设计了其3-连通m-控制集新的近似算法，表明其近似比是个常数，并降低了算法的时间复杂性, 还设计出了多跳容错连通控制集的近似比为多项式的近似算法.