路与圈直积的直径与容错直径研究

Diameter and Fault-Tolerant Diameter of the Direct Product of Path and Cycle

摘要: 本文研究了路径图$P_n$ ，圈图$C_m$ 及其直积图$P_n\times P_m,P_n\times C_m$ 和$C_n\times C_m$ 的直径与容错直径，其中$n$ 和$m$ 为正整数。对于给定的正整数$k$ ，通过分析图的结构特性，我们给出了这些图的直径与$k$ -容错直径的精确表达式，并建立了若干关于直积图中两点间距离的计算公式。特别地，我们证明了$P_n\times P_m$ 的容错直径等于其直径，而在$P_n\times C_m$ 和$C_n\times C_m$ 中，容错直径随图的结构参数变化而呈现出不同特性。本文的结果为图在网络容错性分析与通信延迟建模中的应用提供了理论依据。

Abstract: This paper investigates the diameter and fault-tolerant diameter of path $P_n$ , cycle $C_m$ , and their direct products $P_n\times P_m$ , $P_n\times C_m$ and $C_n\times C_m$ , where $n$ and $m$ are positive integers. For a given positive integer $k$ , by analyzing the structural properties of these graphs, we derive exact expressions for their diameters and $k$ -fault-tolerant diameters, and establish several formulas for computing distances between two vertices in the direct product graphs. In particular, we prove that the fault-tolerant diameter of $P_n\times P_m$ equals its diameter, while in $P_n\times C_m$ and $C_n\times C_m$ , the fault-tolerant diameter varies with the structural parameters of the graphs. The results of this study provide a theoretical foundation for the application of graphs in network fault-tolerance analysis and communication latency modeling.

1. 引言

图的直径是图论与网络科学中的核心参数之一。对于一个连通图$G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个简单图，其中$V\left(G\right)$ 表示顶点集合，$E\left(G\right)$ 为$V\left(G\right)$ 的二元素子集，称为$G$ 的边集合，图中任意两顶点$u,v\in V$ 之间的距离$d\left(G;u,v\right)$ 定义为连接$u$ 和$v$ 的最短路径所包含的边数。图$G$ 的直径(Diameter)，记为$d\left(G\right)$ ，则定义为所有顶点对之间距离的最大值[1]，即：

$d\left(G\right)=\max \left\{d\left(G;u,v\right)|\forall u,v\in V\left(G\right)\right\}.$

该参数直接刻画了网络在最坏情况下的通信效率或信息传输延迟。然而，实际网络中的节点或链路可能因故障而失效，仅凭直径不足以评估网络的鲁棒性。为此，研究者引入了容错直径(Fault-Tolerant Diameter)与宽直径(Wide Diameter)等更强健的度量指标。具体而言，对于给定的正整数$k$ ，图$G$ 的k-容错直径$D_k\left(G\right)$ 定义为：在删除不超过$\left(k-1\right)$ 个顶点后，剩余连通子图直径的最大值[2]，即

$D_k\left(G\right)=\max \left\{d\left(G-X;u,v\right):X\subseteq V\left(G\right)\setminus \left\{u,v\right\},\left|X\right|\le k-1\right\}.$

这一参数衡量了网络在发生有限故障后仍能维持有效通信的能力。这些参数的研究，对于设计高可靠、低延迟的互联网络拓扑结构具有重要的理论指导意义。

在图运算中，直积图(Direct Product Graph，亦称张量积)作为构造复杂网络模型的重要工具之一，被广泛应用于并行计算与分布式系统的网络设计中[3]-[5]。路$P_n$ 与圈$C_m$ 作为最基本、最规整的图类，它们的直积图$P_n\times P_m,P_n\times C_m$ 和$C_n\times C_m$ 不仅结构优美，而且具有丰富的组合性质。例如，Shiu等[6]指出$P_n\times C_m$ 同构于一类环形栅栏图(Circular Palisade Graph)，其具体结构依赖于$m$ 的奇偶性。对这类直积图的直径与容错参数进行精确分析，是评估其作为网络拓扑可靠性的关键。

目前，关于路径图与圈图在笛卡尔积(Cartesian Product)运算下的直径与容错性已有较为系统的研究。例如，已知笛卡尔积图$P_n\square P_m$ (即网格图)的直径为$n+m-2$ ，其容错直径等相关参数也已被精确确定[3] [7]。然而，对于直积图，相关研究则更多地集中于谱理论[8]、染色问题[6] [9]与连通性[10] [11]等方面。例如，Wang等人[8]研究了$P_n\times C_m$ 的拉普拉斯谱；Li与Sun [10]探讨了其彩虹连通数。尽管这些研究揭示了直积图丰富的代数与组合性质，但对其容错直径与宽直径等强鲁棒性参数的系统性研究仍相对缺乏，尤其是针对不同奇偶性组合下精确值的刻画。

本文旨在系统研究$P_n\times P_m,P_n\times C_m$ 和$C_n\times C_m$ 的直径与容错直径。通过深入分析其组合结构，我们给出了这些参数在不同情况下的精确表达式或紧的上界。本文的主要结果如下：

1) 给出了$P_n\times P_m$ 的直径与1-容错直径。

2) 给出了$P_n\times C_m$ 在$m$ 取不同奇偶性时的直径与2-容错直径的精确值。

3) 给出了$C_n\times C_m$ 的直径。

我们的结果从理论上揭示了这类直积图网络的容错能力与极限性能，为其在可靠网络设计中的应用提供了坚实的理论依据。

2. 术语和符号

本文考虑简单图。令图$G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个简单图，其中$V\left(G\right)$ 表示顶点集合，$E\left(G\right)$ 为$V\left(G\right)$ 的二元素子集，称为$G$ 的边集合。对于任意的集合$S$ ，$\left|S\right|$ 表示$S$ 中元素的个数。首先我们给出直径和容错直径的定义。

定义 2.1 (距离)：设$G=\left(V,E\right)$ 是一个连通图。对于图中任意两个顶点$u,v\in V\left(G\right)$ ，它们之间的距离为连接$u$ 到$v$ 的最短路径的长度(即包含的边数)，记为$d\left(G;u,v\right)$ 或在无歧义时简记为$d\left(u,v\right)$ 。

特别地，如果$u=v$ ，则$d\left(G;u,v\right)=0$ 。如果在$G$ 中存在$u$ 到$v$ 的路径，则称$u$ 到$v$ 在$G$ 中连通；如果在$G$ 中不存在$u$ 到$v$ 的路径，则称$u$ 到$v$ 在$G$ 中不连通，此时将$u$ 到$v$ 的路径距离为$\infty$ ，即$d\left(G;u,v\right)=\infty$ 。

定义 2.2 (直径)：图$G$ 的直径，记为$d\left(G\right)$ ，是图中任意两个顶点之间距离的最大值，即：

