MO¨ bius立方体的h-好邻条件诊断度 The h-Good-Neighbor Conditional Diagnosability of MO¨ bius Cubes

doi:10.12677/AAM.2018.71005

Advances in Applied Mathematics
Vol.07 No.01(2018), Article ID:23513,9 pages
10.12677/AAM.2018.71005

The h-Good-Neighbor Conditional Diagnosability of Möbius Cubes

Lili Li

●Abstract

●Full-Text PDF

●Full-Text HTML

●Full-Text ePUB

●Linked References

●How to Cite this Article

School of Mathematics and Statistics, Xidian University, Xi’an Shaanxi

Received: Dec. 18^th, 2017; accepted: Jan. 17^th, 2018; published: Jan. 24^th, 2018

ABSTRACT

The conditional diagnosability is an important measure of the reliability of interconnection network. The “condition” means that all adjacent processors of any processor cannot be potentially faulty at the same time. As an improvement of conditional diagnosability, h-good-neighbor conditional diagnosability has been proposed by Peng et al. under the assumption that every fault-free node has at least h fault-free neighbors, which is an important indicator of reliability of interconnection network in the case of vertices failure. In this paper, we first introduced and investigated the h-good-neighbor conditional diagnosability of Möbius Cubes ( $M Q_{n}$ ). And we showed that the h-good- neighbor conditional diagnosability of M bius Cubes is $(n - h + 1) 2^{h} - 1 (0 \leq h \leq n - 3)$ under the PMC and MM* model, which can be several times higher than the classical diagnosability of $M Q_{n}$ .

Keywords:Conditional Diagnosability, Möbius Cubes, h-Good-Neighbor Conditional Diagnosability, PMC Model, MM* Model

Möbius立方体的h-好邻条件诊断度

李莉莉

西安电子科技大学，数学与统计学院，陕西西安

收稿日期：2017年12月18日；录用日期：2018年1月17日；发布日期：2018年1月24日

摘要

条件诊断度是衡量互连网络可靠性能优劣的重要参数，“条件”意味着任何处理器的所有相邻处理器不能同时出现潜在故障。作为条件诊断度的一个改进参数，Peng等人通过限制要求每个无故障节点至少包含有h个无故障的邻点提出了h-好邻条件诊断度，是一种在节点失效的情况下衡量互连网络可靠性的重要指标。本文研究并证明了Möbius立方体( $M Q_{n}$ )在PMC模型和MM*模型下的h-好邻条件诊断度是 $(n - h + 1) 2^{h} - 1 (0 \leq h \leq n - 3)$ ，相比于传统诊断度成几何倍数的提高。

关键词 :条件诊断度，Möbius立方体，h-好邻条件诊断度，PMC模型，MM*模型

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

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

1. 引言

随着大规模集成电路和现代通讯技术的快速发展，多处理器计算机系统中处理器的数量急剧增加，连接这些处理器的互连网规模也在相应扩大。再加上各种因素及外界因素的干扰，系统不可避免的会发生故障，那么如何在系统发生故障时，仍能使系统高效、快速、准确地正常工作，减轻系统故障风险是具有极其重要的现实意义。在多处理器系统中故障诊断是一个用来分析系统故障诊断和定位能力的强有力工具。确定一个系统中的故障节点和无故障节点的过程叫做系统的故障诊断，系统可以保证确定的最大故障节点数称为系统可诊断度 [1] [2] 。

在系统故障诊断中，根据互连网络拓扑结构充分运用处理器之间的自治能力，让各个处理器相互测试，由测试结果得到准确的诊断结果。不同的测试假设导致不同的测试模型。一般常用的两种模型为PMC模型和MM*模型。1967年，Preparata et al. [1] 假设只有在处理器相邻时才可以相互测试的情况下提出了PMC模型。在该模型中，当执行测试者u是无故障时，若被测试者v是无故障的，那么测试的结果为0，否则为1，此时测试的结果是可靠的。当测试者u故障时，测试结果不定，此时测试的结果是不可靠的。1981年Malek和Maeng [3] 提出了比较模型，简称MM模型。在MM模型下，测试也是相邻处理器之间相互测试，如果执行测试者w是无故障的，那么测试的结果是可靠的，即当被测试者u，v都无故障时，测试结果为0，否则为1；反之，当测试者w故障的，测试结果是不可靠的，即测试结果不定。1992年，Sengupta和Dahbura [4] 对MM模型进行了改进，要求每一个处理器节点都必须与它的所有的相邻节点互相测试，称为MM*模型。表1描述了在PMC模型与MM*模型下相邻节点的测试结果。

