有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度 Diagnosability of n-Dimensional Hypercubes and Folded Hypercubes with Missing Edges under the MM* Model

doi:10.12677/AAM.2021.101018

Advances in Applied Mathematics
Vol. 10 No. 01 ( 2021 ), Article ID: 39894 , 10 pages
10.12677/AAM.2021.101018

有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度

樊畅畅，王世英^*，马晓蕾

●How to Cite this Article

河南师范大学，数学与信息科学学院，河南新乡

收稿日期：2020年12月19日；录用日期：2021年1月15日；发布日期：2021年1月21日

摘要

一个多重处理器系统的诊断度是测量互连网络错误容忍度的一个重要研究参数。n维折叠超立方体 $F Q_{n}$ 是由n维超立方体 $Q_{n}$ 添加 $2^{n - 1}$ 条边得到。在这篇文章中，我们首先研究了 $Q_{n}$ 在MM*模型下的诊断度，证明了 $Q_{n}$ 即使存在 $n - 2$ 条遗失边仍具有强局部诊断性，并且证明了 $n - 2$ 是最优值。然后，我们研究了 $F Q_{n}$ 在MM*模型下的诊断度，证明了 $F Q_{n}$ 即使存在 $n - 1$ 条遗失边仍具有强局部诊断性，并且证明了 $n - 1$ 是最优值。

关键词

互连网络，局部诊断度，n维超立方体，n维折叠超立方体，MM*模型

Diagnosability of n-Dimensional Hypercubes and Folded Hypercubes with Missing Edges under the MM* Model

Changchang Fan, Shiying Wang^*, Xiaolei Ma

College of Mathematics and Information Science, Henan Normal University, Xinxiang Henan

Received: Dec. 19^th, 2020; accepted: Jan. 15^th, 2021; published: Jan. 21^st, 2021

ABSTRACT

Diagnosability of a multiprocessor system is an important research parameter to measure the fault tolerance of interconnection networks. The n-dimensional folded hypercube $F Q_{n}$ is obtained by adding $2^{n - 1}$ edges to the n-dimensional hypercube $Q_{n}$ . In this paper, we firstly study the diagnosability of $Q_{n}$ and prove that $Q_{n}$ has the strong local diagnosability property even if there exist $n - 2$ missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges. Then we study the diagnosability of $F Q_{n}$ and prove that $F Q_{n}$ has the strong local diagnosability property even if there exist $n - 1$ missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges.

Keywords:Interconnection Networks, Local Diagnosability, n-Dimensional Hypercubes, n-Dimensional Folded Hypercubes, MM* Model

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着互连网络变得越来越复杂，多重处理器系统的规模变得越来越庞大。一些处理器在诊断时可能会出现故障，所以发现哪些处理器发生了故障是非常重要的。只有找到了故障的处理器，整个系统诊断的可靠性才能得到保证。识别故障处理器的过程叫做系统的诊断。在之前的研究中，研究者已经提出了许多系统诊断模型，其中被广泛使用的是比较模型(MM模型)。MM模型是由Maeng和Malek首次提出的 [1]。之后，Sengupta和Dahbura [2] 提出了MM*模型，它是MM模型的一个特例。在MM*模型中，一个节点必须测试它的每一对相邻节点。Sengupta和Dahbura [2] 在MM*模型下为有n个处理器的一般诊断系统提出了一个 $O (n^{5})$ 诊断算法。在故障处理器的数量不超过t的情况下，如果所有故障的处理器可以被识别出来并且不被替换，我们就称这个系统是t-可诊断的。一个系统G的诊断度 $t (G)$ 是使得G是t-可诊断的t的最大值 [3] [4] [5] [6]。

在之前的研究中，人们一直考虑的是一个多重处理器系统的全局诊断度。在文献 [7] 中，Hau和Tan首次提出了一种测量多重处理器系统的局部诊断度的概念。这种新的概念更关注每个处理器的局部性质。在2009年，Chiang和Tan [8] 提出了一种确定系统诊断度的新方法，即延展星结构法。自此以后，该方法被广泛使用。在文献 [9] 中，Chiang等证明了 $n (n \geq 4)$ 维星图的诊断度是 $n - 1$ ，且即使它存在高达 $n - 3$ 条遗失边，仍保持强局部诊断性。Cheng等又研究了置换树生成的Cayley图 [10] 和 $(n, k)$ 星图和2树生成的Cayley图 [11]。在2018年，Wang和Ma [12] 证明了交错群图 $A G_{n}$ 在MM*模型下即使存在 $2 n - 7$ 条遗失边，仍保持强局部诊断性。在2020年，Ren和Wang [13] 证明了完全图生成的Cayley图 $C K_{n}$ 在MM*

模型下即使存在 $\frac{1}{2} n (n - 1) - 2$ 条遗失边，仍保持强局部诊断性。2020年，Wang和Ma [14] 证明了排列图 $A_{n, k}$

在MM*模型下即使存在 $(k - 1) (n - k) - 1$ 条遗失边，仍保持强局部诊断性。2020年，Zhou [15] 等证明了扩展k元n立方体 $X Q_{n}^{k}$ 在比较模型下即使存在 $4 n - 5$ 条遗失边，仍保持强局部诊断性。

n维超立方体 $Q_{n}$ 和n维折叠超立方体 $F Q_{n}$ 都有许多优良性质。比如点传递性，边传递性，递归结构，高连通性等 [16]。在这篇文章中，我们首先证明了 $Q_{n}$ 的诊断度是n，且在MM*模型下即使存在高达 $n - 2$ 条遗失边仍保持强局部诊断性并且是最优的。然后，我们证明了 $F Q_{n}$ 的诊断度是 $n + 1$ ，且在MM*模型下即使存在 $n - 1$ 条遗失边仍保持强局部诊断性并且是最优的。

