排列图的相关性质

我们通常用一个连通的无向图 G = (V, E) 表示互连网络的拓扑结构, 图 G 的顶点代表网络中的组件, 图 G 的边代表网络中组件 之间的通信联系. 对互连网 络的研究是并行和分布式计算机系统中的一个重要研究领域. 本文主要研究排列图的支撑连通性. 排列图是由D.kay 和Tripathi提出来的, 它是星图的一类推广, 但它的阶却比星图更具有灵活性, 它是点可迁图也是边可 迁图. 当 n ≥ 2, k = 1 时, 排列图为完全图, 而当 n ≥ 3, k ̸= n − 1时, 它是非二部 图. 本文第一章给出一些基本概念, 第二、三、四章分不同情况研究了An,k的支 撑连通性. 本文主要结果如下: 结论(1) 当 n ≥ 5 时, An,2 为超支撑连通图. 结论(2) 当 n ≥ 6, n − k ≥ 3 时, An,k 为 3∗-连通图和 4∗-连通图. 结论(3) 当 k ≥ 3, n − k ≥ 4 时, An,k 是 [k(n − k)]∗-连通图. 结论(4) An,k 为 s∗- 连通图, 其中 (k−1)(n−k) < s < k(n−k), k ≥ 3, n−k ≥ 4.