图网络斯坦纳彩虹连通度的算法及随机性研究

Steiner tree problem is one of the first seven problems shown NP-complete and rainbow connection is a concept of connectivity defined on colored graphs. The Steiner rainbow connection number of graphs is a comprehensive graph parameter of Steiner problem and rainbow connectivity problem. It has its theoretical interest and finds practical applications in information transfer and network security. The purpose of this project is to research the Steiner rainbow connectivity of a graph from some following aspects: explore the computational complexity of Steiner rainbow connection number; design approximate algorithms for Steiner rainbow connection number; study Steiner rainbow connectivity of random graphs. Since the generality of Steiner rainbow connectivity, the research on Steiner rainbow connectivity will not only further promote the research on the topics of Steiner connectivity as well as coloring, but also provide some theoretical basis for the application in complex networks security.

斯坦纳树问题是经典的七个NP完全问题之一，彩虹连通性是定义在染色图上的广义连通性概念。斯坦纳彩虹连通数结合了斯坦纳问题和彩虹连通性问题两个方面，它不仅具有重要的理论研究意义，而且在信息传输与网络安全等领域有着广泛应用。本项目拟从以下几个方面研究图的斯坦纳彩虹连通性：其一，探讨图的斯坦纳彩虹连通数的计算复杂性；其二，设计图的斯坦纳彩虹连通数的近似算法；其三，研究随机图的斯坦纳彩虹连通性。由于斯坦纳彩虹连通数更具一般性，本项目的研究不仅深化了图的斯坦纳连通性理论和染色理论，也为斯坦纳彩虹连通数在信息传输与网络安全方面的应用提供一定的理论基础。

斯坦纳树问题是经典的七个NP完全问题之一，彩虹连通性是定义在染色图上的广义连通性概念。斯坦纳彩虹连通度结合了斯坦纳问题和彩虹连通性问题两个方面，它不仅具有重要的理论研究意义，而且在信息传输与网络安全等领域有着广泛应用。因此，对斯坦纳彩虹连通度的研究是非常有意义的。.本项目在国家自然科学基金委的资助下，完成了项目预期的主要目标。目前，该项目得到的主要结果如下：研究了图的k点彩虹指数问题，得到了一般图的3点彩虹指数与阶数和最小度相关的上界。对于一般图G的k彩虹指数，针对k有单调性，但是n阶圈图的k点彩虹指数的结果说明了对于一般图的k点彩虹指数，上述单调性不成立；研究了图操作下的全彩虹连通度问题，得到了全彩虹连通数在加边和删边操作下的变化以及卡氏积图与图半径相关的上下界；研究了图的路连通度，完善了完全二部图的路连通度的已有结果；研究了斯坦纳彩虹连通度问题，运用正则引理证明了如果一个连通图的最小度有下界，那么图的k斯坦纳彩虹连通数有上界。此外，本项目还开展了带容量的有向中国邮递员问题的研究，也已取得相应的研究成果。