主要证明

Lemma 2 的前半部分。证明了两个关键点：

算法终止时，黑色 + 灰色节点构成了 root 所在的 active 连通区域 $H$；
黑色节点集合 $A_S$ 支配这个区域 $H$；
证明 黑色节点集合 $A_S$ 自身是连通的。

最终目的是得到：$ A_S \text{ 是 } H \text{ 的 CDS} $
也就是：

$A_S$ 支配 $H$；
$G[A_S]$ 连通。

注意这里输出的 $S$，但真正起作用的是 $S$ 中的 active/black 节点，也就是 $A_S$。理解时可以把输出骨干看成黑色节点集合。 √

1. $H_\varphi$

这里定义：
$$
H_\varphi
$$
表示
$$
G[A_\varphi]
$$
中包含 root $r$ 的连通分量。

因为在随机场景下，所有 active 节点构成的子图：
$$
G[A_\varphi]
$$
不一定连通。

比如有些 active 节点可能分布在另一个孤立区域中，和 root 所在区域没有 active 路径连接。

所以算法目标不是控制所有 active 节点，而是控制：

包含根节点 $r$ 的 active 连通分量。

也就是 $H_\varphi$。

2. $N_G(H_\varphi)$ 中的节点一定 inactive

原文观察式 (3)：
$$
\text{all nodes in } N_G(H_\varphi) \text{ are inactive under } \varphi.
$$

$H_\varphi$ 是 root 所在的 active 连通分量。

如果 $H_\varphi$ 外面有一个邻居节点 $x$，也就是：
$$
x\in N_G(H_\varphi)
$$
并且 $x$ 是 active，那么 $x$ 就可以通过一条边连接到 $H_\varphi$。

这样 $x$ 就应该属于同一个 active 连通分量 $H_\varphi$。

但 $x$ 在 $N_G(H_\varphi)$ 中，说明它不在 $H_\varphi$ 内，只是在外部邻居。

因此矛盾。

所以这些外部邻居只能是 inactive。

简单说：

一个 active 连通分量的边界外邻居，如果还是 active，那它就应该被并入这个连通分量；所以边界外邻居一定 inactive。

这个结论很重要，因为算法不需要揭示全图，只需要找到一个 active 区域，并确认它的外边界都是 inactive，就知道这个区域已经完整了。

3. 为什么不需要揭示所有节点状态？

论文说：

to identify a stochastic CDS, it is not mandatory to disclose the states of all nodes.

假如网络中有 100 个节点，root 所在 active 连通分量只有 20 个节点。算法只需要找到并支配这 20 个 active 节点即可，不需要知道另一边完全不连通区域里的节点状态。

只要已经确认：
$$
N_G(H)
$$
里所有节点 inactive，那么 $H$ 就是一个完整的 active 连通分量。

因此，算法可以提前停止，而不是探测整个图。

4. $H$ 是什么？

在证明中，$H$ 表示：

由黑色节点和灰色节点，也就是已知 active 节点构成的诱导图。

黑色节点：被主动 probe 且 active。
灰色节点：没有被主动 probe，但被 active 节点揭示为 active。

所以 $H$ 是当前已经知道的 active 区域。

5. 性质 (4) 在证明什么？

性质 (4)：
$$
\text{all nodes in } N_G(H) \text{ are confirmed to be inactive.}
$$
即算法终止时，当前已知 active 区域 $H$ 的外部邻居都已经被确认 inactive。

这个性质一旦成立，就说明：
$$
H
$$
已经是一个完整的 active 连通分量，不会再有 active 节点贴在它外面。

6. 性质 (4) 的证明逻辑

假设存在一个节点：
$$
v\in N_G(H)
$$
并且 $v$ 的状态还没有被揭示，也就是白色。

因为 $v$ 是 $H$ 的邻居，所以它和 $H$ 中某个节点相邻。

而 $H$ 由黑色和灰色节点构成。

但是前面 Algorithm 1 有性质：

白色节点不能有黑色邻居。

所以 $v$ 不可能连着黑色节点，只能连着某个灰色节点 $u$。

于是对于这个灰色节点 $u$ （计算其收益）：

第一，因为它邻接白色节点 $v$，所以：
$$
NWS(u)\geq 1
$$
第二，因为灰色节点一定是通过某个黑色节点揭示出来的，所以灰色节点一定邻接黑色节点。因此：
$$
NCS(u)\geq 1
$$
于是：
$$
NWS(u)+NCS(u)>1
$$
也就是说，节点 $u$ 仍然满足算法继续迭代的条件。

所以算法不应该终止。

这和“算法已经终止”矛盾。

因此，不可能存在这样的白色边界节点。边界节点都必须已经被揭示。

而如果边界节点已揭示且 active，那它就应该属于 $H$，不会在 $N_G(H)$ 外部。所以边界节点只能是 inactive。

