图的容错性与可靠性

1. 基本概念引入
   图的容错性研究的是图结构在部分顶点或边失效后，剩余部分仍能保持特定性质的能力。可靠性则是量化这种稳健性的数学框架。设G=(V,E)是一个无向连通图，若删除任意k-1个顶点后图仍连通，则称G是k-顶点连通的。类似可定义k-边连通性。例如树是1-顶点连通的，因为删除任一顶点可能破坏连通性。

2. 容错参数体系

   • 连通度：顶点连通度κ(G)是最小的顶点子集，删除后使图不连通或只剩单顶点；边连通度λ(G)定义为使图不连通需删除的最小边数。根据Whitney定理，恒有κ(G)≤λ(G)≤δ(G)（最小度）。
   • 条件连通度：要求删除点集后剩余图满足特定条件（如最小度≥r）。当r=1时即为经典连通度，该推广能更精细刻画网络脆弱性。

3. 可靠性多项式模型
   假设边以概率p独立工作，则网络可靠性R(G,p)表示所有顶点连通的概率。对于n顶点m边的图，可展开为\(R(G,p)=\sum_{i=n-1}^{m} N_ip^i(1-p)^{m-i}\)，其中N_i是恰含i条边且连通支撑子图的数量。计算N_i是#P-难问题，需借助分解定理（如通过收缩删除边递归计算）。

4. 容错直径分析
   若G是k-连通图，定义f-容错直径D_f为删除任意f个顶点(f<k)后剩余图的直径最大值。例如Harary图通过循环构造实现最优容错直径。关键结论：对于k-连通图，有\(D_1 \leq D_0 + 2\)（Chung-Garey定理），该上界紧致。

5. 应用与扩展
   在数据中心网络中，常采用广义超立方体等结构，其边容错直径在删除O(log n)条边后仍保持O(log n)级别。现代研究还结合随机图理论，分析Erdős-Rényi图在随机边失效下的连通概率阈值现象。