2. 基本概念

我们用一个无向简单图 $G = (V, E)$ 表示一个多重处理器系统，其中点集 $V (G)$ 代表处理器，边集 $E (G)$ 代表处理器之间的通信链接。一个顶点v的度 $d_{G} (v)$ 是v在G中关联的边的数目。 $δ (G)$ 表示G的顶点的最小度。G中任意一个点v的邻集 $N_{G} (v)$ 是与v相邻的所有顶点组成的集合。对于度、邻集这些概念，在没有歧义产生时，我们通常省略下标G。如果对于所有的 $v \in V$ 都满足 $d (v) = k$ ，则这个图是k-正则的。G的一条途径是指一个有限非空序列 $P = v_{0} e_{1} v_{1} e_{2} v_{2} \dots e_{n} v_{n}$ ，它的项交替地为顶点和边，使得对 $1 \leq i \leq n$ ， $e_{i}$ 的端点是 $v_{i - 1}$ 和 $v_{i}$ ，称P是从 $v_{0}$ 到 $v_{n}$ 的一条途径。 $v_{0}$ 和 $v_{n}$ 分别称为P的起点和终点，整数n称为P的长。若途径P的顶点 $v_{0}, v_{1}, \dots, v_{n}$ 互不相同，则P称为路。我们用 $P = 〈 v_{0}, v_{1}, \dots, v_{n} 〉$ 表示一条长为n的起点是 $v_{0}$ ，终点是 $v_{n}$ 的路。假设 $V^{'}$ 是V的一个非空子集，以 $V^{'}$ 为顶点集，以两端点均在 $V^{'}$ 中的边的全体为边集所组成的子图，称为G的由 $V^{'}$ 导出的子图，记为 $G [V^{'}]$ ， $G [V^{'}]$ 称为G的导出子图。如果把G的点集任意划分为两个非空子集X和Y，总存在一条边满足其中一个端点在X中，另一个端点在Y中，那么G是连通的。一个图G的连通度 $κ (G)$ 和边连通度 $λ (G)$ 分别是把图G变成一个不连通图或仅一个点所需移除的点和边的最小数量。文中其它未定义而直接使用的符号和术语参见文献 [17]。

3. MM*模型

在MM模型中，一个处理器发送同样的任务给一对不同的邻点，然后比较它们的反馈结果。一个系统 $G = (V (G), E (G))$ 的比较方案被模型化为一个多重图，用 $M = (V (G), L)$ 表示，其中L是被标记的边集。一条被标记的边 ${(u, v)}_{w} \in L$ 代表用一个顶点w去比较两个相邻顶点u和v，这意味着 $u w, v w \in E (G)$ 。如果节点w是非故障的(故障的)，那么测试结果是可靠的(不可靠的)。如果 $u, v \in F$ 且 $w \in V (G) \ F$ ，则 ${(u, v)}_{w} \to 1$ 。如果 $u \in F$ 且 $v, w \in V (G) \ F$ ，则 ${(u, v)}_{w} \to 1$ 。如果 $v \in F$ 且 $u, w \in V (G) \ F$ ，则 ${(u, v)}_{w} \to 1$ 。如果 $u, v, w \in V (G) \ F$ ，则 ${(u, v)}_{w} \to 0$ 。 $M = (V (G), L)$ 中所有比较结果的集合称为诊断的症候，用 $σ$ 表示。如果比较 ${(u, v)}_{w}$ 不一致，则 $σ ({(u, v)}_{w}) = 1$ ；否则， $σ ({(u, v)}_{w}) = 0$ 。因此，一个症候是从L到 ${0, 1}$ 的一个函数。MM*中每个节点必须测试其任意一对相邻节点。即如果 $u w, v w \in E (G)$ ，则 ${(u, v)}_{w} \in L$ 。在系统中，所有故障处理器的集合叫作一个故障集，它可以是 $V (G)$ 的任意一个子集。在MM*模型下，对于一个给定的症候 $σ$ ，如果对任意的 ${(u, v)}_{w} \in L$ 满足 $w \in V \ F$ ， $σ ({(u, v)}_{w}) = 1$ 当且仅当 $u, v \in F$ 或 $u \in F$ 或 $v \in F$ ，则我们称故障子集 $F \subseteq V (G)$ 和 $σ$ 是一致的。我们用 $σ (F)$ 表示和F一致的所有症候的集合。设 $F_{1}$ 和 $F_{2}$ 是 $V (G)$ 中两个不同的子集。如果 $σ (F_{1}) \cap σ (F_{2}) \neq \emptyset$ ，则 $(F_{1}, F_{2})$ 是不可区分对；否则， $(F_{1}, F_{2})$ 是可区分对。 $F_{1} Δ F_{2} = (F_{1} \ F_{2}) \cup (F_{2} \ F_{1})$ 。

定理3.1 [2] [18] 一个系统 $G = (V, E)$ 在MM*模型下是t-可诊断的，当且仅当对于V的每一对不同的故障子集 $F_{1}$ 和 $F_{2}$ ，其中 $| F_{1} | \leq t$ ， $| F_{2} | \leq t$ ，满足下列条件之一：

1) 有两个顶点 $u, w \in V \ (F_{1} \cup F_{2})$ ，有一个顶点 $v \in F_{1} Δ F_{2}$ ，使得 $u w \in E$ ， $v w \in E$ 。

2) 有两个顶点 $u, v \in F_{1} \ F_{2}$ ，有一个顶点 $w \in V \ (F_{1} \cup F_{2})$ ，使得 $u w \in E$ ， $v w \in E$ 。