$d\left(G\right)=\max \left\{d\left(G;u,v\right)|\forall u,v\in V\left(G\right)\right\}.$

直径衡量了图在最坏情况下的通信延迟。

在实际应用中，图可能非连通。为此，我们扩充直径的定义如下：

定义 2.3 (非连通图的直径)：设$G=\left(V,E\right)$ 是一个非连通图，其顶点集$V$ 可划分为$V_1,V_2,\cdots ,V_k$ ，使得每个导出子图$G\left[V_i\right]\left(i=1,2,\cdots ,k\right)$ 是一个连通分支。则图$G$ 的直径定义为：

$d\left(G\right)=\max \left\{d\left(G\left[V_i\right]\right)|i=1,2,\cdots ,k\right\}.$

从其中$G\left[V_i\right]$ 表示$G$ 中顶点子集$V_i$ 的导出子图。

容错直径的概念旨在评估网络在顶点发生故障后的稳健性，它要求即使在删除一定数量的顶点后，剩余子图的直径仍然可控。

定义 2.4 (k-容错距离)：假设$k$ 是一个正整数且图$G$ 是$k$ -连通图的(即至少需要删除$k$ 个顶点才能使图变得不连通)。对于任意两个不同的顶点$u,v\in V\left(G\right)$ ，令

$D_k\left(G;u,v\right)=\max \left\{d\left(G-X;u,v\right):X\subseteq V\left(G\right)\setminus \left\{u,v\right\},\left|X\right|\le k-1\right\}$

其中，$G-X$ 表示从图$G$ 中删除顶点子集$X$ 后得到的子图。我们称$D_k\left(G;u,v\right)$ 为$u$ 与$v$ 在图$G$ 中的$k$ -容错距离。

这个定义衡量了在删除最多$k-1$ 个(不包括$u$ 和$v$ )顶点后，$u$ 和$v$ 之间最坏情况下的距离。

定义 2.5 (k-容错直径)：假设$k$ 是一个正整数且图$G$ 是$k$ -连通图的，图$G$ 的$k$ -容错直径，记为$D_k\left(G\right)$ ，定义为所有顶点对的$k$ -容错距离的最大值，即：

$D_k\left(G\right)=\max \left\{D_k\left(G;u,v\right)|u,v\in V\left(G\right),u\ne v\right\}.$

其意义是：对于任意一个包含不超过$k-1$ 个故障顶点的集合$X$ ，子图$G-X$ 的直径都不会超过$D_k\left(G\right)$ 。

值得指出的是：直径$d\left(G\right)$ 可以衡量无故障时的通信效率；容错直径$D_k\left(G\right)$ 可以衡量存在故障时的通信效率。由它们的定义可以，两个参数之间存在以下基本关系：对于$k\ge 1$ 。

$d\left(G\right)=D_1\left(G\right)\le D_k\left(G\right).$

即，容错直径在考虑故障后，其值不小于原始图的直径。

接下来我们给出直积图的定义。直积图(Direct Product Graph，亦称张量积)是构建复杂网络的重要图运算之一。

定义 2.6 (直积图)：假设$G$ 和$H$ 为两个图。它们的直积图$G\times H$ 定义如下：

• 顶点集：$V\left(G\times H\right)=\left(x,y\right)|x\in V\left(G\right),y\in V\left(H\right)$ 。

边集：$E\left(G\times H\right)$ 由满足$x_1{x}_2\in E\left(G\right)$ 且$y_1{y}_2\in E\left(H\right)$  的顶点对$\left(x_1,x_1\right)\left(y_2,y_2\right)$ 构成。

Figure 1. The direct product of $P_5$ and $P_4$

图1. $P_5$ 与$P_4$ 的直积图

图1是P₅与P₄的直积图，并在两个方向上展示了原图上的顶点到直积图上的顶点对的对应关系。

由直积图的定义，关于直积图中两点间的距离，有如下基本结论：

定理 2.7 假设$G$ 和$H$ 为两个图，$\left(x_i,y_p\right),\left(x_j,y_q\right)\in V\left(G\times H\right)$ 。如果$d\left(G;x_i,x_j\right)=\ell$ 且$d\left(H;y_p,y_q\right)=k$ ，则有

$d\left(G\times H;\left(x_i,y_p\right),\left(x_j,y_q\right)\right)\ge \max \left\{\ell ,k\right\}.$

证明：不妨设$\ell \ge k$ 。假设在$G\times H$ 中存在一条从$\left(i,p\right)$ 到$\left(j,q\right)$ 的长度为$\ell -1$ 的路径

$P=\left(x_i,y_p\right)\left(x_{i_1},y_{p_1}\right)\left(x_{i_2},y_{p_2}\right)\cdots \left(x_{i_{\ell }-2},y_{p_{\ell -2}}\right)\left(x_j,y_q\right),$

其中每个$\left(x_{i_t},y_{p_t}\right)$ ，$t=1,2,\cdots ,\ell -2$ 。

根据直积图的定义，路径$P$ 中每条边$\left(x_a,y_b\right)\left(x_c,y_d\right)\in E\left(G\times H\right)$ 满足$x_a{x}_c\in E\left(G\right)$ 且$y_b{y}_d\in E\left(H\right)$ 。因此，序列

$x_i,x_{i_1},x_{i_2},\cdots ,x_{i_{\ell -2}},x_j$

构成图$G$ 中一条从$x_i$ 到$x_j$ 的迹(trail)，其长度为$\ell -1$ 。

由于任何迹都包含一条从$x_i$ 到$x_j$ 的路径，其长度不超过该迹的长度，因此有$d\left(G;x_i,x_j\right)\le \ell -1$ ，这与已知条件$d\left(G;x_i,x_j\right)=\ell$ 矛盾。故假设不成立，原结论$d\left(G\times H;\left(x_i,y_p\right),\left(x_j,y_q\right)\right)\ge \max \left\{\ell ,k\right\}$ 得证。

3. 主要结论

对于$P_n\times P_m$ ，本节将给出其直径与容错直径的精确表达式与证明。并基于此结论得出一个较定理2.7强的，在简单图的直积图中两点的距离公式，以便于后续证明进行。

3.1. $P_n\times P_m$ 中的直径与容错直径

在探究图的直径与容错直径之前，我们首先分析$P_n\times P_m$ 在图参数$n$ 与$m$ 取不同值时的结构特性。由路的性质与直积图的定义，可直接得到如下结论。为方便书写，在不引起歧义的情况下，$v_{i,j}=\left(i,j\right)$ 表示直积图$P_n\times P_m$ 中的顶点，其中$i\in V\left(P_n\right)=\left\{0,1,\cdots ,n-1\right\}$ ，$j\in V\left(P_m\right)=\left\{0,1,\cdots ,m-1\right\}$ 。