由于t-可诊断的充分条件要求较高，不仅受诊断图的最小度限制，而且相比于系统中的总节点数，t

Table 1. The test results under the PMC model and MM* model

表1. PMC和 MM*模型下的测试结果

值显得非常小。如超立方网络中，t-可诊断度受其最小度限制，可诊断性 $n / 2^{n}$ 相对很小。由于系统中点数众多，出现故障的点数可能会很多，此时t-可诊断并不适用。为了进一步提高系统的可诊断度，以牺牲精确诊断为代价，Lai等人于2005年通过限制每一个节点至少有一个好的邻点提出了条件t-可诊断 [5] 。因为在实际环境中，一个点的所有的邻点同时故障的可能性相对较小，几乎可以忽略不计，故此，我们认为这种策略是可行的。但对于大规模的多处理器系统，一个节点的度远大于1，这时仍要求一个节点至少有一个好邻点相对保守，同时也无益于在实际环境中提高系统的可诊断度。于是Peng等人 [6] 提出了h-好邻条件诊断度，并同时确定了当 $0 \leq h \leq n - 3$ 时，超立方体在PMC模型下的-好邻条件可诊断度为 $(n - h + 1) 2^{h} - 1$ 。随之超立方体、k-元n-方立方体、排列组合图等网络拓扑结构在PMC模型和MM*模型下的h-好邻条件诊断度被广泛研究并确定 [7] [8] [9] [10] 。研究发现该策略诊断相对传统诊断度而言诊断能力成几何倍数的提高，大大提高了系统的可靠性。

另外，Möbius立方体网络作为超立方体网络的变体，在保留前者原有优良性能的基础上，又增加了一些新的优良性能。本文主要研究了Möbius立方体在PMC模型和MM*模型下h-好邻条件诊断度并确定了当 $0 \leq h \leq n - 3$ 时，其在PMC和MM*模型下的h-好邻条件可诊断度为 $(n - h + 1) 2^{h} - 1$ 。

2. 预备知识

对多处理器计算机系统进行理论研究时，通常可看作一个简单无向图 $G = (V, E)$ ，其中点集V代表系统中处理器的集合，边集E代表系统中处理器间的通信链路的集合。本节首先引入了本文中所应用的图论相关定义及相关性质，然后对M bius立方体网络拓扑结构进行了简要描述。

2.1. 术语和概念

在本文中图 $G = (V, E)$ 是指一个顶点集为V边集为E的无环无平行边的简单连通图。对于任意的两点u和v，如果存在边 $e = (u, v) \in E (G)$ ，则我们说他们是相邻的，也可以说边e连接了顶点u和v。对于 $\forall u \in V$ ，用 $N_{G} (u)$ 表示u在G中的邻点集。点u的度是指u所关联的边的数目，即是在 $N_{G} (u)$ 中点的数

目，记为 $d_{G} (u)$ 。 $\forall S \subseteq V$ ，用 $N_{G} (S)$ 表示 $S$ 在 $G - S$ 中的邻点集，即 $N_{G} (S) = \cup_{u \in S} N_{G} (u) - S$ 。对于图

$H = (V^{'}, E^{'})$ ， $G = (V, E)$ ，如果 $V^{'} \subseteq V$ 且 $E^{'} \subseteq E$ ，则称图H为G的子图，记为 $H \subseteq G$ 。若 $V^{'} = V$ ，此时则称子图H为G的支撑子图。对于图G中任意子集 $V^{'} \subseteq V (G)$ ，称以 $V^{'}$ 为点集，以图G中两端点均在 $V^{'}$ 的所有边为边集的子图为点集 $V^{'}$ 的导出子图，记作 $G [V^{'}]$ 。给定两个集合A，B，集合 $(A - B) \cup (B - A)$ 称为A与B的对称差，记为 $A Δ B$ 。用 $G - A$ 表示从图G中删除顶点子集A所获得的子图，记为 $\bar{A}$ 。这里涉及未提到的术语可参考文献 [11] 。

DahBura与Masson [12] 提出了一个多项式复杂度算法来检验一个系统是否是t-可诊断的。

引理2.1 [12] ：多处理器系统 $G = (V, E)$ 中，若任意一对不同的故障集 $F_{1}, F_{2} \subseteq V$ 满足 $| F_{1} |, | F_{2} | \leq t$ ，且在 $V - (F_{1} \cup F_{2})$ 和 $F_{1} Δ F_{2}$ 之间至少有一个测试，则称系统G是t-可诊断的。

