摘要
蜻蜓网络使用一组路由器作为虚拟路由器,具有直径小、低延迟、低成本、高带宽等特点,在数据交换方面具有显著优势,因而在高性能计算系统（HPC）的应用中有很大的发展潜力. 本文选择无平行链路、相对全局链路连接方式的蜻蜓网络D(n, h)进行研究. 互连网络在图论中可以表示为一个简单无向图, 网络中的一个路由器用图中的一个点来表示,两个路由器间的链路则用图中的一条边来表示. 这样,对互连网络的拓扑结构的研究就转化为对图的结构进行研究. 一个图 G 中若包含哈密尔顿圈, 则称图 G 是哈密尔顿的. 若图 G 中存在 3 到|V(G)| 长的所有圈, 则称图 G 是泛圈的. 若对图 G 中任意一点 u, 过点 u 存在 3 到|V(G)|长的所有圈,则称图G是点泛圈的. 若图G中任意不同的两点间均存在哈密尔顿路,则称图G是哈密尔顿连通的. 若去掉不超过l个点后图G依然是哈密尔顿的,则称图G是l-点故障哈密尔顿的. 本文主要对蜻蜓网络D(n, h)的哈密尔顿性、泛圈性、点故障哈密尔顿性等进行研究,得到的主要结论如下: 1. 在第二章中,我们首先证明了当 n≥1, h≥2时,蜻蜓网络 D(n, h)是哈密尔顿的;随后进一步证明了当 n≥4, h≥2时, D(n, h)是泛圈的,并且是点泛圈的、哈密尔顿连通的. 2. 在第三章中,我们首先证明了去掉任意多个组内坐标不为0或n-1的点, D(n, h)总是哈密尔顿的,并在此基础上进一步证明了当n≥4, h≥2时, D(n, h)是2-点故障哈密尔顿的.
NETL