3) 有两个顶点 $u, v \in F_{2} \ F_{1}$ ，有一个顶点 $w \in V \ (F_{1} \cup F_{2})$ ，使得 $u w \in E$ ， $v w \in E$ 。

4. 局部诊断度

定义4.1 [8] 系统 $G = (V, E)$ 中，如果 $x \in F_{1} Δ F_{2}$ 且对于V的每一对不同的故障子集 $F_{1}$ 和 $F_{2}$ 是可区分的，其中 $| F_{1} | \leq t$ ， $| F_{2} | \leq t$ ，则点 $x$ 是局部t-可诊断的。

引理4.1 [8] 一个系统 $G = (V, E)$ 是t-可诊断的当且仅当G中每个点都是局部t-可诊断的。

定义4.2 [8] 一个系统 $G = (V, E)$ 中，G中x点是局部t-可诊断的t的最大值被定义为点x的局部诊断度 $t_{l} (x)$ 。即 $t_{l} (x) = \max {t : G 在 x 点是局部 t - 可诊断的}$ 。

引理4.2 [8] 一个系统 $G = (V, E)$ 的诊断度 $t (G)$ 等于G中每个点的局部诊断度的最小值，即 $t (G) = \min {t_{l} (x) : 对于所有的 x \in V (G)}$ 。

定义4.3 [8] 设x是一个图 $G = (V, E)$ 中的一个点。若 $d_{G} (x) \geq n$ ，我们定义一个延展星图 $E S (x; n)$ ，其中 $d_{E S (x; n)} (x) = n$ ，点集 $V (E S (x; n)) = {x} \cup {v_{i j} : i = 1, 2, \dots, n, j = 1, 2, 3, 4}$ ，边集 $E (E S (x; n)) = {(x, v_{i 1}), (v_{i 1}, v_{i 2}), (v_{i 2}, v_{i 3}), (v_{i 3}, v_{i 4}) : i = 1, 2, \dots, n}$ 。

引理4.3 [8] 设x是系统 $G = (V, E)$ 中的一个点且 $d_{G} (x) = n$ 。如果点x在G中存在一个延展星图 $E S (x; n)$ ，则x的局部诊断度是n。

引理4.4 [8] 设x是图 $G = (V, E)$ 中的一个点。如果x的局部诊断度等于它在G中的度，即 $t_{l} (x) = d_{G} (x)$ ，则这个点x有强局部诊断性。

引理4.5 [8] 设 $G = (V, E)$ 是一个图。如果G中每个点的局部诊断度都等于它在G中的度，即对于所有的 $x \in V (G)$ 都有 $t_{l} (x) = d_{G} (x)$ ，则G有强局部诊断性。

5. n维超立方体Q_n

定义5.1 [19] 设 $n \geq 1$ 。n维超立方体 $Q_{n}$ 的点集是 $V (Q_{n}) = {u_{1} u_{2} \dots u_{n - 1} u_{n} : u_{k} \in {0, 1}, 1 \leq k \leq n}$ ，其中任意两个顶点相邻当且仅当只有一位 $u_{k} (1 \leq k \leq n)$ 是不同的。

$Q_{n}$ 是n正则的， $| V (Q_{n}) | = 2^{n}$ ， $| E (Q_{n}) | = n 2^{n - 1}$ 。 $V (Q_{n}^{k : i})$ 表示 $V (Q_{n})$ 中点的第k位是i， $1 \leq k \leq n$ ， $i \in {0, 1}$ 。 $Q_{n}^{k : i}$ 是由 $V (Q_{n}^{k : i})$ 导出的 $Q_{n}$ 的子图。 $Q_{n}$ 可以沿第k位分解为两个子图 $Q_{n}^{k : 0}$ 和 $Q_{n}^{k : 1}$ 。为了简便，我们把 $Q_{n}^{k : i}$ 简记作 $Q_{n}^{i}$ 。

引理5.1 [19] $Q_{n}^{i}$ 同构于 $Q_{n - 1}$ ，对于每个 $i \in {0, 1}$ 。

引理5.2 [16] n维超立方体是点传递的和边传递的。

引理5.3 [16] $κ (Q_{n}) = λ (Q_{n}) = n$ 。

6. n维折叠超立方体FQ_n

定义6.1 [16] 设 $n \geq 2$ 。n维折叠超立方体 $F Q_{n}$ 的点集是 $V (F Q_{n}) = {u_{1} u_{2} \dots u_{n - 1} u_{n} : u_{k} \in {0, 1}, 1 \leq k \leq n}$ ，其中两个顶点相邻当且仅当这两个点的n位中只有一位不同或全不同。

$V (F Q_{n}^{k : i})$ 表示 $V (F Q_{n})$ 中点的第k位是i， $1 \leq k \leq n$ ， $i \in {0, 1}$ 。 $F Q_{n}^{k : i}$ 是由 $V (F Q_{n}^{k : i})$ 导出的 $F Q_{n}$ 的子图。 $F Q_{n}$ 可以沿第k位分解成两个子图 $F Q_{n}^{k : 0}$ 和 $F Q_{n}^{k : 1}$ ，且 $F Q_{n}^{k : i}$ 同构于 $Q_{n - 1}$ ，对于每个 $i \in {0, 1}$ 。端点在不同子图 $F Q_{n}^{k : i}$ 和 $F Q_{n}^{k : j}$ 中的边称为外边，端点在同一个子图 $F Q_{n}^{k : i}$ 中的边称为内边。 $F Q_{n}$ 是 $n + 1$ 正则的， $| V (F Q_{n}) | = 2^{n}$ ， $| E (F Q_{n}) | = (n + 1) 2^{n - 1}$ 。为了简便，我们把 $F Q_{n}^{k : i}$ 简记为 $F Q_{n}^{i}$ 。