Lai et al. [5] 与Sengupta等人 [4] 分别提出了在PMC模型和MM*下故障集对 $(F_{1}, F_{2})$ 可区分的充要条件。图1(a)，图1(b)分别给出了在PMC模型和MM*下可区分对 $(F_{1}, F_{2})$ 的示例说明，即引理2.2和2.3。

引理2.2 [5] ：对图 $G = (V, E)$ 的任意两个集合 $F_{1}, F_{2} \subseteq V$ ，若 $V - (F_{1} \cup F_{2})$ 中存在一个点u与点 $v \in F_{1} Δ F_{2}$ 相邻，则称 $F_{1}$ 与 $F_{2}$ 在PMC模型下是可区分的。

由引理2.1，2.2可知，若系统 $G = (V, E)$ 中任意两个不同的子集 $F_{1}, F_{2} \subseteq V$ 有 $| F_{1} |, | F_{2} | \leq t$ ，且 $F_{1}$ 与 $F_{2}$ 是可区分的，则该系统是t-可诊断的。

引理2.3 [4] ：对图 $G = (V, E)$ 的任意两个集合 $F_{1}, F_{2} \subseteq V$ ， $F_{1}, F_{2}$ 在MM*模型下可区分当且仅当以下条件至少一个成立：

Figure 1. Illustration of a distinguishable pair $(F_{1}, F_{2})$

图1. 可区分对 $(F_{1}, F_{2})$ 的说明

1) 存在点 $u \in (F_{1} Δ F_{2})$ ， $v, w \in \bar{F_{1} \cup F_{2}}$ 满足 $u w, v w \in E (G)$ 。

2) 存在点 $u, v \in (F_{1} - F_{2})$ ， $w \in \bar{F_{1} \cup F_{2}}$ 满足 $u w, v w \in E (G)$ 。

3) 存在点 $u, v \in (F_{2} - F_{1})$ ， $w \in \bar{F_{1} \cup F_{2}}$ 满足 $u w, v w \in E (G)$ 。

定义2.1 [6] ：设 $G = (V, E)$ 是一个简单无向图， $F \subseteq V$ 。若 $\forall v \in V - F$ 有 $| N (v) \cap (V - F) | \geq h$ ，则称F是图G的h-好邻条件故障集。若图G的h-好邻条件故障集F使得 $G - F$ 不连通，则称F是图G的h-好邻条件故障点割集。G的所有h-好邻条件故障点割集中最小基数称为G的h-好邻连通度，记为 $κ^{h} (G)$ 。

定义2.2 [6] ：设 $G = (V, E)$ 是一个简单无向图，若任意一对不同的h-好邻条件故障集 $F_{1}, F_{2} \subseteq V$ 满足 $| F_{1} |, | F_{2} | \leq t$ ，且 $F_{1}, F_{2}$ 是可区分的，则称图G是h-好邻条件t-可诊断的。使得图G是h-好邻条件t-可诊断的最大t值称为图G的h-好邻条件可诊断度，记作 $t_{h} (G)$ 。

2.2. Möbius立方体网络

超立方体网络 $Q_{n}$ 作为当今研究的热点，具有正则性、对称性、顶点传递性、高容错性等优良特性，正是这些特性使得它成为并行处理和并行计算系统的首选拓扑结构。但是超立方体网络同样也存在一些不足，比如其直径相对较大，在其维数增加时易造成数据传输的丢失，成本花费较高等 [13] 。因此，莫比乌斯立方体网络 [14] 作为超立方体的变体结构被提出，它有更优与超立方体的性能，尤其在直径、连通度、容错性、嵌入性等方面。

1995年，Cull和Larson [14] 提出了n-维莫比乌斯(Möbius)立方体网络，记为 $M Q_{n}$ ，具有以下性质：(详见文献 [14] )。这里用2元n序列来定义。

定义2.3 [14] ：n-维Möbius立方体网络的顶点可以由一个n位二进制串表示，即

$V = {u_{n - 1} u_{n - 2} \dots u_{0} | u_{i} \in {0, 1}, i = 0, 2, \dots, n - 1}$

点 $u = u_{n - 1} u_{n - 2} \dots u_{0} \in V (M Q_{n})$ 连接到另外n个点 $u^{i} \in V (M Q_{n})$ ( $0 \leq i \leq n - 1$ )当且仅当：

