关于笛卡尔乘积图边容错直径的研究

刘启云，王金建，谢 堃

(安徽大学数学科学学院，合肥 230601)

0 引言

大规模集成(VLSI)电路技术的出现，使人们能建造出非常庞大而复杂的互联网络.出于多方面考虑，下一代超级计算机系统将通过增加处理器的数目，而不是单靠利用更快的处理器来实现高速快捷的目的.建造超级计算机系统最困难的技术问题将是连接这些处理器的互联网络的设计，选择一个合适和理想的互联网络拓扑结构将变成一个迫切需要解决的问题.实践证明，图论是设计和分析互联网络的最基本且强有力的数学工具，因为互联网络的拓扑结构就是图.将网络中的处理器看成图中的顶点，各处理器之间的网络连线对应于图中连接相应顶点的边，此时，就可以通过分析图的结构来研究该网络.这样，网络的建构方法和可靠性，就可以看作是图的构造方法和可靠性.笛卡尔乘积是构建大型网络的重要方法，容错性是衡量网络效用性的重要标准，它们均可对应成图的相关特点和性质.

1 预备知识

介绍徐俊明［1］给出的图的基本定义和符号，这里只考虑简单无向图，即那些没有环和重边的无向图.

定义1 令图G=(V(G)，E(G))，其中V(G)，E(G)分别是图G的顶点集和边集.对任何u，v∈V(G)，若u，v之间有边，就说u和v是邻接的，并分别用NG(u)，dG(u)表示顶点u的邻点集合和邻点的数目，通常dG(u)称为u的度，图G顶点的最小度和最大度记作δ(G)和Δ(G)，分别定义为

定义2 设u0，u1，…，uk是G中的k+1个不同的顶点，若对所有的0≤i≤k-1，均有ui与ui+1邻接，记P=u0u1…uk，则P表示一条从u0到uk的……