最近学习了一些故障诊断，想着整理一下图论的一些概念和基础知识
Vertex (顶点): 就是图里的一个点，代表一个处理器。
Edge (边): 连接两个顶点的线，代表处理器之间的物理连接。
Cycle (环)： 在图论里，环就是一个封闭的圈，比如 A-B-C-A。在网络里，环非常重要，因为它提供了冗余路径。如果环上一个点坏了，数据还可以从另一个方向绕过去，网络不会立刻断开。
故障集 F
故障集 F 就是网络中所有坏掉的处理器（顶点）组成的集合。
用图论语言：F⊆V(G) ，即 F 是图 G 顶点集的一个子集
这些顶点被认为“失效”了，不能工作，也不能参与测试
不可区分
Indistinguishable (不可区分): 如果两种故障情况（比如故障集A和故障集B）产生的测试结果完全一样，我们就说它们是不可区分的。这意味着我们无法判断到底是A坏了还是B坏了，诊断失败。
普通超立方体 Qn
普通超立方体 Qn 是最经典的多处理器互连网络模型：
顶点：所有 n 位二进制串，比如 000,001,010,011 是 Q3 的 8 个顶点。总数是 2n 。
边：两个顶点相邻，当且仅当它们的二进制串恰好有一位不同。也就是 Hamming 距离为 1。
度数：每个顶点有 n 个邻居，所以是 n -正则图；边数是 n2n−1 。
递归结构：Qn 可看成两个 Qn−1 再加上对应顶点之间的一完美匹配，即
Qn≅Qn−1□K2.
小例子：Q2 是正方形，Q3 就是几何立方体的图；Q4 以后不好画，但定义完全一样。
几个常用性质：直径是 n ；按二进制串中 1 的个数的奇偶性可把顶点分成两半，所以 Qn 是二分图；顶点连通度是 κ(Qn)=n 。
折叠超立方体 FQₙ
折叠超立方体 FQₙ 就是多加了一种边：两个节点如果所有位都相反（比如 0011 和 1100），也连一条”补边”。这样每个节点的邻居从 n 个变成 n+1 个，网络更”结实”，直径也更小。
增广立方体 AQn
增广立方体 AQn 可以看成在普通超立方体 Qn 上“加边增强”得到的网络。
顶点仍和 Qn 一样：所有 n 位二进制串，共 2n 个。边分两类：
cube edges（立方体边）：和普通超立方体一样，两个串恰好一位不同就相邻。每个点有 n 条。
complement edges（取反边/补边）：把一个顶点的末尾连续 k 位整体取反，其中 k=2,3,…,n 。这样每个点再多 n−1 条边。
所以 AQn 是 (2n−1) -正则图：每个点有 n 条普通超立方体边，加 n−1 条补边。
例子 AQ3 ，顶点 000 的邻居是：
cube edges：001,010,100 ；
complement edges：011 （末两位取反），111 （末三位全取反）。
共 5 个邻居，度数 2⋅3−1=5 。
它也可以递归理解：把最高位为 0 的顶点看成 AQn0 ，最高位为 1 的看成 AQn1 ，两半各自都同构于 AQn−1 ；但两半之间不是只加一条完美匹配，而是每个顶点在另一半中有两个对应邻居：一个“同后缀”的 cube 边，一个“后缀全取反”的 complement 边。因此 AQn 不是 hypercube-like network，不能简单套用超立方体类网络的那套 g-extra 结论。
和上面的超立方体 AQn 对比：Qn 每个点只连“翻一位”的邻居；而 AQn 还额外加入“按某段取反”的 complement edges，所以每个点度数从 n 变成 2n−1 ，连通性和容错能力更强，但结构也更复杂。
k 元 n 立方 k-ary n-cube
k-ary n-cube（中文常译作 k 元 n 立方，也称 n 维 k 元环面）是并行计算、片上网络和互连网络中常见的一类规则图拓扑。它可以看作超立方体的一种推广。
它是 n 个长度为 k 的环$C_{k}$的笛卡尔积：
$$
C_{k} \square C_{k} \square \cdots \square C_{k}
$$
共有 n 个因子。
顶点可以表示为 n 元组：
$$
(x_{1},x_{2},\ldots,x_{n}),x_{i} \in { 0,1,\ldots,k - 1}
$$
因此顶点总数为：
$$
N = k^{n}
$$
两个顶点相邻，当且仅当它们恰好有一个坐标相差 $\pm 1(modk)$，其余坐标相同。也就是说，每个节点在每一维上与前后两个邻居相连，形成环绕连接，所以整体是一个 n 维环面。
特例
- 当
k = 2时，k-ary n-cube 退化为常见的 n 维超立方体，即 binary n-cube / hypercube - 当
n = 1时，它是一个长度为 k的环 $C_{k}$。 - 当
n = 2时，它是一个 $k \times k$的二维环面。 - 如果去掉每一维的环绕连接，则得到的是 k-ary n-mesh，而不是 k-ary n-cube。
基本性质
顶点数：$k^{n}$
每个节点的度数：
若 $k& gt;2$，度数为 $2n$；
若 $k = 2$，度数为 $n$。
直径：
$D = n\left\lfloor \frac{k}{2} \right\rfloor$
它是顶点传递的，也是边传递的，并且是 Cayley 图。
当且仅当 $k$ 为偶数时，它是二部图。
它是高度对称、规则、可扩展的互连拓扑。
交叉立方体 Crossed Cubes
Crossed Cubes（交叉立方体，通常记作 $CQ_{n}$ 是一种多处理器互连网络拓扑。 它可以看作普通超立方体（Hypercube）的一种改进：通过调整节点之间的连接方式，让网络在保持较好的通信性能的同时，具有一些更有利的结构性质。
| 性质 | 结果 | 通俗解释 |
|---|---|---|
| 节点数 | $2^n$ | 每个节点对应一个 n 位二进制串 |
| 节点度 | n | 每个节点恰好连接 n 个邻居 |
| 连通度 | n | 至少删除 n 个节点，才可能使网络断开 |
| 三角形 | 不含三角形 | 网络中不存在由 3 个节点组成的环 |
| 对比项 | 普通超立方体 $Q_{n}$ | 交叉立方体 $CQ_{n}$ |
|---|---|---|
| 节点连接规则 | 两个二进制串恰好有一位不同 | 使用交叉立方体特有的配对规则 |
扭曲超立方体 Twisted Hypercubes
Twisted Hypercube（扭曲超立方体）是一类对普通超立方体进行连接方式改造的多处理器互连网络。 它的核心思想是：保留超立方体的基本框架，但改变某些维度上的节点连接规则，从而获得不同的网络结构和通信性质。
交换超立方体 Exchanged Hypercubes
在多处理器网络研究中，常见的交换超立方体记作 $EH(s,t)$
其中 (s,t) 是两个正整数，分别控制网络中两组不同的超立方体结构。经典定义将它看作普通二进制超立方体的一种删边变体：保留所有节点，但有选择地删除部分连接，以降低互连复杂度。
每个节点可以写成一个长度为 s+t+1 的二进制串：
$$
u=a_{s} \cdot \cdot \cdot a_{1}b_{t} \cdot \cdot \cdot b_{1}c
$$
这里：
- $a_{s},…,a_{1}$：一组 $s$ 位二进制信息；
- $b_{t},…,b_{1}$：另一组 $t$ 位二进制信息；
- $c$：最后一位，用来决定该节点采用哪一组维度的连接规则。
connectivity（连通度）
在图论/互连网络里，connectivity（连通度）衡量的是：一个网络“最少坏掉多少个点/边”就会变得不连通。
通常说 connectivity 多指 vertex connectivity，记作 κ(G) ：
κ(G) = 删除最少的顶点数，使图 G 变得不连通。
对应到多处理器网络：顶点=处理器，边=通信链路；κ(G) 就是最少要坏多少个处理器，网络才会被拆成至少两块。边的版本叫 edge connectivity，记作 λ(G) ，类似地定义为删除最少边使图断开。
常见例子：
完全图 Kn ：κ(Kn) = n−1 ，要删掉 n−1 个点才剩一个点；
环 Cn ：κ(Cn) = 2 ，删两个点能断开；
树 T ：κ(T) = 1 ，删掉一个割点就断；
超立方体 Qn ：κ(Qn) = n ；
增广立方体 AQn ：κ(AQn) = 2n−1 。
一般有
κ(G)≤λ(G)≤δ(G),
其中 δ(G) 是最小度数。
但普通 connectivity 有个缺点：它常被“一个很小的碎块 + 一个仍然很大的核心”主导。比如网络断成“1 个孤立点”和“其余 99% 还连着”，按普通 connectivity 也算失效，可实际上核心仍可能工作。所以才会有更细的推广：
r-component connectivity：要求断开后至少剩 r 个分量；
h-extra / g-extra connectivity：要求每个剩余分量至少 h+1 或 g+1 个顶点；
Diagnosability (可诊断性)
Diagnosability (可诊断性)： 这是最基础的指标。它回答的问题是：“在保证能找出所有故障点的前提下，系统最多能容忍多少个坏点？” 比如，一个网络的可诊断性是10，意味着只要有10个或更少的处理器坏了，我们都能把它们全找出来。如果有11个，就可能找不准了。
Cyclic Diagnosability (循环可诊断性) ct(G)
Cyclic Diagnosability (循环可诊断性) ct(G)：它回答的问题是：“在保证能找出所有故障点的前提下，系统最多能容忍多少个坏点，同时要求这些故障点把网络切开后，剩下的部分里至少有两个包含环的连通分支？”
Cyclic Connectivity (循环连通度) κc(G)
Cyclic Connectivity (循环连通度) κc(G): 要让网络断开，并且剩下的部分里至少有两个包含环的连通分支，最少需要拔掉多少个点。这是 ct(G) 的一个“亲戚”，是图论里的一个概念。
两者的联系
虽然定义不同，但这两个概念是“亲戚”：
Cyclic Connectivity 是 Cyclic Diagnosability 的“地基”
要知道“能诊断多少故障”，先得知道“网络在循环条件下有多容易被切断”
论文引用了前人结果 κc(Qn)=4n−8 ，作为证明 ct(Qn)=5n−10 的出发点
诊断性 ≥ 连通性
直观理解：如果敌人需要 4n−8 个节点才能破坏网络，那系统至少能“识别”这么多故障（因为故障数少于这个数时，网络根本没断，诊断 trivial）
但实际上能诊断的更多（5n−10 ），因为即使网络断了，只要还能区分故障集，诊断就成功
总结一句话：
κc(G) 问的是“最少多少点能搞坏我”
ct(G) 问的是“最多多少点坏了我还能修好”
t-diagnosable (t-可诊断的)
如果一个网络在任何不超过 t 个故障点的情况下都能被成功诊断（即所有可能的故障集都是可区分的），那它就是 t-可诊断的。
必记lemma
邻域计算
如果集合 S 里包含一个4-圈（正方形），那么当 S 有5个或6个点时，它的外部邻居数量至少有某个保证值。
具体：
∣S∣=5 （4-圈 + 1个额外点）⇒∣N(S)∣≥5n−12
∣S∣=6 （4-圈 + 2个额外点）⇒∣N(S)∣≥6n−17
可区分性判据
PMC：存在健康点 u∈F1∪F2 直接连差异点 v∈F1△F2
MM*：存在健康点 w 能同时”看到”两个差异点（三种情况）
超立方体性质
任意两点最多 2 个公共邻居（cn ≤2 ）
删除 ≤5n−10 个点后，只剩一个大分支 + 总点数 ≤5 的小碎片
在超立方体 $Q_{m}$ 中，一个顶点如果和 4-环中的一个顶点相邻，它必定和 4-环中的两个顶点相邻（这是一个超立方体的几何性质）。
折叠超立方体性质
在 $n$ 维折叠超立方体 $FQ_{n}$ 中，取一个 4-环 $S$。如果有一个顶点 $u$ 离这个 4-环“很远”——既不在 $S$ 里，也不和 $S$ 中任何顶点直接相邻——那么 $u$ 的邻居和 $S$ 的邻居，最多只能有 2 个 是重合的。
G 有完美匹配，当且仅当对于任意顶点子集 $X$，$o(G - X) \leq \mid X \mid$。$o(G - X)$表示：在删除顶点集 $X$ 后，剩下的图 $G - X$ 中，包含奇数个顶点的连通分量（连通块）的个数。