命题 3.1 对于任意两个顶点$\left(i,p\right),\left(j,q\right)\in V\left(P_n\times P_m\right)$ ，则

$\left(i,p\right)\left(j,q\right)\in E\left(P_n\times P_m\right)\iff \left|i-j\right|=1且\left|p-q\right|=1.$

等价地，这成立当且仅当$i\pm p\equiv j\pm q\left(\mathrm{mod}2\right)$ ，或$i\pm j\equiv p\pm q\left(\mathrm{mod}2\right)$ 。

上述关于边存在的同余条件可以推广到连通性。对路径上的每个顶点依次应用命题3.1，可得如下更强的结论：

引理 3.2 对于任意两个顶点$\left(i,p\right),\left(j,q\right)\in V\left(P_n\times P_m\right)$ ，则

$\left(i,p\right)$ 与$\left(j,q\right)$ 连通在$P_n\times P_m$ 中当且仅当$i\pm p\equiv j\pm q\left(\mathrm{mod}2\right)$ ，或$i\pm j\equiv p\pm q\left(\mathrm{mod}2\right)$ 。

由定理2.7和引理3.2可得任意两点的距离如下：

引理3.3设$\left(i,p\right),\left(j,q\right)\in V\left(P_n\times P_m\right)$ 且两点在$P_n\times P_m$ 中连通。令$\left|i-j\right|=\ell$ 且$\left|p-q\right|=k$ ，则

$d\left(P_n\times P_m;\left(i,p\right),\left(j,q\right)\right)=\max \left\{\ell ,k\right\}.$

证明：不失一般性，假设$\ell \ge k>0$ ，$i+\ell =j$ ，$p+k=q$ 。由引理3.2可知，连通性条件可知$\ell \equiv k \left(\mathrm{mod}2\right)$ ，故$\ell -k$ 为偶数。我们可以构造一条从$\left(i,p\right)$ 到$\left(j,q\right)$ 的路径：

1) 路径$P_1$ ：从$\left(i,p\right)$ 出发，通过一系列“对角线”$\left(+1,+1\right)$ 和$\left(+1,-1\right)$ 交替移动，在第一位坐标增加$\left(\ell -k\right)$ 的同时，第二位坐标最终回到$p$ ，到达点$\left(i+\ell -k,p\right)$ .此段路径长度为$\ell -k$ ，即

$\left(i,p\right)\left(i+1,p+1\right)\left(i+2,p\right)\left(i+3,p+1\right)\left(i+4,p\right)\cdots \left(i+\ell -k,p\right).$

2) 路径$P_2$ ：从$\left(i+\ell -k,p\right)$ 出发，通过一系列“对角线”移动$\left(+1,+1\right)$ ，在第一位坐标增加$k$ 的同时，从$p$ 变化至$q$ ，到达点$\left(j,q\right)$ .此段路径长度为$k$ ，即

$\left(i+\ell -k,p\right)\left(i+\ell -k+1,p+1\right)\left(i+\ell -k+2,p+2\right)\cdots \left(i+\ell -1,p+k-1\right)\left(j,q\right).$

其中$\left(i+\ell ,p+k\right)=\left(j,q\right)$ .

令$P=P_1\cup P_2$ ，则$P$ 一条从$\left(i,p\right)$ 到$\left(j,q\right)$ 的总长度为$\ell$ 的路径。因此，

$d\left(P_n\times P_m;\left(i,p\right),\left(j,q\right)\right)\le \text{max}\left\{\ell ,k\right\}$ .

另一方面，由定理2.7可知$d\left(P_n\times P_m;\left(i,p\right),\left(j,q\right)\right)\ge \max \left\{\ell ,k\right\}$ .综上所述$d\left(\left(i,p\right),\left(j,q\right)\right)=\max \left\{\ell ,k\right\}$ .对于$k>\ell$ 的情况证明类似。

利用引理3.3，我们可以直接得出$P_n\times P_m$ 的直径。

定理3.4$P_n\times P_m$ 的直径为$d\left(P_n\times P_m\right)=\max \left\{n-1,m-1\right\}$ .

证明：对于任意两个顶点$\left(i,p\right),\left(j,q\right)\in V\left(P_n\times P_m\right)$ ，有$\max \left|i-j\right|=n-1$ 和$\max \left|p-q\right|=m-1$ .

由引理3.3

$d\left(\left(i,p\right),\left(j,q\right)\right)=\text{max}\left\{\left|i-j\right|,\left|p-q\right|\right\}$

因此，图的直径即为所有顶点对间该距离的最大值：

$d\left(P_n\times P_m\right)=\underset{\left(i,p\right),\left(j,q\right)\in V\left(P_n\times P_m\right)}{\max }\max \left\{\left|i-j\right|,\left|p-q\right|\right\}=\max \left\{n-1,m-1\right\}.$

等号成立的情况分析如下：

• 情况1：当$n$ 或$m$ 为偶数时，$P_n\times P_m$ 有两个同构的连通分支。考虑其中一个分支即可。

• 若$n\ge m$ 且$n$ 为偶数，最大值可在点对$\left(\left(0,0\right),\left(n-1,1\right)\right)$ 处达到。

• 若$n\ge m$ 且$n$ 为奇数，最大值可在点对$\left(\left(0,0\right),\left(n-1,0\right)\right)$ 处达到。

• 情况2：当$n$ 和$m$ 均为奇数时，$P_n\times P_m$ 的两个连通分支不同构。考虑包含$\left(\left(0,0\right),\left(n-1,m-1\right)\right)$ 的连通分支，该点对间的距离即为最大值$\max \left\{n-1,m-1\right\}$ 。

综上述讨论，定理得证。

根据$P_n\times P_m$ 的定义可知其有两个连通分支，若$n$ 和$m$ 至少有一个偶数，则$P_n\times P_m$ 的两个连通分支都为1-连通，则$P_n\times P_m$ 的容错直径就是其直径。

基于对$P_n\times P_m$ 的研究，我们可以将距离公式推广到更一般的直积图中。

定理3.5设$G$ 和$H$ 为两个简单图，$x_i,x_j\in V\left(G\right)$ ，$y_p,y_q\in V\left(H\right)$ 。令$a=d\left(G;x_i,x_j\right)$ ，$b=\text{d}\left(H;y_p,y_q\right)$ 。考虑直积图$G\times H$ 中的顶点$u=\left(x_i,y_p\right)$ 和$v=\left(x_j,y_q\right)$ 。

1) 若$a\equiv b\left(\mathrm{mod}2\right)$ ，则

$d\left(G\times H;u,v\right)=\max \left\{a,b\right\}$ (1)

