Definitions：核心定义与证明 (C 部分)

Definition 1：p-QDG

p-QDG 是这篇论文的基础模型。

给定：

1
r1 > r2 > ... > rp > 0

表示 p 种通信模式的通信半径。

两个节点之间距离越近，可用通信模式越多，边也越多。

例如 $p=3$ 时：

1
2
3
4
5
6
7
8
9
10
11
dist(x,y) > r1：
无边

r2 < dist(x,y) ≤ r1：
1 条边

r3 < dist(x,y) ≤ r2：
2 条边

0 < dist(x,y) ≤ r3：
3 条边

所以 p-QDG 是多重图。

Definition 2：Independent nodes

如果两个节点距离大于最大通信半径：

1
dist(u,v) > r1

则它们相互独立。

也就是：

1
两个节点之间没有任何通信模式对应的边

Lemma 1：独立邻居数量上界

Lemma 1 说明：

对任意节点 $u$，与 $u$ 相邻且彼此独立的节点数量不超过 5。

这是一个几何上界，后面会用于近似比证明。

你可以把它理解为：

在一个半径为 $r_1$ 的圆内，彼此距离都大于 $r_1$ 的点最多只能有 5 个。

这也是性能比中常数 5 的来源之一。

Definition 3：Edge cut set

边割集是：

删除后会使图不连通的一组边。

其中又区分：

1
2
3
k-edge cut set：大小为 k 的边割集
minimal edge cut set：极小边割集，不能再删小
minimum edge cut set：最小边割集，所有边割中边数最少

这里要注意：

1
2
minimal 是极小，按包含关系；
minimum 是最小，按数量大小。

Definition 4：Minimum weight edge cut set

这是加权图中的最小权重边割。

它比较的不是边数，而是：

1
边权重总和

这个定义后面会和关联边加权图配合使用。

Definition 5：Brother edge / Edge family

因为 p-QDG 是多重图，两个节点之间可能有多条边。

这些同一对节点之间的平行边互称：

1
brother edges

它们组成的集合叫：

1
edge family，记为 EF(x,y)

如果 $x,y$ 之间有 3 条边：

1
EF(x,y) = {(x,y)1, (x,y)2, (x,y)3}

如果没有边：

1
EF(x,y) = ∅

这个定义是为了精确表示多通信模式下两个节点之间的多条链路。

Definition 6：Associated Edge-Weighted Graph

这个定义非常重要。

它把多重图 $G$ 转换成一个边加权图 $H$。

转换规则是：

1
2
3
4
节点集合不变；
如果 G 中 x,y 之间至少有一条边，
则 H 中 x,y 之间有一条边；
H 中这条边的权重等于 |EF(x,y)|。

也就是说：

1
多重边数量 → 加权图中的边权

例如：

1
2
G 中 a 和 b 有 3 条边
H 中 a 和 b 有 1 条边，权重为 3

这个转换方便后面处理最小割问题。

Lemma 2：多重图最小割与加权图最小权重割等价

Lemma 2 说明：

在多重图 $G$ 中求最小边割，等价于在其关联边加权图 $H$ 中求最小权重边割。

证明的关键是：

1
2
多重图中的最小边割一定由若干完整的 edge family 组成，
不会只删除某个 edge family 的一部分。

因为如果只删除部分兄弟边，两个端点之间仍有剩余边相连，那么这部分删除对割开图没有必要，会违反极小边割集的性质。

这个 Lemma 很重要，因为它为后续判断边连通性提供了工具。

Definition 7：k-edge-connected

一个图是 $k$-edge-connected，表示：

删除任意 $k-1$ 条边后，图仍然连通。

例如：

1
2
3
1-edge-connected：普通连通
2-edge-connected：删除任意 1 条边后仍连通
3-edge-connected：删除任意 2 条边后仍连通

在本文中，它用于保证：

1
骨干内部的链路故障容忍能力

Definition 8：m-edge-dominating set

给定集合 $S$，如果对任意非骨干节点 $u \notin S$，都有：

1
|E(u,S)| ≥ m

那么 $S$ 是一个 m-edge-dominating set。

它表示：

每个非骨干节点至少有 m 条边连接到骨干。

这保证了普通节点接入骨干的边冗余。

Definition 9：(k,m)-ECDS

这是全文核心定义。

集合 $S$ 是 $(k,m)$-ECDS，当且仅当：

1
2
1. S 是 m-edge-dominating set；
2. G[S] 是 k-edge-connected graph。

它表示：

具有边故障容忍能力的虚拟骨干。

其中：

1
2
m-edge-dominating 保证普通节点接入骨干可靠；
k-edge-connected 保证骨干内部链路可靠。

也就是：

1
外部接入有冗余，内部连通也有冗余。

Definition 10：ANS_r

给定节点 $r$，只要非空集合 $S$ 不包含 $r$，则 $S$ 是 $r$ 的 associated node set，记为：

1
ANS_r

因为 $E(S)$ 是 $S$ 与外部之间的边，删除 $E(S)$ 后，$S$ 会与包含 $r$ 的外部部分断开，所以：

1
G - E(S) 不连通

Definition 11：k-ANS_r

如果 $S$ 是 $ANS_r$，并且：

1
|E(S)| = k

那么 $S$ 是：

1
k-ANS_r

它本质上表示：

一个不包含 $r$，且只通过 k 条边与外部连接的节点集合。

也就是一个大小为 k 的割对应的节点集合。

Theorem 1

Theorem 1 说明：

在一个已经是 $(k-1)$-edge-connected 的多重图中，图是 $k$-edge-connected，当且仅当不存在 $(k-1)$-ANS$_r$。

直观理解：

1
2
3
4
(k−1)-ANS_r 表示一个薄弱区域；
它只靠 k−1 条边连接到 r 所在部分；
如果存在这样的区域，删除这 k−1 条边图就会断开；
如果不存在，则图达到 k-edge-connected。

这一定理后面可能用于算法中判断是否还需要增强边连通性。

Definition 12：L_n(S) path

$L_n(S)$ 路径表示：

1
2
路径两端点在 S 外，
中间 n 个内部节点都在 S 中。

例如：

1
u - a - v

如果 $a \in S$，$u,v \notin S$，则是 $L_1(S)$ path。

这个定义后面可能用于描述通过已有集合 $S$ 连接外部节点的路径。

Definition 13：Weight Function

这个定义本质上是：

1
字典序比较

比较两个 $k$ 元组时：

1
2
3
4
先比较第 1 个分量；
相同再比较第 2 个；
再相同继续比较第 3 个；
依次类推。

后面算法可能会用它来选择优先级最高的候选节点或候选路径。

Definition 14：Laminar Family

Laminar family 是一组集合，任意两个集合之间只能满足：

1
2
一个包含另一个；
或者完全不相交。

不能出现部分重叠。

Lemma 3 说明：

1
2
如果 F 是 S 的 laminar family，
那么 |F| ≤ 2|S| − 1。

这个结论后面可能用于限制某类 ANS 集合的数量，从而服务于近似比分析。