计算机科学中的若干组合问题研究

This project aims at the study of some graphic parameters such as the conditional connectivity, spanning connectivity, bounded connectivity, Menger number, wide-diameter, fault-diameter and so on, which frequently appear in the reliable and efficient analysis of interconnection networks since they are important parameters to measure the performance of networks. Our study not only provides a further mathematical foundation for the design and analysis of the next generation of large-scale parallel super computer systems, but also further enriches and perfects combinatorial network theory, expands research contents and application areas of graph theory. The problems of determining these parameters are NP-hard, and are challenges for us. In this project, we will employ the combinatorial and algebraic method to study the structure of networks, to reveal the close relationships among these parameters and their rules of changes. To this aim, we have to make a breakthrough at some new idea and creative technique. In the process of the project, we will further promote academic intercommunion with international experts, popularize new theory and methods in networks, train young talents with innovative abilities, and upgrade our research level and international reputation in combinatorial network theory.

本项目主要研究互连网络可靠性和有效性分析中的若干图论参数：各种限制条件下的连通度、支撑连通度、有界连通度、Menger数、宽直径、容错直径等，它们是度量网络性能的重要参数。这些参数的研究不仅为新一代超大规模并行计算机系统的互连网络设计和分析提供进一步的数学理论基础和依据，而且进一步充实完善组合网络理论，大大丰富了图论的研究内容和应用范围。这些问题的解决和参数的确定大多是NP-hard问题，具有很大的挑战性。本项目将通过组合和代数分析方法，深入研究网络结构性质，揭示这些参数之间密切关系和内在联系，探索变化规律，力争在理论和方法上取得较大突破，实现拟定的研究目标。在项目实施过程中加强国内外学术交流，普及组合网络新理论和新方法，培养具有创新能力的高水平年轻人才，提高我国组合网络理论研究水平和国际影响。

本项目研究计算机科学中的若干组合问题，顺利完成计划书中拟定的主要研究任务。图的各种各样条件连通度和宽直径是网络容错性和有效性的重要度量参数。网络故障是不可避免的，故障诊断和由网络故障引起的各种度量参数变化是网络理论研究的重要课题。本项目通过图的替代乘积和群的半直积构造Cayley图，弄清了给定限制边连通度的点可迁图的存在性，解决了困扰10多年的问题；确定了许多著名网络（如星网络、(n,k) 星网络、超立方体型网络、对偶立方、交换超立方体网络和分层立方网络等）的高阶超连通度；建立了在限制条件下的故障诊断数与 2 强点连通度之间的密切关系,从而确定了许多著名网络在限制条件下的诊断数和 2 强点连通度；研究了具有递归结构网络的嵌入连通度, 确定了若干网络（如超立方体、星图等）嵌入点连通度和嵌入边连通度；研究和确定了正则图、置换图、笛卡尔乘积图等的 2 强边连通度的脆弱性（即持久度）；证明了变形超立方体网络的点可迁性和圈、路容错嵌入和容错超立方体网络多对多不交路问题；利用图的本原指数, 确定了直积图的直径；研究了正则图的宽直径；确定了强超立方体网络的容错直径和宽直径。本项目共完成学术论文17 篇,英文版网络理论专著一部。这些研究成果大大丰富和完善了图的理论,为分析网络性能提供进一步的理论依据。