$u^{i} = {\begin{cases} u_{n - 1} u_{n - 2} \dots u_{i + 1} \bar{u_{i}} u_{i - 1} \dots u_{0}; u_{i + 1} = 0; \\ u_{n - 1} u_{n - 2} \dots u_{i + 1} \bar{u_{i} u_{i - 1} \dots u_{0}}; u_{i + 1} = 1. \end{cases}$

其中 $\bar{u_{i}} = 1 - u_{i}$ 。

根据Möbius立方体的定义，我们可以确定两个顶点是否相邻。因此，当 $u_{n} = 0$ 时，我们称网络为0-Möbius立方体(0-MQ_n)，当 $u_{n} = 1$ 时，该网络称为1-Möbius立方体(1-MQ_n)。

引理2.4 [15] ： $n \geq 3$ ，n-维Möbius立方体 $M Q_{n}$ 无三角。

引理2.5 [16] ：设 $Y \subseteq V (X Q_{n}), X Q_{n} \in H L_{n}$ ， $n \geq 1$ ，若 $δ (X Q_{n} [Y]) \geq h$ ，则 $| Y | \geq 2^{h}$ ， $h \in [0, n]$ 。

引理2.6 [17] ：若 $X Q_{n} \in {C Q_{n}, 0 - M Q_{n}, 1 - M Q_{n}, L T Q_{n}}$ ， $n \geq 2$ ，则 $κ^{h} (X Q_{n}) = 2^{h} (n - h)$ ， $h \in [0, n - 2]$ 。

3. Möbius立方体的h-好邻条件可诊断度

在本节中，我们将证明我们的主要结论：n-维Möbius立方体在PMC模型和MM*模型下的h-好邻条件诊断度。

定理3.1：n-维M bius立方体在PMC模型和MM*模型下的h-好邻条件诊断度 $t_{h} (M Q_{n})$ 的上界，即 $t_{h} (M Q_{n}) \leq 2^{h} (n - h) + 2^{h} - 1$ ， $0 \leq h \leq n, n \geq 2$ 。

证明：设 $A = {x = x_{n - 1} x_{n - 2} \dots x_{h} x_{h - 1} \dots x_{0} | x_{i} = 0, i \in {h, h + 1, \dots, n - 1}}$ ， $x_{j} \in {0, 1}$ ， $j \in {0, 1, \dots, h - 1}$ 。显

然地， $M Q_{n} [A] ≅ M Q_{h}$ ， $| A | = 2^{h}$ 。由 $M Q_{n}$ 的定义知， $A$ 的所有邻点在 $V_{k}$ 中，这里 $V_{k} = {x^{k} | x \in A}$ ， $k \in {h, h + 1, \dots, n - 1}$ 。记 $F_{1} = \cup_{h}^{n - 1} V_{k}$ ， $F_{2} = A \cup F_{1}$ 。所以有 $| F_{1} | = (n - h) 2^{h}$ ， $| F_{2} | = (n - h) 2^{h} + 2^{h}$ 。由于 $A = F_{1} Δ F_{2}$ 和 $F_{1} = N (A)$ ，所以在 $\bar{F_{1} \cup F_{2}}$ 和 $F_{1} Δ F_{2}$ 之间不存在边的连接，故根据引理2.2与2.3知， $F_{1}$ 和 $F_{2}$ 是不可区分的。如图2所示。

另一方面， $M Q_{n} [A] ≅ M Q_{h}$ ，很容易得到 $M Q_{n} [A]$ 是h-正则图，所以在A中的每个点至少有h个邻点在A中。记 $X = V (M Q_{n}) - F_{1} \cup F_{2}$ ，因为 $F_{1} \subset F_{2}$ ，所以 $X = V (M Q_{n}) - F_{2}$ 。现在我们考虑在X中的点，由X的定义知，对 $\forall x \in X$ 有 $x^{i} \in X$ ， $i \in {0, 1, \dots, h - 1}$ ，即在X中的每个点至少有h个邻点在X中。因此， $M Q_{n} - F_{1}$ 与 $M Q_{n} - F_{2}$ 的最小度都至少为h，由定义2.1知， $F_{1}$ 与 $F_{2}$ 是两个不同的h-好邻条件故障点割集。

观察到 $F_{1}$ 和 $F_{2}$ 是 $M Q_{n}$ 的两个不同的h-好邻条件故障点割集且 $| F_{1} | = (n - h) 2^{h}$ ， $| F_{2} | = (n - h) 2^{h} + 2^{h}$ ，但是 $F_{1}$ 和 $F_{2}$ 是不可区分的。因此，根据引理2.2与2.3知， $M Q_{n}$ 不是h-好邻条件 $2^{h} (n - h) + 2^{h}$ -可诊断的。即有 $t_{h} (M Q_{n}) \leq 2^{h} (n - h) + 2^{h} - 1$ 。因此，定理成立。

上述定理提供了 $M Q_{n}$ 的h-好邻条件可诊断的一个上界。下面我们分别证明在PMC模型和MM*模型下下界是可以达到的。

定理3.2：n-维Möbius立方体在PMC模型下的h-好邻条件诊断度的下界 $t_{h} (M Q_{n}) \geq 2^{h} (n - h) + 2^{h} - 1$ ， $0 \leq h \leq n - 3, n \geq 2$ 。

证明：反证法，假设 $t_{h} (M Q_{n}) < 2^{h} (n - h) + 2^{h} - 1$ ，则存在两个不可区分的h-好邻条件故障集 $F_{1}, F_{2}$ 使得 $| F_{1} |, | F_{2} | \leq 2^{h} (n - h) + 2^{h} - 1$ 。且当 $0 \leq h \leq n - 3$ 时，易知 $| V (M Q_{n}) | - | F_{1} \cup F_{2} | \geq 2^{n} - 2 (2^{h} (n - h) + 2^{h} - 1) > 0$ ，

Figure 2. Illustration of $F_{1}$ and $F_{2}$

图2. $F_{1}$ 和 $F_{2}$ 的说明

所以有 $\bar{F_{1} \cup F_{2}} \neq \emptyset$ 。因为 $F_{1}$ 与 $F_{2}$ 是不可区分的，由引理2.2可知在 $F_{1} Δ F_{2}$ 和 $\bar{F_{1} \cup F_{2}}$ 之间是不存在边的连接，因此 $N (F_{1} Δ F_{2}) \subseteq F_{1} \cap F_{2}$ 。且又因为 $F_{1}$ 与 $F_{2}$ 是两个不同的h-好邻条件故障集，所以 $M Q_{n} - F_{1}$ 与 $M Q_{n} - F_{2}$ 的最小度都至少为h，故 $F_{1} \cap F_{2}$ 是 $M Q_{n}$ 的一个h-好邻条件故障点割集。结合引理2.5和2.6得， $M Q_{n}$ 的最小点割集的基为 $(n - h) 2^{h}$ 。因此， $| F_{1} \cap F_{2} | \geq κ^{h} (M Q_{n}) = (n - h) 2^{h}$ 。

由于 $F_{1}$ 是一个h-好邻条件故障集，在 $F_{2} - F_{1}$ 中的任意点至少有h个好邻点在子图 $F_{2} - F_{1}$ 中，即 $δ (F_{2} - F_{1}) \geq h$ ，结合引理2.5有 $| F_{2} - F_{1} | \geq 2^{h}$ 。此时，

$| F_{2} | = | F_{2} - F_{1} | + | F_{1} \cap F_{2} | \geq 2^{h} + (n - h) 2^{h}$

矛盾于假设 $| F_{2} | \leq 2^{h} + (n - h) 2^{h} - 1$ 。因此，定理成立。

定理3.3：n-维Möbius立方体在MM*模型下的h-好邻条件诊断度的下界 $t_{h} (M Q_{n}) \geq 2^{h} (n - h) + 2^{h} - 1$ ， $0 \leq h \leq n - 3, n \geq 5$ 。

证明：反证法，假设 $t_{h} (M Q_{n}) < 2^{h} (n - h) + 2^{h} - 1$ ，则存在两个不可区分的h-好邻条件故障集 $F_{1}, F_{2}$ 使得 $| F_{1} |, | F_{2} | \leq 2^{h} (n - h) + 2^{h} - 1$ 。由引理2.3知，故障集对 $(F_{1}, F_{2})$ 不能满足引理2.3的任一条件，故我们将证明以下每一种情况都与假设相矛盾。

情形1： $V (M Q_{n}) = F_{1} \cup F_{2}$ 。

当 $n \geq 5, 0 \leq h \leq n - 3$ 时，因为 $V (M Q_{n}) = F_{1} \cup F_{2}$ ，此时，

$2^{n} = | V (M Q_{n}) | = | F_{1} \cup F_{2} | \leq | F_{1} | + | F_{2} | \leq 2 (2^{h} (n - h) + 2^{h} - 1) \leq 2^{n} - 2$

这与事实相矛盾。

情形2： $V (M Q_{n}) \neq F_{1} \cup F_{2}$ 。

在此情形下，我们有 $V (M Q_{n}) - F_{1} \cup F_{2} \neq \emptyset$ 。设 $W$ 是 $V (M Q_{n}) - F_{1} \cup F_{2}$ 的所有孤立点的集合。则对

$\forall w \in W$ ，有 $N_{M Q_{n}} (w) \subseteq F_{1} \cup F_{2}$ 。下面我们根据h的大小讨论以下两种情形来证明 $W = \emptyset$ 成立。

子情形2.1： $h = 1$ 。

反证法，假设 $W = \emptyset$ ，则至少存在一个孤立点 $w \in W$ 。若 $F_{1} - F_{2} = \emptyset$ ，则有 $w \in V (M Q_{n}) - F_{2}$ ， $N_{M Q_{n}} (w) \subseteq F_{2}$ 。这与 $F_{2}$ 是h-好邻条件故障集相矛盾，所以 $F_{1} - F_{2} \neq \emptyset$ 。类似地， $F_{2} - F_{1} \neq \emptyset$ 。由于 $F_{1}$ 和 $F_{2}$ 是两个不可区分的故障集，根据引理2.3得，至多存在一个点 $u \in F_{2} - F_{1}$ 使得u与w是相邻的，故恰好存在一个点 $u \in F_{2} - F_{1}$ 使得u与w是相邻的。类似地，恰好存在一个点 $v \in F_{1} - F_{2}$ 使得v与w是相邻的。因此，W中的任意点存在 $n - 2$ 个邻点在 $F_{1} \cap F_{2}$ 中。由假设知 $| F_{2} | \leq 2^{h} (n - h + 1) - 1 = 2 n - 1$ ，所以有：

$\begin{matrix} \sum_{w \in W} | N_{F_{1} \cap F_{2}} (w) | = | W | (n - 2) \leq \sum_{v \in F_{1} \cap F_{2}} d_{M Q_{n}} (v) \\ \leq | F_{1} \cap F_{2} | n \leq (| F_{2} | - 1) n \leq (2 n - 2) n \end{matrix}$

由上可得， $| W | \leq 2 n + 2$ 。如果 $V (M Q_{n}) - (F_{1} \cup F_{2} \cup W) = \emptyset$ ，则当 $n \geq 5$ 时，

$\begin{matrix} 2^{n} = | V (M Q_{n}) | = | F_{1} \cup F_{2} | + | W | \leq | F_{1} | + | F_{2} | + | W | \\ \leq 2 (2 n - 1) + 2 n + 2 < 2^{n} \end{matrix}$

不成立，所以 $V (M Q_{n}) - (F_{1} \cup F_{2} \cup W) \neq \emptyset$ 。记 $H = V (M Q_{n}) - (F_{1} \cup F_{2} \cup W)$ ，考虑到在 $V (M Q_{n}) - (F_{1} \cup F_{2})$ 中的所有孤立点都包含在W中，所以不存在孤立点在H的导出子图 $M Q_{n} [H]$ 中。由引理2.3得，在H和 $F_{1} Δ F_{2}$ 之间不存在边的连接。因为 $F_{1}$ 和 $F_{2}$ 都是1-好邻条件故障集，易知 $F_{1} \cap F_{2}$ 是 -好邻条件故障点割集。由引理2.5和2.6得， $| F_{1} \cap F_{2} | \geq 2 n - 2$ 。注意到 $| F_{1} | \leq 2 n - 1$ ， $| F_{2} | \leq 2 n - 1$ 且 $F_{1} - F_{2} \neq \emptyset$ ， $F_{2} - F_{1} \neq \emptyset$ 。因此， $| F_{1} - F_{2} | = | F_{2} - F_{1} | = 1$ ，故设 $F_{1} - F_{2} = {v_{1}}$ ， $F_{2} - F_{1} = {v_{2}}$ 。对任意点w，w与 $v_{1}, v_{2}$ 是相邻的，且有

$N_{F_{1} \cap F_{2}} (w) = d_{M Q_{n}} (w) - {v_{1}, v_{2}}$ 。由于 $V (M Q_{n})$ 中任意两个顶点之间至多有两个公共邻点，因此，至多在W中存在两个孤立点。图3给出了W的两种情形。

若 $| W | = 1$ ，不防设 $W = {w}$ ，则 $w$ 与 $v_{1}, v_{2}$ 是相邻的。由引理2.4知 $M Q_{n}$ 中无三角且任意两个顶点之间至多有两个公共邻点，故有 $N_{F_{1} \cap F_{2}} (w) \cap N_{F_{1} \cap F_{2}} (v_{1}) = \emptyset$ ， $N_{F_{1} \cap F_{2}} (w) \cap N_{F_{1} \cap F_{2}} (v_{2}) = \emptyset$ 和 $N_{F_{1} \cap F_{2}} (v_{1}) \cap N_{F_{1} \cap F_{2}} (v_{2}) \leq 1$ 。此时，当 $n \geq 4$ 时，

$\begin{matrix} | F_{2} | = | F_{1} \cap F_{2} | + | F_{2} - F_{1} | \\ \geq | N_{F_{1} \cap F_{2}} (w) | + | N_{F_{1} \cap F_{2}} (v_{1}) | + | N_{F_{1} \cap F_{2}} (v_{2}) | - 1 + 1 \\ \geq n - 2 + n - 1 + n - 1 - 1 + 1 > 2 n - 1 \end{matrix}$

这与假设 $| F_{2} | \leq 2 n - 1$ 相矛盾。

若 $| W | = 2$ ，则 $N ({v_{1}, v_{2}} \cup W) \subseteq F_{1} \cap F_{2}$ 。不妨设 $W = {w, w^{'}}$ ，则 $w^{'}$ 与 $v_{1}, v_{2}$ 是相邻的。因为 $M Q_{n}$ 中任意两个顶点之间至多有两个公共邻点，所以 $v_{1}, v_{2}, w, w^{'}$ 在 $F_{1} \cap F_{2}$ 中无公共邻点。且当 $n \geq 4$ 时，

$2 n - 1 \geq | F_{2} | = | F_{1} \cap F_{2} | + | F_{2} - F_{1} | \geq N ({v_{1}, v_{2}} \cup W) + 1 \geq n - 8 + 1 > 2 n - 1$

不成立。

子情形2.2： $h \geq 2$ 。

由于 $F_{1}$ 是 $M Q_{n}$ 的h-好邻条件故障集，所以对任意的 $x \in V (M Q_{n}) - F_{1}$ 有 $| N_{V (M Q_{n}) - F_{1}} (x) | \geq h$ 。由假设知故障集对 $(F_{1}, F_{2})$ 不满足引理2.3的任一条件，所以对于任意点 $w \in W$ ，至多存在一个邻点在 $F_{2} - F_{1}$ 中。因此， $| N_{{V (M Q_{n}) - F_{1} \cup F_{2}}} (w) | \geq h - 1 \geq 1$ ，即在 $V (M Q_{n}) - F_{1} \cup F_{2}$ 中的每个点都不是孤立点。

因此， $W = \emptyset$ 。

由 $W = \emptyset$ 知 $V (M Q_{n}) - F_{1} \cup F_{2}$ 中不存在孤立点，因此 $[V (M Q_{n}) - F_{1} \cup F_{2}]$ 中不存在边 $u v$ 使得 $u (v)$ 与

$F_{1} Δ F_{2}$ 中的某些点是相邻的。否则， $F_{1}$ 和 $F_{2}$ 是可区分的，与假设矛盾。因此，在 $V (M Q_{n}) - F_{1} \cup F_{2}$ 和 $F_{1} Δ F_{2}$ 之间不存在边。考虑到 $F_{1}$ 和 $F_{2}$ 是h-好邻条件故障集，易知 $F_{1} \cap F_{2}$ 是h-好邻条件故障点割集且 $δ (M Q_{n} [F_{2} - F_{1}]) \geq h$ ，结合引理2.5和2.6得， $| F_{2} - F_{1} | \geq 2^{h}$ ， $| F_{1} \cap F_{2} | \geq κ^{h} (M Q_{n}) = (n - h) 2^{h}$ 。此时，

$| F_{2} | = | F_{2} - F_{1} | + | F_{1} \cap F_{2} | \geq 2^{h} + (n - h) 2^{h}$

Figure 3. Illustration of the proof of $h = 1$

图3. $h = 1$ 的证明情况说明

这与假设 $| F_{2} | \leq 2^{h} + (n - h) 2^{h} - 1$ 相矛盾。

综上所述，定理成立。

由定理3.1，3.2和3.3，我们可以立即获得以下定理：

定理3.4：n-维Möbius立方体在PMC模型下的h-好邻条件诊断度 $t_{h} (M Q_{n}) = 2^{h} (n - h) + 2^{h} - 1$ ， $0 \leq h \leq n - 3, n \geq 2$ 。

定理3.5：n-维Möbius立方体在MM*模型下的h-好邻条件诊断度 $t_{h} (M Q_{n}) = 2^{h} (n - h) + 2^{h} - 1$ ， $0 \leq h \leq n - 3, n \geq 5$ 。

4. 结论

本文主要研究了n-维Möbius立方体 $M Q_{n}$ 的h-好邻条件诊断度，且分别确定了当 $n \geq 2$ 和 $n \geq 5$ 时，其在PMC和MM*模型下的h-好邻条件诊断度为 $t_{h} (M Q_{n}) = 2^{h} (n - h + 1) - 1 (0 \leq h \leq n - 3)$ 。h-好邻条件诊断度从本质上说限制的只是好的邻点，与条件t-可诊断是不同的。由于在大规模多处理器系统中，一个处理器相邻单元数远大于1，故其好的邻点会更多。所以该诊断策略更加适用于实际应用，是一个值得研究的方向，同时h-好邻条件诊断度的确定为后续算法的研究提供了更好的理论支撑。

文章引用

李莉莉. MO^¨ bius立方体的h-好邻条件诊断度
The h-Good-Neighbor Conditional Diagnosability of MO^¨ bius Cubes[J]. 应用数学进展, 2018, 07(01): 30-38. http://dx.doi.org/10.12677/AAM.2018.71005

参考文献 (References)

1. Preparata, F.P., Metze, G. and Chien, R.T. (2006) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, EC-16, 848-854.
https://doi.org/10.1109/PGEC.1967.264748

2. Hakimi, S.L. and Amin, A.T. (1974) Characterization of Connection Assignment of Diagnosable Systems. IEEE Transactions on Computers, C-23, 86-88.
https://doi.org/10.1109/T-C.1974.223782

3. Malek, M. (1980) A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems. Symposium on Computer Architecture, La Baule, 6-8 May 1980, 31-36.
https://doi.org/10.1145/800053.801906

4. Sengupta, A. and Dahbura, A.T. (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

5. 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

6. Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412.
https://doi.org/10.1016/j.amc.2012.03.092

7. Wang, S.Y. and Han, W.P. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimensional Hypercubes under the MM* Model. Information Processing Letters, 116, 574-577.
https://doi.org/10.1016/j.ipl.2016.04.005

8. Yuan, J., Liu, A.X., Ma, X., Liu, X.L., Qin, X. and Zhang, J.F. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177.
https://doi.org/10.1109/TPDS.2014.2318305

9. Yuan, J., Liu, A.X., Qin, X., Zhang, J.F. and Li, J. (2016) g-Good-Neighbor Conditional Diagnosability Measure of 3-Ary n-Cube Networks. Theoretical Computer Science, 626, 144-162.

10. Lin, L., Xu, L., Wang, D. and Zhou, S. (2016) The g-Good-Neighbor Conditional Diagnosability of Arrangement Graphs. IEEE Transactions on Dependable and Secure Computing, PP, 1-12.
https://doi.org/10.1109/TDSC.2016.2593446

11. 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.

12. Dahbura, A.T. and Masson, G.M. (1984) An o(n^2.5) Fault Identiﬁcation Algorithm for Diagnosable Systems. IEEE Transactions on Computers, C-33, 486-492.
https://doi.org/10.1109/TC.1984.1676472

13. 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

14. Cull, P. and Larson, S.M. (1995) The Mobius Cubes. IEEE Transactions on Computers, 44, 647-659.
https://doi.org/10.1109/12.381950

15. Fan, J.X. (1998) Diagnosability of Möbius Cubes. IEEE Transactions on Parallel and Distributed Systems, 9, 923-928.
https://doi.org/10.1109/71.722224

16. Li, X.J. and Xu, J.M. (2013) Edge-Fault Tolerance of Hypercube-Like Networks. Elsevier North-Holland, Inc.
https://doi.org/10.1016/j.ipl.2013.07.010

17. Ye, L. and Liang, J. (2016) On Conditional h-Vertex Connectivity of Some Networks. Chinese Journal of Electronics, 25, 556-560.
https://doi.org/10.1049/cje.2016.05.023

期刊菜单