引理6.1 [16] n维折叠超立方体是点传递的和边传递的。

引理6.2 [16] n维折叠超立方体有下列性质：

1) $κ (F Q_{n}) = λ (F Q_{n}) = n + 1$ 。

2) $F Q_{n}^{i}$ 中每个点与 $n - 1$ 条内边关联，与2条外边关联。

3) $F Q_{n}^{i}$ 中每个点有2个外邻点。

7. n维超立方体Q_n的诊断度

引理7.1 设F是 $Q_{n} (n \geq 5)$ 中任意的遗失边集， $| F | \leq n - 2$ 。 $Q_{n} - F$ 中存在一个延展星图 $E S (x; d_{Q_{n} - F} (x))$ ，其中 $x \in V (Q_{n})$ 。

证明我们通过对n进行归纳来证明这个引理。由引理5.2， $Q_{n}$ 是点传递的。不失一般性，取 $x = 00 \dots 0 \in V (Q_{n})$ 。当 $n = 5$ ， $x = 00000$ 。我们可以在 $Q_{5}$ 中x点处找到四个延展星图 $E S (00000; 5)$ (见图1~4)。显然，这些图中除了与00000关联的边外，其它所有边都不相同。由 $| F | \leq n - 2 = 3$ ，我们可以在 $Q_{5}$ 中x点处找到一个不包含遗失边F的延展星图 $E S (x; d_{Q_{5} - F} (x))$ 。假设定理对于 $Q_{n - 1}$ 成立，即当 $| F | \leq n - 3$ 且 $n \geq 6$ 时，在 $Q_{n - 1} - F$ 中x点处存在一个延展星图 $E S (x; d_{Q_{n - 1} - F} (x))$ 。现在我们证明定理对于 $Q_{n} (n \geq 6)$ 成立。 $Q_{n}$ 可以沿第n位分解成两个同构的子图 $Q_{n}^{0}$ 和 $Q_{n}^{1}$ 。由引理5.1， $Q_{n}^{i}$ 同构于 $Q_{n - 1} (i = 0, 1)$ 。假设 $F_{i} = F \cap E (Q_{n}^{i})$ ， $| F_{0} | = \max {| F_{0} |, | F_{1} |}$ 。由于 $| F | \leq n - 2$ ， $| F_{i} | \leq n - 2$ 对于 $i \in {0, 1}$ 。令 $x^{'}$ 是x在 $Q_{n}^{1}$ 中的邻点。由 $x = 00 \dots 00 \in V (Q_{n}^{0})$ ，于是， $x^{'} = 00 \dots 01 \in V (Q_{n}^{1})$ 。我们使用 $P_{x^{'}}$ 代表以 $x^{'}$ 作为起始点的路。为了证明这个引理，我们首先需要在 $Q_{n}^{0} - F_{0}$ 中x点处找一个延展星图 $E S (x; d_{Q_{n}^{0} - F_{0}} (x))$ ，然后在 $Q_{n}^{1} - F_{1}$ 中找一条三长的路 $P_{x^{'}}$ ，并连接 $P_{x^{'}}$ 到x。

Figure 1. The first extended star graph $E S (x; 5)$ of $Q_{n}$

图1. $Q_{n}$ 的第一个延展星图 $E S (x; 5)$

Figure 2. The second extended star graph $E S (x; 5)$ of $Q_{n}$

图2. $Q_{n}$ 的第二个延展星图 $E S (x; 5)$

Figure 3. The third extended star graph $E S (x; 5)$ of $Q_{n}$

图3. $Q_{n}$ 的第三个延展星图 $E S (x; 5)$

Figure 4. The fourth extended star graph $E S (x; 5)$ of $Q_{n}$

图4. $Q_{n}$ 的第四个延展星图 $E S (x; 5)$

情形1 $| F_{0} | \leq n - 3$

由归纳假设，在 $Q_{n}^{0} - F_{0}$ 中 $x = 00 \dots 0$ 点处存在一个延展星图 $A = E S (x; d_{Q_{n}^{0} - F_{0}} (x))$ 。根据n维超立方

体的定义，x在 $Q_{n}^{1}$ 中仅有一个邻点 $x^{'}$ 。如果 $x x^{'} \in F$ ，我们就不需要找一条通过 $x^{'}$ 的路。因此，假设 $x x^{'} \notin F$ 。由引理5.3， $λ (Q_{n}^{1}) = n - 1 > n - 3 \geq | F_{1} |$ 。于是， $Q_{n}^{1} - F_{1}$ 是连通的。由 $n \geq 6$ 时， $| V (Q_{n}^{1}) | = 2^{n - 1} \geq 2^{5} = 32$ ，故 $Q_{n}^{1} - F_{1}$ 中存在一条三长的路 $P_{x^{'}}$ 。所以 $P_{x^{'}} \cup {x x^{'}}$ 是 $Q_{n} - F$ 中一条四长的路。我们再把它与A相结合就

得到 $E S (x; d_{Q_{n} - F} (x))$ 。

情形2 $| F_{0} | = n - 2$

假设 $f \in F_{0}$ 且 $F^{'} = F_{0} \ {f}$ 。此时 $| F^{'} | = n - 3$ 。由 $Q_{n}^{0} ≅ Q_{n - 1}$ 和归纳假设，在 $Q_{n}^{0} - F^{'}$ 中x点处存在延

展星图 $E S (x; d_{Q_{n}^{0} - F^{'}} (x))$ 。假设 $A = E S (x; d_{Q_{n}^{0} - F^{'}} (x))$ 。如果 $f \notin E (A)$ ，我们在 $Q_{n}^{0} - F_{0}$ 中x点处得到一个延展星图 $E S (x; d_{Q_{n}^{0} - F_{0}} (x)) = A$ 。假设 $f \in E (A)$ 。若f直接与x关联，则在A中删除这条包含f的路得到

$E S (x; d_{Q_{n}^{0} - F_{0}} (x))$ 。假设f不与x关联。设f在A中一条三长的路 $P_{u}$ 中，其中 $u \in N_{Q_{n}^{0}} (x)$ 。由n维超立方体的定义， $N_{Q_{n}^{0}} (x) = N_{Q_{n}^{0}} (000 \dots 000) = {100 \dots 000, 010 \dots 000, \dots, 000 \dots 010}$ 。不失一般性，设 $u = 100 \dots 000$ ，

得到 $P_{u} = P_{100 \dots 000}$ 。我们删除A中包含f的路，然后再找到另一条没有遗失边的三路 $P_{u}$ 。由n维超立方体的定义，u在 $Q_{n}^{1}$ 中有且仅有一个邻点 $u^{'}$ ， $u^{'} = 100 \dots 001 \in V (Q_{n}^{1})$ 。设 $P_{u} = 〈 1000 \dots 00, 1000 \dots 01, 1100 \dots 01, 1110 \dots 01 〉$ ， $P_{x^{'}} = 〈 0 \dots 00001, 0 \dots 00011, 0 \dots 00111, 0 \dots 01111 〉$ 。由于 $| F | \leq n - 2$ 且 $| F_{0} | = n - 2$ ，故 $Q_{n}^{0}$ 之外没有遗失边。 $P_{u}$ 和 $P_{x^{'}}$ 是 $Q_{n} - F$ 中两条没有遗失边的点不交的三长路。然后连接 $P_{u}$ 和 $P_{x^{'}}$ 到x。因此在 $Q_{n} - F$ 中x点处得到了一个延展星图 $E S (x; d_{Q_{n} - F} (x))$ 。

当遗失边个数 $| F | = 0$ 时，由引理4.2，4.3和7.1，我们得到以下推论。

推论7.1 n维超立方体 $Q_{n} (n \geq 5)$ 的诊断度是n，即 $t (Q_{n}) = n$ 。

定理7.1 设F是 $n (n \geq 5)$ 维超立方体 $Q_{n}$ 中任意边子集且 $| F | \leq n - 2$ 。对 $Q_{n}$ 中的每个点x， $Q_{n} - F$ 有强局部诊断性，其中F的个数是最优的。

证明由引理4.3和7.1，在 $Q_{n} - F$ 中，每个点x的局部诊断度等于它的度。由引理4.4和4.5， $Q_{n} - F$ 有强局部诊断性。现在我们证明F的个数是最优的。接下来我们举例说明当 $| F | = n - 1$ 时， $Q_{n} - F$ 不具有强局部诊断性。由于 $Q_{n}$ 是点传递的，不失一般性，假设 $x = 00 \dots 0 \in V (Q_{n})$ 。我们假设 $Q_{n}$ 中 $n - 1$ 条遗失边F都与x关联，那么在 $Q_{n} - F$ 中x的度就变成了1，即 $d_{Q_{n} - F} (x) = 1$ 。假设u是x在 $Q_{n} - F$ 中唯一的邻点。令 $F_{1} = ({u} \cup N (u)) \ {x}$ ， $F_{2} = N (u)$ 。此时 $| F_{1} | = | F_{2} | = n$ 。显然， $V (Q_{n}) \ (F_{1} \cup F_{2})$ 和 $F_{1} Δ F_{2}$ 之间没有边。由定理3.1和引理4.4， $Q_{n} - F$ 中u点在MM*模型下不是局部n可诊断的。然而， $d_{Q_{n} - F} (u) = n$ 。故在 $Q_{n} - F$ 中u的局部诊断度(少于n)不等于它的度(等于n)。因此，u没有强局部诊断性。故n维超立方体有 $n - 1$ 条遗失边时，就不具有强局部诊断性了。

8. n维折叠超立方体FQ_n的诊断度

引理8.1假设F是 $F Q_{n} (n \geq 6)$ 中任意边子集， $| F | \leq n - 1$ 。 $F Q_{n} - F$ 中存在一个延展星图 $E S (x; d_{F Q_{n} - F} (x))$ ，其中 $x \in V (F Q_{n})$ 。

证明 $F Q_{n}$ 可以沿第n位分解为 $F Q_{n}^{0}$ 和 $F Q_{n}^{1}$ 两个子图。当 $i \in {0, 1}$ 时， $F Q_{n}^{i}$ 同构于 $Q_{n - 1}$ 。由于 $F Q_{n}$ 是点传递的，不失一般性，我们假定 $x = 00 \dots 00 \in V (F Q_{n}^{0})$ 。由引理6.2， $F Q_{n}^{i}$ 中每个点都有两个外部邻点。设 $y_{0}$ 、 $y_{1}$ 是x在 $F Q_{n}^{1}$ 中的邻点。假设 $y_{0} = 00 \dots 01$ ， $y_{1} = 11 \dots 11$ 。设 $F_{i} = F \cap E (F Q_{n}^{i})$ 对于 $i \in {0, 1}$ ， $| F_{0} | = \max {| F_{0} |, | F_{1} |}$ 。因此 $| F_{i} | \leq n - 1$ 对于 $i \in {0, 1}$ 。为了证明这个引理，我们首先需要在 $F Q_{n}^{0} - F_{0}$ 中x点

处找到一个延展星图 $E S (x; d_{F Q_{n}^{0} - F_{0}} (x))$ ，然后在 $F Q_{n}^{1} - F_{1}$ 中找两条点不交的三长路 $P_{y_{0}}$ 和 $P_{y_{1}}$ ，其中 $P_{y_{i}}$ 代

表以 $y_{i}$ 作为起始点的路 $(i \in {0, 1})$ 。最后我们连接 $P_{y_{0}}$ 和 $P_{y_{1}}$ 到x，并结合 $E S (x; d_{F Q_{n}^{0} - F_{0}} (x))$ 。因此我们就在 $F Q_{n} - F$ 中x点处找到了一个延展星图 $E S (x; d_{F Q_{n} - F} (x))$ 。

情形1 $| F_{0} | \leq n - 3$

由 $F Q_{n}^{0} ≅ Q_{n - 1}$ ， $| F_{0} | \leq n - 3$ 和引理7.1，我们在 $F Q_{n}^{0} - F_{0}$ 中x点处得到一个延展星图 $E S (x; d_{F Q_{n}^{0} - F_{0}} (x))$ 。

设 $A = E S (x; d_{F Q_{n}^{0} - F_{0}} (x))$ 。如果 $x y_{0} \in F$ 、 $x y_{1} \in F$ ，我们就不需要发现两条分别通过 $y_{0}$ 、 $y_{1}$ 的路。如果 $x y_{0}$

和 $x y_{1}$ 中仅有一条属于F，则不妨假设 $x y_{1} \in F$ 。此时我们只需要在 $F Q_{n}^{1} - F_{1}$ 中找一条以 $y_{0}$ 开头的三长路 $P_{y_{0}}$ 。由于 $λ (F Q_{n}^{1}) = λ (Q_{n - 1}) = n - 1 > n - 3 \geq | F_{1} |$ 。因此 $F Q_{n}^{1} - F_{1}$ 是连通的。当 $n \geq 6$ 时， $| V (F Q_{n}^{1}) | = 2^{n - 1} \geq 2^{5} = 32$ 。因此在 $F Q_{n}^{1} - F_{1}$ 中存在一条以 $y_{0}$ 开头的三长路 $P_{y_{0}}$ 。我们连接 $P_{y_{0}}$ 到x，然后结合A，我们就可以在 $F Q_{n} - F$ 中x点处得到一个延展星图 $E S (x; d_{F Q_{n} - F} (x))$ 。如果 $x y_{0}$ 和 $x y_{1}$ 都不属于F，此时我们需要在 $F Q_{n}^{1} - F_{1}$ 中找到一条以 $y_{0}$ 开头的三长路 $P_{y_{0}}$ 和一条以 $y_{1}$ 开头的三长路 $P_{y_{1}}$ ，且两条路是点不交的。设 $H_{i} (i \in {0, 1})$ 是由第 $n - 1$ 位是i、第n位是1的点集导出的 $F Q_{n}^{1}$ 的子图。于是， $y_{i} \in V (H_{i})$ 。由n维超立方体和折叠超立方体的定义， $H_{i}$ 同构于 $Q_{n - 2}$ 。由于 $λ (H_{i}) = λ (Q_{n - 2}) = n - 2 > n - 3 \geq | F_{1} |$ ，故 $H_{i} - F_{1}$ 是连通的。由 $n \geq 6$ 时， $| V (H_{i}) | = 2^{n - 2} \geq 2^{4} = 16$ ，因此我们可以在 $H_{i} - F_{1}$ 中找到一条以 $y_{i}$ 开头的三长路 $P_{y_{i}} (i \in {0, 1})$ 。显然，这两条三长路是点不交的，然后我们连接 $P_{y_{0}}$ 和 $P_{y_{1}}$ 到x，最后结合A。因此我们在 $F Q_{n} - F$ 中x点处得到了一个延展星图 $E S (x; d_{F Q_{n} - F} (x))$ 。

情形2 $| F_{0} | = n - 2$

设 $f \in F_{0}$ ， $F^{'} = F_{0} \ {f}$ 。故 $| F^{'} | = n - 3$ 。由 $F Q_{n}^{0} ≅ Q_{n - 1}$ 和引理7.1，在 $F Q_{n}^{0} - F^{'}$ 中x点处存在延展星

图 $E S (x; d_{F Q_{n}^{0} - F^{'}} (x))$ ，设 $A = E S (x; d_{F Q_{n}^{0} - F^{'}} (x))$ 。如果 $f \notin E (A)$ ，则 $E S (x; d_{F Q_{n}^{0} - F_{0}} (x)) = A$ 。假定 $f \in E (A)$ 。

如果f与x关联，我们删除这条包含f的路。假定f不与x关联。令f在A中一条三长路 $P_{u}$ 中， $u \in N_{F Q_{n}^{0}} (x)$ 。由n维折叠超立方体的定义， $N_{F Q_{n}^{0}} (x) = {100 \dots 000, 010 \dots 000, \dots, 000 \dots 010}$ 。不失一般性，设 $u = 100 \dots 000$ 。我们得到 $P_{u} = P_{100 \dots 000}$ 。我们需要找到另一条没有遗失边的三长路 $P_{u}$ 。由n维折叠超立方体的定义，u在 $F Q_{n}^{1}$ 中有两个邻点 $u_{0}$ ， $u_{1}$ 。不妨设 $u_{0} = 011 \dots 111$ ， $u_{1} = 100 \dots 001$ 。设 $H_{i j}$ 是由第1位是i，第2位是j，第n位是1的点集导出的 $F Q_{n}^{1}$ 的子图，其中 $i, j \in {0, 1}$ 。由n维超立方体和折叠超立方体的定义， $H_{i j}$ 同构于 $Q_{n - 3}$ 。于是， $u_{0} \in V (H_{01})$ ， $u_{1} \in V (H_{10})$ ， $y_{0} \in V (H_{00})$ ， $y_{1} \in V (H_{11})$ 。由于 $λ (H_{i j}) = λ (Q_{n - 3}) = n - 3 >$ $1 \geq | F_{1} |$ ，故 $H_{i j} - F_{1}$ 是连通的。由 $n \geq 6$ ， $| V (H_{i j}) | = 2^{n - 3} \geq 2^{3} = 8$ 。因此我们可以在 $H_{01} - F_{1}$ 中找到一条二长路 $P_{u_{0}}$ ， $H_{10} - F_{1}$ 中找到一条二长路 $P_{u_{1}}$ ， $H_{00} - F_{1}$ 中找到一条三长路 $P_{y_{0}}$ ， $H_{11} - F_{1}$ 中找到一条三长路 $P_{y_{1}}$ 。显然，这四条路是点不交的。注意到 $| F | - | F_{0} | \leq 1$ 。如果存在某个 $i \in {0, 1}$ 使得 $u u_{i} \in F$ ，那么 $u u_{j} \notin F$ ， $j \in {0, 1} \ {i}$ 。然后我们连接 $P_{u_{j}}$ 与u得到一条没有遗失边的三长路 $P_{u}$ 。如果存在某个 $i \in {0, 1}$ 使得 $x y_{i} \in F$ ，那么我们就不需要找以 $y_{i}$ 开始的路。否则，我们需要连接 $P_{y_{0}}$ 、 $P_{y_{1}}$ 到x。最后我们在 $F Q_{n} - F$ 中x点处得到一个延展星图 $E S (x; d_{F Q_{n} - F} (x))$ 。

情形3 $| F_{0} | = n - 1$

设 $f, f^{'} \in F_{0}$ ， $F^{'} = F_{0} \ {f, f^{'}}$ 。故 $| F^{'} | = n - 3$ 。由 $F Q_{n}^{0} ≅ Q_{n - 1}$ 和引理7.1，在 $F Q_{n}^{0} - F^{'}$ 中x点处存在

延展星图 $E S (x; d_{F Q_{n}^{0} - F^{'}} (x))$ ，设 $A = E S (x; d_{F Q_{n}^{0} - F^{'}} (x))$ 。如果x与遗失边 ${f, f^{'}}$ 关联，则我们删除有遗失

边的路。假定x不与遗失边 ${f, f^{'}}$ 关联。如果f和 $f^{'}$ 中至多有一条属于A，证明类似于情形2。故我们假设f和 $f^{'}$ 分别属于A中两条不同的路 $P_{u}$ 和 $P_{v}$ ，其中 $u, v \in N_{F Q_{n}^{0}} (x)$ 。我们删除这两条包含遗失边的路，再重新找两条不含遗失边的路 $P_{u}$ 和 $P_{v}$ 。由n维折叠超立方体的定义， $N_{F Q_{n}^{0}} (x) = {100 \dots 000, 010 \dots 000, \dots, 000 \dots 010}$ 。不失一般性，设 $u = 100 \dots 000$ ， $v = 010 \dots 000$ 。于是， $P_{u} = P_{100 \dots 000}$ ， $P_{v} = P_{010 \dots 000}$ 。不妨设 $u_{0} = 100 \dots 001$ 是u在 $F Q_{n}^{1}$ 中的一个邻点， $v_{0} = 010 \dots 001$ 是v在 $F Q_{n}^{1}$ 中的一个邻点。设 $H_{i j} (i, j \in {0, 1})$ 是由第1位是i，第2位是j，第n位是1的点集导出的 $F Q_{n}^{1}$ 的子图。由n维超立方体和折叠超立方体的定义， $H_{i j}$ 同构于 $Q_{n - 3}$ 。于是， $u_{0} \in V (H_{10})$ ， $v_{0} \in V (H_{01})$ ， $y_{0} \in V (H_{00})$ ， $y_{1} \in V (H_{11})$ 。因为 $| F | - | F_{0} | = 0$ ，所以 $H_{i j} - F_{1}$ 是连通的。由 $n \geq 6$ ， $| V (H_{i j}) | = 2^{n - 3} \geq 2^{3} = 8$ 。因此我们可以在 $H_{10} - F_{1}$ ， $H_{01} - F_{1}$ ， $H_{00} - F_{1}$ 和 $H_{11} - F_{1}$ 中分别找到一条二长路 $P_{u_{0}}$ ，二长路 $P_{v_{0}}$ ，三长路 $P_{y_{0}}$ 和三长路 $P_{y_{1}}$ 。显然，这些路是点不交的。我们分别连接 $P_{u_{0}}$ 到u， $P_{v_{0}}$ 到v， $P_{y_{0}}$ 到x， $P_{y_{1}}$ 到x。于是，我们就在 $F Q_{n} - F$ 中x点处得到了一个延展星图 $E S (x; d_{F Q_{n} - F} (x))$ 。

当遗失边个数 $| F | = 0$ 时，由引理4.2，4.3和8.1，我们得到以下推论。

推论8.1n维折叠超立方体 $F Q_{n} (n \geq 6)$ 的诊断度是 $n + 1$ 。即 $t (F Q_{n}) = n + 1$ 。

定理8.1设F是 $n (n \geq 6)$ 维折叠超立方体 $F Q_{n}$ 中任意边子集且 $| F | \leq n - 1$ 。 $F Q_{n} - F$ 有强局部诊断性，其中F的个数是最优的。

证明由引理4.3和8.1，在 $F Q_{n} - F$ 中，每个点x的局部诊断度都等于它的度。由引理4.4和4.5， $F Q_{n} - F$ 有强局部诊断性。现在我们证明F的个数是最优的。接下来我们举例说明当 $| F | = n$ 时， $F Q_{n} - F$ 不具有强局部诊断性。由于 $F Q_{n}$ 是点传递的，不失一般性，假设 $x = 00 \dots 00 \in V (F Q_{n})$ 。我们假设 $F Q_{n}$ 中n条遗失边F都与x关联，那么在 $F Q_{n} - F$ 中x的度就变成了1。即 $d_{F Q_{n} - F} (x) = 1$ 。假设u是x在 $F Q_{n} - F$ 中唯一的邻点。令 $F_{1} = ({u} \cup N (u)) \ {x}$ ， $F_{2} = N (u)$ 。此时 $| F_{1} | = | F_{2} | = n + 1$ 。显然， $V (F Q_{n}) \ (F_{1} \cup F_{2})$ 和 $F_{1} Δ F_{2}$ 之间没有边。由定理3.1和引理4.4， $F Q_{n} - F$ 中u在MM*模型下不是局部 $n + 1$ 可诊断的。然而， $d_{F Q_{n} - F} (u) = n + 1$ 。故在 $F Q_{n} - F$ 中u的局部诊断度(少于 $n + 1$ )不等于它的度(等于 $n + 1$ )。因此，u没有强局部诊断性。故n维折叠超立方体有n条遗失边时，就不具有强局部诊断性了。

9. 结论

在这篇文章中，我们研究了n维超立方体和n维折叠超立方体在MM*模型下的局部诊断度。我们证明了n维超立方体 $Q_{n}$ 的诊断度是n，n维折叠超立方体 $F Q_{n}$ 的诊断度是 $n + 1$ ，以及即使 $Q_{n}$ 和 $F Q_{n}$ 中分别存在高达 $n - 2$ 和 $n - 1$ 条遗失边，它们仍保持这种强的性质。因此，在n维超立方体和n维折叠超立方体的遗失边数分别不超过 $n - 2$ 和 $n - 1$ 的条件下，它们的诊断度等于每个处理器剩余度的最小值。

基金项目

国家自然科学基金资助项目(61772010)。

文章引用

樊畅畅,王世英,马晓蕾. 有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度
Diagnosability of n-Dimensional Hypercubes and Folded Hypercubes with Missing Edges under the MM* Model[J]. 应用数学进展, 2021, 10(01): 150-159. https://doi.org/10.12677/AAM.2021.101018

参考文献

1. Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors Systems. Proceeding of the 11th International Symposium on Fault-Tolerant Computing, Vol. 11, 173-175.

2. Sengupta, A. and Dahbura, A. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. https://doi.org/10.1109/12.177309

3. Fan, J.X. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. https://doi.org/10.1109/TPDS.2002.1041887

4. Gu, M.-M., Hao, R.-X., Feng, Y.-Q. and Yu, A.-M. (2018) The 3-Extra Connectivity and Faulty Diagnosability. The Computer Journal, 61, 672-686. https://doi.org/10.1093/comjnl/bxx089

5. Gu, M.-M., Hao, R.-X. and Zhou, S.M. (2019) Fault Diagnosability of Data Center Networks. Theoretical Computer Science, 776, 138-147. https://doi.org/10.1016/j.tcs.2019.01.020

6. Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. https://doi.org/10.1109/TC.2005.19

7. Hsu, G.-H. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. https://doi.org/10.1109/TPDS.2007.1022

8. Chiang, C.-F. and Tan, J.J.M. (2009) Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers, 58, 251-259. https://doi.org/10.1109/TC.2008.158

9. Chiang, C.-F., Hsu, G.-H., Shih, L.-M. and Tan, J.J.M. (2012) Diagnosability of Star Graphs with Missing Edges. Information Sciences, 188, 253-259. https://doi.org/10.1016/j.ins.2011.11.012

10. Cheng, E. and Liptak, L. (2013) Diagnosability of Cayley Graphs Generated by Transposition Trees with Missing Edges. Information Sciences, 238, 250-252. https://doi.org/10.1016/j.ins.2013.03.009

11. Cheng, E., Liptak, L. and Steffy, D.E. (2013) Strong Local Diagnosability of (n,k)-Star Graphs and Cayley Graphs Generated by 2-Trees with Missing Edges. Information Processing Letters, 113, 452-456. https://doi.org/10.1016/j.ipl.2013.03.002

12. Wang, S.Y. and Ma, X.L. (2018) Diagnosability of Alternating Group Graphs with Missing Edges. Recent Advances Electrical and Electronic Engineering, 11, 51-57. https://doi.org/10.2174/2352096510666171107155511

13. Ren, Y.X. and Wang, S.Y. (2020) Diagnosability of the Cayley Graph Generated by Complete Graph with Missing Edges under the MM* Model. The Computer Journal, 63, 1438-1447. https://doi.org/10.1093/comjnl/bxz096

14. Wang, S.Y. and Ma, X.L. (2020) Diagnosability of Arrangement Graphs with Missing Edges under the MM* Model. International Journal of Parallel, Emergent and Distributed Systems, 35, 69-80. https://doi.org/10.1080/17445760.2019.1600688

15. Zhou, Z.P., Wang, S.Y., Ma, X.L. and Ren, Y.X. (2020) Diagnosability of Expanded k-Ary n-Cubes with Missing Edges under the Comparison Model. International Journal of Parallel, Emergent and Distributed Systems, 35, 16-28. https://doi.org/10.1080/17445760.2019.1649404

16. El-Amawy, A. and Latifi, S. (1991) Properties and Performance of Folded Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2, 31-42. https://doi.org/10.1109/71.80187

17. Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York. https://doi.org/10.1007/978-1-84628-970-5

18. Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. https://doi.org/10.1109/TC.1984.1676472

19. Saad, Y. and Schultz, M.H. (1988) Topological Properties of Hypercubes. IEEE Transactions on Computers, 37, 867-872. https://doi.org/10.1109/12.2234

NOTES

^*通讯作者。

期刊菜单