于是性质 (4) 成立。

7. 为什么 $A_S$ 是 $H$ 的支配集？

原文说：

Since every gray node is adjacent to a black node, $A_S$ is a dominating set of $H$.

这里：
$$
A_S
$$
是黑色节点集合，也就是被 probe 且 active 的节点集合。

$H$ 是黑色 + 灰色节点构成的图。

对于 $H$ 中的每个节点：

如果它是黑色节点，那么它自己就在 $A_S$ 中；
如果它是灰色节点，那么它一定邻接某个黑色节点。

所以所有 $H$ 中的节点都被 $A_S$ 支配。

因此：
$$
A_S \text{ dominates } H
$$
即 $A_S$ 是 $H$ 的 DS。

8. $S$、$A_S$、黑色节点到底是什么关系？

论文里：
$$
S
$$
是被 probe 的节点集合。
$$
A_S
$$
是 $S$ 里面 active 的节点，也就是黑色节点集合。

所以：
$$
A_S = {v\in S : v \text{ is active}}
$$
如果所有被探测节点都 active，那么：
$$
A_S=S
$$
但如果某个被探测节点 inactive，那么它在探测记录 $S$ 里，但不在 $A_S$ 里，而且会被移除。

在理解 CDS 输出时，真正作为骨干的是：
$$
A_S
$$
也就是黑色节点集合。

论文最后说输出 $S$，但严格理解应是输出其中 active 的被探测节点，即黑色节点集合。

笔记

理论分析首先定义 H_ϕ 为 G[A_ϕ] 中包含根节点 r 的 active 连通分量。
由于 H_ϕ 是一个极大的 active 连通分量，因此其在原图 G 中的外部邻居 N_G(H_ϕ) 必然都是 inactive，否则这些 active 邻居也会被并入 H_ϕ。

Lemma 2 证明 Algorithm 1 输出的是一个可行的 stochastic CDS。
证明思路是：算法并不需要揭示全图所有节点状态，只需要识别出 root 所在 active 连通分量。令 H 为算法终止时由黑色和灰色节点组成的已知 active 子图。
首先证明算法终止时 N_G(H) 中所有节点都已经被确认为 inactive。
若存在未揭示的边界白色节点 v，则 v 不能邻接黑色节点，只能邻接某个灰色节点 u；

由于 u 邻接白色节点且灰色节点又邻接黑色节点，有 NWS(u)≥1 且 NCS(u)≥1，因此算法不应终止，矛盾。

因此 H 是 G[A_ϕ] 中的一个 active 连通分量。由于每个灰色节点都邻接某个黑色节点，黑色节点集合 A_S 支配 H。接下来只需证明 G[A_S] 连通，即可说明 A_S 是 H 的 CDS。

总结

算法终止时，黑色 + 灰色节点构成的 active 区域 $H$ 的边界外邻居都已经确认 inactive，因此 $H$ 是 root 所在的完整 active 连通分量；而黑色节点支配所有灰色节点，所以只要证明黑色节点连通，就能说明输出是 CDS。

对后面做容错版来说，有启发：
原论文证明的是：
$$
G[A_S]\text{ connected}
$$
未来如果做容错，证明目标可能要换成：
$$
G[A_S]\text{ 2-connected}
$$
这就比这里难一层，因为不仅要证明黑色节点连通，还要证明没有割点，或者删除任意一个黑色节点后仍连通。

补充：节点状态

状态	含义	是否 active 已知？	是否被主动探测？	是否属于骨干候选
白色 white	状态未知	不知道	没有	暂时不是
黑色 black	被 probe 且 active	已知 active	是	是
灰色 gray	被黑色节点揭示为 active	已知 active	否	还不是，但可能以后变黑
removed	已知 inactive	已知 inactive	可能是，也可能不是	不可能

算法逻辑

可以这样理解：

从已知 active 的根节点 $r$ 开始，把被主动探测且 active 的节点染成黑色，把被黑色节点顺带揭示出的 active 节点染成灰色，把 inactive 节点移除。然后算法不断在当前黑色节点的 2-hop 范围内，选择最值得探测的白色或灰色节点。如果探测到 active，就让它变黑并揭示邻居；如果探测到 inactive，就移除。重复这个过程，直到当前 root 所在 active 连通分量已经被黑色节点支配，并且黑色节点自身连通。

S 用来记录已经被主动探测过的节点。探测到 active 的节点会变成黑色，并加入有效骨干集合 $A_S$；如果探测到 inactive，则该节点被移除，不参与后续构造。灰色节点是由已经探测且 active 的黑色节点通过 full feedback 揭示出来的 active节点，它们 状态已知但还没有被主动探测，因此暂时不属于黑色骨干。若黑色节点揭示出的邻居是 inactive，则该邻居直接被移除。白色节点表示状态尚未被揭示，仍然未知。