2) 若$a\cancel{\equiv }b\left(\mathrm{mod}2\right)$ ，且在$G$ 中存在一个包含$x_1$ 和$x_2$ 的奇圈$C_p$ (设($p$ 为满足此条件的最小奇圈长)

$d\left(G\times H;u,v\right)=\max \left\{p-a,b\right\}$ (2)

3) 若$a\cancel{\equiv }b\left(\mathrm{mod}2\right)$ ，且在$G$ 和$H$ 中分别存在包含$x_1,x_2$ 和$y_1,y_2$ 的奇圈$C_p$ 和$C_q$ ($p,q$ 为最小奇圈长)，则

$d\left(G\times H;u,v\right)=\min \left\{\max \left\{p-a,b\right\},\max \left\{a,q-b\right\}\right\}$ (3)

4) 若$a\cancel{\equiv }b\left(\mathrm{mod}2\right)$ ，且在$G$ 与$H$ 中均不存在同时包含$x_1,x_2$ 和$y_1,y_2$ 的奇圈，则$v_1$ 与$v_2$ 在$G\times H$ 中不连通，即

$d\left(G\times H;u,v\right)=\infty$ (4)

证明：我们先概括主要证明思路，对于直积图，在直积图中移动一步，意味着两点在原图中要同时移动一步。因此我们要找到在原图中的一条长度相同的最短的路径。对于两路径奇偶性相同时，路径短的一方通过“往回走再走回来”的方式实现与路径长的一方同时到达目标点。而奇偶性不同，但若存在奇圈，则可以取奇圈中另一方向，从而取到奇偶性相同的路径，对其应用第一种情况的结论即可。且对于奇圈，由于其长度为奇数，任意拆分都只能是奇长或偶长，则定能与取到距离的路径合并成一个取到最短距离所在路径的最小奇圈，且满足圈长最小性。但若均不存在奇圈，则两者不连通。

(1) $a\equiv b\left(\mathrm{mod}2\right)$ 。

考虑$G$ 中所有从$x_i$ 到$x_j$ 的路径集合$\left\{P_{1t}\right\}$ ，其长度构成集合$L_1=\left\{l_{1t}\right\}$ ，其中$\forall i,l_{1t}\equiv a\left(\mathrm{mod}2\right)$ (这里假设路的长度可以为0，即$x_1=x_2$ 的情况)。类似地，考虑$H$ 中所有从$y_p$ 到$y_q$ 的路径集合$\left\{P_{2t^{\prime }}\right\}$ ，其长度构成集合$L_2=\left\{l_{2t^{\prime }}\right\}$ ，其中$\forall t,l_{2t^{\prime }}\equiv b\left(\mathrm{mod}2\right)$ 。因此，我们有$\underset{t}{\min }\left\{l_{1t}\right\}=a$ ，$\underset{t^{\prime }}{\min }\left\{l_{2t^{\prime }}\right\}=b$ 。

在直积图$G\times H$ 中，取一对路径$P_{1t_1}\in G$ 和$P_{2{t^{\prime }}_1}\in H$ ，其中$\left|P_{1t_1}\right|=a$ ，$\left|P_{2{t^{\prime }}_1}\right|=b$ 。考虑$P_{1t_1}\times P_{2{t^{\prime }}_1}$ ，由于$\left|P_{1t_1}\right|=a\equiv b=\left|P_{2{t^{\prime }}_1}\right|\left(\mathrm{mod}2\right)$ ，根据引理3.3，顶点$u$ 和$v$ 在$P_{1t_1}\times P_{2{t^{\prime }}_1}$ 中连通且距离满足：

$d\left(P_{1t_1}\times P_{2{t^{\prime }}_1};u,v\right)=\max \left\{a,b\right\}.$

因此，在$G\times H$ 中，

$d\left(G\times H;v_1,v_2\right)\le \max \left\{a,b\right\}$

由定理2.7可知：

$d\left(G\times H;v_1,v_2\right)\ge \max \left\{a,b\right\}$

综上讨论可知(1)成立。

(2) 若$a\cancel{\equiv }b\left(\mathrm{mod}2\right)$ ，且在$G$ 中存在一个包含$x_1$ 和$x_2$ 的奇圈$C_p$ (设$p$ 为满足此条件的最小奇圈长)。首先我们给出如下要求：

要求：存在圈$C_p$ 为过$x_1,x_2$ 且在其上取到距离$a$ 的圈。

证明：如果不存在这样的$C_p$ ，则对于$G$ 中任意包含过$x_1,x_2$ 的圈$C$ ，$x_1,x_2$ 在$C$ 上的距离都不为$a$ ，则在$C$ 上由$x_1,x_2$ 划分出的两路径$P_{t_1},P_{t_2}$ ，其长度$t_1,t_2$ 满足$\left|P_{t_1}\right|\cancel{\equiv }\left|P_{t_2}\right|\left(\mathrm{mod}2\right)$ ，且$\left|P_{t_1}\right|,\left|P_{t_2}\right|>a$ ，因为$\left|P_{t_1}\right|+\left|P_{t_2}\right|=\left|C\right|$ 为奇数。不妨设$\left|P_{t_1}\right|\cancel{\equiv }a\left(\mathrm{mod}2\right)$ ，考虑$G$ 中一条长度为$a$ 的$x_1,x_2$ 路径$P_{t_0}$ ，则$P_{t_0}\cup P_{t_1}$ 构成一个奇圈且长度为$a+\left|P_{t_1}\right|<\left|P_{t_2}\right|+\left|P_{t_1}\right|=\left|C\right|$ ，与条件假设矛盾。

由于$\left|C_p\right|$ 为奇数，则$a$ 与$\left|C_p\right|-a$ 的奇偶性不同，因此$\left|C_p\right|-a\equiv b\left(\mathrm{mod}2\right)$ ，因为$a\cancel{\equiv }b\left(\mathrm{mod}2\right)$ 。现在考虑$G$ 中的路径长度为$\left|C_p\right|-a$ 和H中的路径长度为$b$ ，运用情况(1)的结论可知(2)成立。

(3) 运用$G$ 中的奇圈$C_p$ ，得$d\left(G\times H;u,v\right)=\max \left\{p-a,b\right\}$ ，运用H中的奇圈$C_q$ ，得$d\left(G\times H;u,v\right)=\max \left\{a,q-b\right\}$ 。因此，实际距离应为这两种方式中的较小值，即(3)成立。

(4) 由条件可知$G$ 中连通$x_i$ 到$x_j$ 的只有路径，且$G$ 中连通$y_p$ 到$y_q$ 的只有路径。由命题3.1可知在$G\times H$ 中不存在$u$ 到$v$ 的路，即$d\left(G\times H;u,v\right)=\infty$ 。

3.2. $P_n\times C_m$ 中的直径与容错直径

