图的割稀疏化

稀疏化并不是平均删边：细割中的少数关键边一旦漏采，割值会完全失真；处在许多替代路径中的边则可用较低概率保留。按重要性采样并用 $1/p_e$ 重权，既保持固定割无偏，又把有限边数集中到所有割同时可控的范围。

稠密网络例子 ​

全网遥测图可能有近二次边。cut sparsifier 把边压到近线性规模后，任意数据中心分区的跨区容量仍在 $1\pm \epsilon$ 内，可加速多次 cut/flow 计算；被采边的权重必须放大以补偿低采样率。

相邻概念边界 ​

保留所有割不等于保留所有点对最短路；后者更接近 spanner。Spectral sparsifier 要求所有向量的 Laplacian 二次型近似，通常推出 cut 近似但定义更强。动态 sparsification 是算法框架，不是静态随机抽边的自动性质。负边权会破坏割容量和采样浓缩的标准形式。

Uniform 保证的证明责任 ​

固定割可直接对独立采样边用 Chernoff，但对 $2^{n-1}$ 个割粗暴并集常过大。Benczúr–Karger 分析按割值分层，并利用近最小割数量受控的 cut-counting lemma；高容量割虽更多，却有更强浓缩。这个组合才把“每割高概率”升级成“所有割同时高概率”。

采样概率若用 edge strength 近似值，需证明估计不会把关键边概率低估过多。重权 $w_e/p_e$ 可能增大单边权，尾界参数也必须随之调整。

抽样式稀疏化把边保留概率与逆强度、leverage $w_e{R}_e$ 或割贡献配对，属于随机化算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。；正确性需要对单个割的集中界再扩展到所有相关割，而不是只验证期望边数。

采样权重与共同事件 ​

若边 $e$ 以概率 $p_e$ 保留，进入 $H$ 后应赋权 $w_e/p_e$。因此对任意固定割，每条边贡献的期望仍为 $w_e$；只保留边却不重标权，会系统性缩小所有割。低强度、可能控制细割的边取较大 $p_e$；高强度冗余边才可低概率采样。

困难不在单个固定割的无偏性，而在同一份 $H$ 要同时逼近指数多个割。证明需要割计数、边强度分层和集中不等式把失败事件合并，不能对 $2^n$ 个割直接套朴素 union bound。最终 $O(n\log n/{\epsilon }^2)$ 级边数依赖具体采样定理与常数，页面使用时应引用对应版本。

实现上先近似边强度，再独立采样并累加平行边权；零权边可删除，负权边则不在 cut sparsifier 的标准非负模型内。若后续算法关心拉普拉斯二次型而不只是割值，应使用 spectral sparsifier 的更强保证。