若干互连网络的诊断性及子图嵌入性研究

The topology of an interconnection network is often modeled as an undirected, simple and connected graph, where vertex and edge represent the processor and the link between two processors, respectively. An interconnection network may contain thousands of processors. The work of the interconnection network may be affected by the disabled processors and links. Hence it is important to consider the diagnosis of the interconnection network. If fault-free paths and cycles can be embedded into the interconnection network which has faulty processors and links, then the interconnection network can work normally. Thus subgraph embedding into an interconnection network is an important issue. In this project, we will consider the following problems: (1) the conditional diagnosability and the g-good-neighbor conditional diagnosability of some famous interconnection networks; (2) the diagnosis of some complicated networks and the diagnosis algorithm; (3) the subgraph embedding problem of interconnection networks, especially the Hamiltonian path and Hamiltonian cycle embedding problem of some interconnection networks with faulty links. We hope to get some interconnection networks with better diagnosability and stability.

互连网络通常可以看成是一个无向、简单、连通图，互连网络中的处理器可以用图的顶点表示，而处理器之间的信道可以用图的边表示。互连网络往往含有成千上万的处理器，如果处理器或信道发生故障，就会影响整个网络的运行，因此研究互连网络图的故障诊断能力蕴藏着潜在的应用价值。当互连网络存在部分故障处理器或信道堵塞时，如果能将无故障的路、圈嵌入该网络中，则能保障剩余网络的正常运行，因此研究子图的嵌入问题具有很大的实用价值。本项目拟对如下问题进行研究：（1）部分著名的互连网络的条件诊断能力、g-好邻居条件诊断能力；（2）复杂网络的诊断能力以及诊断算法；（3）互连网络的子图嵌入问题，特别是当互连网络有故障边时，哈密尔顿路、哈密尔顿圈的嵌入问题。我们期望能找到诊断性能以及稳定性能较好的互连网络图类。

图论在组合优化、信息科学、几何学、运筹学以及网络理论等多个领域都发挥着非常重要的作用。由于互连网络的拓扑结构是设计和制造大规模计算机网络系统以及实现各种协议的基础，它直接影响到互连网络的可靠性以及时效性。因此互连网络图在理论计算机科学等领域拥有极其重要的应用价值。本项目充分利用图论、线性代数、矩阵论以及组合数学等数学知识，研究互连网络图的诊断性能及嵌入性能中的如下科学问题：（1）研究网格图的定位-全控制数并给出其上下界。网络的任意一个顶点一定与该网络的定位-全控制集合的某顶点相邻，因此定位-全控制数可以影响该网络的诊断性能。（2）研究给定围长和直径的无圈图的基尔霍夫指标并给出具有最小基尔霍夫指数的图。由于诊断一个网络的故障顶点需要进行测试，这时可以将网络看成电路网络，而基尔霍夫指标可以判断该电路的电阻。因此基尔霍夫指标可以影响该网络的诊断性能。（3）研究冒泡星图的圈嵌入性能。圈是互连网络图中非常重要的元素，可以保证任意两点之间至少有2条路相连。如果其中一条路中有故障元素，则这两个点仍然可以通过另一条路进行正常的信息交互。通过研究冒泡星图（含n!个点且n≥3）的圈的性质，我们得出其任意边都在长度分别为4到n!的所有偶圈上。（4）研究冒泡星图的边容错强Menger边连通度。互连网络图的边容错强Menger边连通度可以得出当该互连网络图存在部分故障的边时，任意两个点之间无故障的路的条数，其也是互连网络图的路嵌入性能的重要指标之一。通过研究冒泡星图的边的性质，我们得出其边容错强Menger边连通度以及条件边容错强Menger边连通度。（5）研究(n,k)-冒泡图的圈嵌入性能。通过研究(n,k)-冒泡图Bn,k的圈的性质，我们得出其任意点都在长度分别为3到|V(Bn,k)|的所有圈上。依托本项目，我们已发表5篇SCI论文。本项目的研究成果可应用于复杂网络等方面，具有广阔的应用前景，并可对理论计算机的研究产生积极的影响。