本节我们研究路$P_n$ 与圈$C_m$ 的直积图$P_n\times C_m$ 。我们首先分析$P_n\times C_m$ 在图参数$n$ 与$m$ 取不同值时的结构特性。由路的性质与直积图的定义，可直接得到如下结论。为方便书写，在不引起歧义的情况下，$v_{i,j}=\left(i,j\right)$ 表示直积图$P_n\times P_m$ 中的顶点，其中$i\in V\left(P_n\right)=\left\{0,1,\cdots ,n-1\right\}$ ，$j\in V\left(C_m\right)={\mathbb{Z}}_m$ .我们首先给出$P_n\times C_m$ 的直径公式。

定理3.6$P_n\times C_m$ 的直径为$d\left(P_n\times C_m\right)=\{\begin{array}{l}\max \left\{n-1,m\right\},如果m�奇�\\ \max \left\{n-1,\frac{m}{2}\right\},如果m�偶�\end{array}$ .

证明：下面的距离标记$d\left(u,v\right)$ 若无另外标出则均表示在图$P_n\times C_m$ 中的距离。

当$m$ 为奇数时，$P_n\times C_m$ 为连通图。考虑删去边集

$E_{del}=\left\{\left(k,0\right)\left(k+1,m-1\right),\left(k+1,0\right)\left(k,m-1\right)|k\in \left\{0,1,\cdots ,n-1\right\}\right\}$

后得到的子图同构于$P_n\times P_m$ 。对于任意两点$u=\left(x_i,y_p\right)$ ，$v=\left(x_j,y_q\right)$ ：

• 若$u,v$ 在$P_n\times P_m$ 中连通，由定理3.4可得

$d\left(u,v\right)\le d\left(P_n\times P_m\right)=\max \left\{n-1,m-1\right\}.$

• 若$u,v$ 在$P_n\times P_m$ 中不连通(不妨设$y_q>y_p$ )，则考虑由$P_n$ 和$C_m$ 的列列$Co{l}_{y_2},Co{l}_{y_2+1},\cdots ,Co{l}_{m-1},Co{l}_0,\cdots ,Co{l}_{y_1}$ 构成的子图$P_n\times P_{m-\left|y_1-y_2\right|+1}$ 。因为$u,v$ 在$P_n\times C_m$ 中连通，而在$u,v$ 在$P_n\times P_m$ 中不连通，故$u,v$ 在$P_n\times P_{m-\left|y_1-y_2\right|+1}$ 中连通，由定理3.4可得

$d\left(u,v\right)\le d\left(P_n\times P_{m-\left|y_1-y_2\right|+1}\right)=\max \left\{n-1,m-\left|y_1-y_2\right|\right\}$

综合两种情况，对任意$u,v$ 有

$d\left(u,v\right)\le \text{max}\left\{n-1,m\right\}.$

另一方面，取$v_0=\left(0,0\right)$ ，$v_1=\left(n-1,0\right)$ ，有

$d\left(v_0,v_1\right)=\text{max}\left\{n-1,m\right\}$

故

$d\left(P_n\times C_m\right)\ge \text{max}\left\{n-1,m\right\}$

因此，$d\left(P_n\times C_m\right)=\text{max}\left\{n-1,m\right\}$ .

当$m$ 为偶数时，$P_n\times C_m$ 有两个连通分支，且互相同构。每个分支中，任意两点$u=\left(x_i,y_p\right)$ ，$v=\left(x_j,y_q\right)$ 满足$x_i+x_j\equiv y_p+y_q\left(\mathrm{mod}2\right)$ ，且

$d\left(u,v\right)\ge \max \left\{d\left(P_n;x_i,x_j\right),d\left(C_m;y_p,y_q\right)\right\}$

因此，

$d\left(P_n\times C_m\right)\ge \text{max}\left\{n-1,d\left(C_m\right)\right\}=\max \left\{n-1,\frac{m}{2}\right\}.$

由$P_n\times C_m$ 的定义可知，针对$P_n\times C_m$ 的单独的一个分支类似于$m$ 为奇数时的讨论可以得到

$d\left(P_n\times C_m\right)\le \max \left\{n-1,\frac{m}{2}\right\}$

从而$d\left(P_n\times C_m\right)=\max \left\{n-1,\frac{m}{2}\right\}$ 。

定理得证。

我们进一步研究$P_n\times C_m$ 在删除若干节点后的直径变化。Shiu等人在文章中指出，

• 当$m$ 为偶数时，$P_n\times C_m\cong CP\left(n,\frac{m}{2}\right)\cup CP\left(n,\frac{m}{2}\right)$ ，即它同构于两个互不相交的、同构的$CP\left(n,\frac{m}{2}\right)$ 图。

• 当$m$ 为奇数时，$P_n\times C_m\cong CP\left(n,m\right)$ ，即，它同构于一个$CP\left(n,m\right)$ 图。

其中，对于$n\ge 2$ 且$m\ge 2$ ，Palisade图(palisadegraph)$P\left(n,m\right)$ 的定义如下：

(1) 顶点集：$\left\{u_{2i,j}|0\le i\le \lfloor \frac{n-1}{2}\rfloor ,0\le j\le m\right\}\cup \left\{u_{2i+1,j}|0\le i\le \lfloor \frac{n-2}{2}\rfloor ,0\le j\le m-1\right\}$ ，

(2) 边集：$\left\{u_{2i+1,j}{u}_{2i,j},u_{2i+1,j}{u}_{2i,j+1},u_{2i+1,j}{u}_{2i+2,j},u_{2i+1,j}{u}_{2i+2,j+1}|0\le i\le \lfloor \frac{n-2}{2}\rfloor ,0\le j\le m-1\right\}$ .

通过将$P\left(n,m\right)$ 的首列与末列对应顶点(即$u_{2i,0}$ 与$u_{2i,m}$ )重合(或等同)，得到的图称为CircularPalisade图(circularpalisadegraph)，记为$CP\left(n,m\right)$ 。

由此定义我们可以验证：当$m$ 为奇数时，$P_n\times C_m$ 为连通的连通度为2，当$m$ 为偶数时，$P_n\times C_m$ 有两个相互同构的连通分支且每个连通分支的连通度都为2。其中图的连通度是指为了使图不再连通或变为平凡图所需删除的最少顶点数。由$k$ -容错直径的定义可知我们只需讨论$k=2$ 。

我们首先分析基础情形$P_3\times C_m$ 与$P_2\times C_m$ 的2-容错直径，其结论是研究一般$P_n\times C_m$ 容错性质的基础。

引理3.7$P_3\times C_m$ 与$P_2\times C_m$ 的2-容错直径满足：

$D_2\left(P_3\times C_m\right)=D_2\left(P_2\times C_m\right)=\{\begin{array}{l}2m-2,如果m�奇�,\\ m-2,如果m�偶�\end{array}$

证明：我们通过结构图示展示其证明思路。

首先我们先分析一般的$P_n\times C_m$ 结构：

当$m$ 为奇数时：

由$P_2\times C_m$ 实际上构成一个$2m$ 圈，故在$P_n\times C_m$ 的坐标表示中相邻的两行构成的子图都是一个$C_{2m}$ ，且每相邻的两个圈共用$m$ 个点。因此我们可以考虑观察将其画成$n-1$ 个圈相扣的形式，如图2。

(a) $P_4\times C_5$ (b) $P_4\times C_5$ Drawn in the form of three $C_{10}$ interlocking sections

(a) $P_4\times C_5$ (b) $P_4\times C_5$ 绘制为3个$C_{10}$ 相扣的形式

Figure 2. The 2 forms of $P_3\times C_5$

图2. $P_3\times C_5$ 的两种形式

(a) $P_4\times C_8$

(a) $P_4\times C_8$

(b) $P_4\times C_8$ drawn in the form of three$C_4$ interlocking sections

(b) $P_4\times C_8$ 绘制为3个$C_4$ 相扣的形式

Figure 3. The 2 forms of $P_4\times C_8$

图3. $P_4\times C_8$ 的两种形式

当$m$ 为偶数时：

此时图有二连通分支，且两分支同构，每一分支都是$n-1$ 个$C_m$ 相扣，如图3。

在探究完图的结构后，我们来看$n=2$ 和3的情况：

当$m$ 为奇数时：

$n=2$ 时，图是一个$C_{2m}$ ，显然删去任意一个顶点都会导致圈结构退化为线性结构。此时直径变为$2m-2$ 。

$n=3$ 时，我们注意到图中有二度顶点与四度顶点，其中四度顶点是由于两圈相扣时共用顶点，由两个二度顶点合并而来。而容错直径要求最坏情况下图的直径。故我们令四度顶点为故障顶点，并在图中删去，此时$P_3\times C_m$ 的两个圈会同时断开，退化为线性结构，故直径也为$2m-2$ 。

当$m$ 为偶数时：

基于前面的分析，我们考虑其一个连通分支。

$n=2$ 时，一个连通分支是一个$C_m$ ，删去任意一个顶点都会导致圈结构退化为线性结构。此时直径变为$2m-2$ 。

$n=3$ 时，我们同样删去四度顶点。此时圈结构也会退化为线性结构，直径变为$m-2$ 。

通过对图示结构的分析可知，在所有单点故障场景下，图的最大直径均由上述情况所界定，故引理得证

基于引理3.7，我们可以推导出一般$P_n\times C_m$ 的容错直径。

定理3.8$P_n\times C_m$ 的2-容错直径为$D_2\left(P_n\times C_m\right)=\{\begin{array}{l}\max \left\{n-1,m+1\right\},如果m�奇�\\ \max \left\{n-1,\frac{m}{2}+1\right\},如果m�偶�\end{array}$ ，$n>3$

证明：由于$P_n\times C_m$ 的连通度为2，则我们只需要讨论删除一个顶点后图$P_n\times C_m$ 的直径的性质。

证明主要以图示展示证明思路。

首先，$n>4$ 时，$P_n\times C_m$ 与$P_2\times C_m$ 时不同，$P_2\times C_m$ 删去一个四度顶点后会使整个图退化为路，$P_n\times C_m$ 中删去一个顶点不会影响整个图的性质。由直积图的定义，$P_n\times C_m$ 中的2度顶点为${\displaystyle {\cup }_{i=0}^{n-1}\left\{\left(u_0,v_i\right)\right\}}{\displaystyle \cup {\displaystyle {\cup }_{i=0}^m\left\{\left(u_{n-1},v_m\right)\right\}}}$ ，当$n\ge 4$ 时，$P_n\times C_m$ 中删除任意一个2度顶点后的子图依然是2-连通的，而考虑绘制成圈的情况时，$P_n\times C_m$ 中删除最内或最外圈的4度顶点$\left({\displaystyle {\cup }_{i=0}^{n-1}\left\{\left(u_1,v_i\right)\right\}}{\displaystyle \cup {\displaystyle {\cup }_{i=0}^m\left\{\left(u_{n-2},v_m\right)\right\}}}\right)$ 后的子图会产生1度顶点，即悬挂顶点。因此，$P_n\times C_m$ 的2-容错直径，我们只需讨论$P_n\times C_m$ 中删除最内或最外圈的一个4度顶点的情况。由前面分析的$P_n\times C_m$ 的结构的相似性，我们以$P_5\times C_5$ 为例演示删点的影响(如图4)。

Figure 4. $P_5\times C_5$ after deleting a 4-degree vertex

图4. $P_5\times C_5$ 删去四度点后的图示

由$P_n\times C_m$ 的定义可知，m为奇数和偶数时$P_n\times C_m$ 的结构是不同的，因此我们对m分两种情况如下：

情形一：$m$ 为奇数

当$m$ 为奇数时，由于图的结构，删除一个节点不会完全阻断不同行之间的连通性。我们考虑两种顶点对：

第一种，不同圈上的两点，由于其取路径会跨越至多$n-1$ 个圈，故对这类点对$u,v$ ，$D_2\left(P_n\times C_m,u,v\right)\le n-1$ 。

第二种，同一圈上的两点，显然在同一圈内取路径会比通过其他的圈上绕着取短的多，而由图4所示，不考虑悬挂顶点，删去顶点后会新形成一个$C_{2m}$ ，因此不考虑悬挂顶点，任意同圈的点$u,v$ ，$D_2\left(P_n\times C_m,u,v\right)\le m$ 。

而考虑入悬挂顶点，悬挂顶点$w$ 先通过一步走进圈内的顶点$w_1$ ，而$w_1$ 到别的同圈顶点的距离小于等于$m$ ，故悬挂顶点到相邻圈内的任意顶点$u$ 的距离满足$D_2\left(P_n\times C_m,w,u\right)\le m+1$ 。故此时对$u,v$ 同圈或是悬挂顶点，$D_2\left(P_n\times C_m,u,v\right)\le m+1$ 。

综上，$D_2\left(P_n\times C_m,u,v\right)\le \max \left\{n-1,m+1\right\}$ 。且$n-1$ 与$m+1$ 都取得到($m+1$ 取在悬挂顶点到其相邻顶点所在圈并与其取到直径的点，$n-1$ 取在最内侧的圈上点到最外侧的圈上的点的某条路径)，并且这对任意两个顶点对都成立，因此

$D_2\left(P_n\times C_m\right)=\max \left\{n-1,m+1\right\}$

则$m$ 为奇数时定理得证。

情形二：$m$ 为偶数

此时每个连通分支结构与$m$ 为奇数时类似，但组成连通分支的圈是$C_m$ ，故作与奇数时相仿的过程，得：

$D_2\left(P_n\times C_m\right)=\max \left\{n-1,\frac{m}{2}+1\right\}$

至此，定理得证。

3.3. $C_n\times C_m$ 中的直径

本节研究两个圈图$C_n$ 与$C_m$ 的张量积$C_n\times C_m$ 的直径性质。我们继续使用坐标表示法，其中$i\in V\left(C_n\right)={\mathbb{Z}}_n$ ，$j\in V\left(C_m\right)={\mathbb{Z}}_m$ 。根据$n$ 和$m$ 的奇偶性不同，我们分三种情况描述如下结论。

定理3.9$C_n\times C_m$ 的直径为：

(1) 当$n,m$ 均为奇数时，$C_n\times C_m$ 的直径如下：

$d\left(C_n\times C_m\right)=\min \left\{\max \left\{\frac{m-1}{2},n\right\},\max \left\{\frac{n-1}{2},m\right\},\max \left\{n-1,m-1\right\}\right\}.$

(2) 当$n,m$ 为一奇一偶时，$C_n\times C_m$ 的直径如下：

$d\left(P_n\times C_m\right)=\{\begin{array}{l}\max \left\{\frac{n}{2},m\right\},如果m�奇�且n�偶�\\ \max \left\{\frac{m}{2},n\right\},如果m�偶�且n�奇�\end{array}.$

(3) 当$n,m$ 均为偶数时，$C_n\times C_m$ 的直径为$d\left(C_n\times C_m\right)=\max \left\{\frac{m}{2},\frac{n}{2}\right\}$ 。

证明：对任意两点$u=\left(x_i,y_p\right)$ ，$v=\left(x_j,y_{2q}\right)$ 有

$d\left(C_n;x_i,x_j\right)=\min \left\{\left|x_i-x_j\right|,n-\left|x_i-x_j\right|\right\},d\left(C_m;y_p,y_q\right)=\min \left\{\left|y_p-y_q\right|,m-\left|y_p-y_q\right|\right\}.$

(1) 当$n,m$ 均为奇数时：首先，取$v_1=\left(0,0\right)$ ，$v_2=\left(1,m-1\right)$ ，由定理3.5可得：

$d\left(C_n\times C_m;v_1,v_2\right)=\max \left\{n-1,m-1\right\},$

因此

$d\left(C_n\times C_m\right)\ge d\left(C_n\times C_m;v_1,v_2\right)\ge \max \left\{n-1,m-1\right\}.$

回顾$v_1=\left(0,0\right)$ ，若$\frac{n-1}{2}\equiv 0\left(\mathrm{mod}2\right)$ ，则取$u=\left(\frac{n-1}{2},0\right)$ ；若$\frac{n-1}{2}\equiv 1\left(\mathrm{mod}2\right)$ ，则取$u=\left(\frac{n+1}{2},0\right)$ ，由定理3.5可得

$d\left(C_n\times C_m;v_1,u\right)=\frac{n-1}{2}$

令$u_1=\left(1,0\right)$ ，运用定理3.5可得$d\left(v_1,u_1\right)=m$ ，因此，

$d\left(C_n\times C_m\right)\ge d\left(v_1,u\right),d\left(C_n\times C_m\right)\ge d\left(v_1,u_1\right).$

故，$d\left(C_n\times C_m\right)\ge \max \left\{\frac{m-1}{2},n\right\},d\left(C_n\times C_m\right)\ge \max \left\{\frac{n-1}{2},m\right\}$ ，即

$d\left(C_n\times C_m\right)\ge \min \left\{\max \left\{\frac{m-1}{2},n\right\},\max \left\{\frac{n-1}{2},m\right\}\right\}.$

至此，$d\left(C_n\times C_m\right)\ge \min \left\{\max \left\{\frac{m-1}{2},n\right\},\max \left\{\frac{n-1}{2},m\right\},\max \left\{n-1,m-1\right\}\right\}$ ，这是直径的一个下界。

另一方面，由于$P_n\times C_m\subseteq C_n\times C_m$ 且$P_m\times C_n\subseteq C_n\times C_m$ ，有：

$d\left(C_n\times C_m;u,v\right)\le \text{d}\left(P_n\times C_m;u,v\right)\le d\left(P_n\times C_m\right)=\max \left\{n-1,m\right\},$

$d\left(C_n\times C_m;u,v\right)\le d\left(P_m\times C_n;u,v\right)\le d\left(P_m\times C_n\right)=\max \left\{n,m-1\right\}.$

因此可得：

$d\left(u,v\right)\le \min \left\{\max \left\{n-1,m\right\}\max \left\{m-1,n\right\}\right\}=\max \left\{n-1,m-1\right\}.$

因此由$u$ 和$v$ 的任意性，可得$d\left(C_n\times C_m\right)\le \max \left\{n-1,m-1\right\}$ .

由$C_n\times C_m$ 的定义可知路径$u\to v$ ，记为$P_{u\to v}$ 满足如下：

$P_{u\to v}\in \left\{P_{d\left(P_n;x_i,x_j\right)}\times C_m,C_n\times P_{d\left(P_m;y_p,x_q\right)},P_{n-d\left(P_n;x_i,x_j\right)}\times C_m,C_n\times P_{m-d\left(P_m;y_p,x_q\right)}\right\},$

因此，

$d\left(C_n\times C_m;u,v\right)\le \min \left\{d\left(P_{\lfloor \frac{n}{2}\rfloor +1}\times C_m\right),d\left(C_n\times P_{\lfloor \frac{m}{2}\rfloor +1}\right)\right\}=\min \left\{\max \left\{\frac{m-1}{2},n\right\},\max \left\{\frac{n-1}{2},m\right\}\right\}.$

至此，$d\left(C_n\times C_m\right)\le \min \left\{\max \left\{\frac{m-1}{2},n\right\},\max \left\{\frac{n-1}{2},m\right\},\max \left\{n-1,m-1\right\}\right\}$ ，这是直径的一个上界。

此处的上界与前面已证的下界一致，故

$d\left(C_n\times C_m\right)=\min \left\{\max \left\{\frac{m-1}{2},n\right\},\max \left\{\frac{n-1}{2},m\right\},\max \left\{n-1,m-1\right\}\right\}.$

则定理中(1)得证。

(2) 不妨设$n$ 为偶数，$m$ 为奇数。由$C_n\times C_m$ 的定义可知路径$u\to v$ ，记为$P_{u\to v}$ 满足如下：

$P_{u\to v}\in P_{d\left(C_n\right)+1}\times C_m,$

因此，$d\left(C_n\times C_m;u,v\right)\le d\left(P_{d\left(C_n\right)+1}\times C_m\right)$ ，因此由$u$ 和$v$ 的任意性，可得

$d\left(C_n\times C_m\right)\le d\left(P_{d\left(C_n\right)+1}\times C_m\right)=\max \left\{\frac{n}{2},m\right\}.$

另一方面，由定理3.7可知

$d\left(C_n\times C_m;u,v\right)\ge \max \left\{d\left(C_n;x_i,x_j\right),d\left(C_m;y_p,y_q\right)\right\},$

此由$u$ 和$v$ 的任意性，可得

$d\left(C_n\times C_m\right)\ge d\left(u,v\right)\ge \max \left\{d\left(C_n;x_i,x_j\right),d\left(C_m;y_p,y_q\right)\right\}\ge \max \left\{d\left(C_n\right),d\left(C_m\right)\right\}=\max \left\{\frac{n}{2},\frac{m}{2}\right\}.$

回顾$v_1=\left(0,0\right),u_1=\left(1,0\right)$ ，对其应用定理3.5可得$d\left(C_n\times C_m\right)\ge d\left(v_1,u_1\right)\ge \max \left\{m,1\right\}=m$ 。因此，

$d\left(C_n\times C_m\right)\ge d\left(u,v\right)\ge \max \left\{\frac{n}{2},m\right\}.$

至此，有$d\left(C_n\times C_m\right)=\max \left\{\frac{n}{2},m\right\}$

而$n$ 为奇数，$m$ 为偶数时过程与上述完全相同，故定理中(2)得证。

(3) 当$n,m$ 均为偶数时，由$C_n\times C_m$ 的定义可知该图不连通，但其两个连通分支互相同构。在每个连通分支内，由前面的证明可知

$d\left(C_n\times C_m;u,v\right)=\max \left\{d\left(C_n;x_i,x_j\right),d\left(C_m;y_p,y_q\right)\right\}$

对该式取最大值即得：

$d\left(C_n\times C_m\right)=\max \left\{\frac{n}{2},\frac{m}{2}\right\}.$

定理(3)得证，故定理得证。

4. 总结与讨论

本文系统研究了路、圈的直积图的直径与容错直径性质。通过深入的图结构分析与严谨的数学推导，我们取得了以下主要成果：

1) 直积图$P_n\times P_m$ 方面：我们精确给出了其直径表达式$d\left(P_n\times P_m\right)=\text{ma}x\left\{n-1,m-1\right\}$ ，并证明了其1-容错直径等于其直径，即$D_1\left(P_n\times P_m\right)=d\left(P_n\times P_m\right)$ 。此外，我们推导了该直积图中两点间距离计算的一般公式，该公式系统地处理了顶点坐标奇偶性差异及图中是否存在奇圈等关键情形。

2) 直积图$P_n\times C_m$ 方面：其直径与容错直径的性质显著依赖于圈$C_m$ 的奇偶性。当$m$ 为奇数时，直径

为$\max \left\{n-1,m\right\}$ ；当$m$ 为偶数时，直径为$\max \left\{n-1,\frac{m}{2}\right\}$ 。我们进一步分析了其在顶点删除故障下的鲁棒

性，精确给出了其2-容错直径$D_2\left(P_n\times C_m\right)$ 的值。结果表明，其容错直径可能显著大于原始直径，尤其是在$m$ 为奇数时，这揭示了其拓扑结构对故障的敏感性。而其敏感性的成因归结于其中的四度节点，在其故障的情况下，图的圈形结构会退化为线性结构，导致通信效率大大降低。导致通信效率大大降低。在网络科学角度上，此类结构在无故障时表现出良好的对称性与中等通信效率，但其鲁棒性瓶颈在于高度数枢纽节点。

3) 直积图$C_n\times C_m$ 方面：我们完整刻画了$n$ 和$m$ 在不同奇偶性组合下的直径，得到了简洁统一的表达式。结果表明，其直径由两个因子图的半周长或其组合形式决定，清晰地揭示了直积操作与原图是否存在奇圈对图连通特性的根本影响。

而相较笛卡尔积图：

1) 对路径图与路径图，直积图的直径为$d\left(P_n\times P_m\right)=\max \left\{n-1,m-1\right\}$ ，笛卡尔积为：$d\left(P_n\square P_m\right)=n+m-2$ 。

