基于并行系统规则网络的条件嵌入研究

The problem of graph embedding takes an important role not only in graph theory, but also in the design and analysis of interconnection networks. The project intends to study the embeddings of paths and cycles in regular networks in three aspects: covering, fault tolerent and prescription. Firstly, we will investigate the spanning connectivity and spanning pan-connectivity of mesh and torus, which are correspongding parameters of covering embeddings, by analysing the structures of hypercube, k-ary n-cube, mesh and torus and studing their relationships. Furthermore, we will present some sufficient conditions for a graph constructed by Cartesian product to be spanning connected. Secondly, according to the distributions of faults in the networeks, we will provide some conditional fault models and determine the fault tolerance of panconnectivity and pancyclicity for mesh and torus under these conditional fault models. Thirdly, according to the distributions of prescripted elements in the networeks, we will provide some conditional prescripted models and determine the prescripted panconnectivity and pancyclicity for mesh and torus under these conditional prescripted models. Finally, we will design algorithms for finding these paths and cycles, provide programs for these algorithms, and execute these algorithms to measure and compare the conditional embeddings of some well-known regular networks.

图嵌入问题不但是图论的重要研究专题, 也是网络设计和分析中重要的研究内容. 本项目拟对覆盖约束、容错约束和指定约束三种约束条件下基于并行系统规则互连网络的路、圈嵌入问题进行研究. 首先，本项目通过剖析n维超立方，k元n立方网络，网格与环网的结构，利用它们之间的性质关系，确定出网格和环网的支撑连通性和支撑泛连通性(它们是覆盖约束嵌入的度量)；获得基于笛卡尔乘积法构建的规则网络保持支撑连通性的一些充分条件. 其次，本项目拟根据网络中故障分布的特点，提出不同的条件故障模型，并确定网格和环网在新的条件故障模式下的容错泛连通性和泛圈性. 再次，根据网络中指定元分布的特点，提出不同的指定模型，并确定网格和环网在新的指定模式下的指定泛连通性和泛圈性. 最后，拟设计用于确定网络中这些约束条件下可嵌入的路和圈的算法，用计算机程序实现该算法，并用这个算法度量和比较一些著名规则网络的可嵌入性.

本项目属于数学与信息学的交叉学科，主要对并行系统的互连网络拓扑性质进行研究，属于基础应用研究，旨在对并行系统互连网络的设计和分析起到一定的指导意义。本项目集中对图嵌入问题方面进行研究，主要对三种约束：覆盖约束、容错约束和指定约束三种下基于并行系统规则互连网络的路、圈嵌入问题进行研究. . 具体来说，覆盖约束下的并行不交路嵌入方面，我们完成环网的支撑连通性和超级支撑连通性以及支撑泛连通性刻画；获得限制条件连通度和以往条件连通度和限制条件连通度之间的关系式；获得部分规则网络保持支撑连通性的充分条件; 证明了非二部环网是2n-3边故障二不交路覆盖的。. 规避约束（容错约束）下路、圈嵌入方面，我们完成网格和环网在已有的各种容错条件下的Hamilton性和Hamilton连通性，容错泛圈性和容错泛连通性刻画；在故障元成单线故障模式时，获得3元n立方网络能够保持哈密尔顿性和可以容忍的故障元数目的上界；按照当前已知的最大容错数, 获得网络能够保持泛圈性的圈长的下界。. 指定约束下的路、圈嵌入方面， 获得k元n立方存在经过指定边集的Hamilton圈,泛圈性的充分条件；在单线指定模式下，确定k元n立方网络具有指定Hamilton性可以允许指定的点和（或）边数目的上界；按照当前已知的最大指定元数, 获得网络能够具有指定泛圈性的最小圈长.