2) 对路径图与圈图，直径与容错直径依赖于圈$C_m$ 圈长的奇偶性，而笛卡尔积$P_n\square C_m$ 的直径已知为

$n-1+\lfloor \frac{m}{2}\rfloor$ 。

3) 对圈图与圈图：直积图的直径对n与m的依赖性更大，但在特定情况下大于笛卡尔积$C_n\square C_m$ 的

直径为$\lfloor \frac{n}{2}\rfloor +\lfloor \frac{m}{2}\rfloor$ 。

分析以上区别，在无故障的规则拓扑下，直积图的通信效率大致优于笛卡尔积图；然而，直积图本身不保连通性，以及其在故障后直径可能剧增的特性($D_2\left(P_3\times C_m\right)=2m-2$ )，凸显了其在容错设计上与笛卡尔积网络不同的脆弱性模式。

本研究为图论中的容错性分析提供了新的理论依据，所获得的精确公式可直接应用于评估和设计具有高容错需求的网络拓扑结构，如互连网络和通信系统。我们的工作表明，虽然直积图在连通性上可能不及笛卡尔积图，但在特定条件下(如因子图尺寸差异大时)能提供更优的无故障通信效率(更小直径)。然而，其容错直径(尤其是对枢纽节点故障的敏感性)往往劣于结构更均匀、冗余路径更多的笛卡尔积网络。这种在效率与鲁棒性之间的权衡，为网络架构师根据具体可靠性要求选择积运算类型提供了关键的理论参考。

未来研究展望：基于本文工作，一个自然的延伸方向是研究这些图积结构的宽直径(Wide Diameter)。宽直径同时衡量了网络在多路径路由下的传输效率与容错能力，对于评估现代高性能网络的整体鲁棒性具有重要意义。未来的工作可以聚焦于确定$P_n\times P_m$ 、$P_n\times C_m$ 及$C_n\times C_m$ 等图积在给定连通度下的宽直径。此外，将研究范围拓展至其他图积运算(如强积)的容错参数，或由借鉴点故障下的情况，深入探究在边故障模型下的容错直径问题，也是极具价值的后续研究方向。

致 谢

衷心感谢浙江省大学生科技创新活动计划(新苗人才计划)和浙江省大学生创新创业训练计划项目对本研究的资助与支持。同时，向所有为本研究提供指导与帮助的专家、老师和同学们致以诚挚的谢意。特别感谢允许我们转载和引用相关资料的文献作者，正是基于您们的前期贡献与无私分享，才使本研究得以顺利开展并取得成果。

基金项目

本论文由浙江省大学生科技创新活动计划(新苗人才计划) (批准号：2023R451014、2024R429A011)和浙江省大学生创新训练项目(批准号：JWXC2024101)资助。

NOTES

^*通讯作者。