图的容错参数 1 基本定义 图的容错参数（fault-tolerance parameters）是衡量图在网络或系统结构中对顶点或边失效的抵抗能力的量化指标。设图 \( G=(V,E) \)，容错参数通常研究当图中部分顶点（或边）因故障被移除后，剩余图仍能保持特定性质（如连通性、直径等）的最大容忍故障数量。例如， 连通度 （connectivity）是最基础的容错参数，表示使图不连通所需移除的最少顶点数。 2 典型容错参数分类 容错参数可分为两类： 顶点容错 ：关注顶点失效对图结构的影响，如顶点连通度 \( \kappa(G) \)、 坚韧度 （toughness）等。 边容错 ：关注边失效的影响，如边连通度 \( \lambda(G) \)、 边坚韧度 （edge toughness）等。 例如，若 \( \kappa(G) \geq k \)，则任意移除少于 \( k \) 个顶点后图仍连通。 3 高阶容错参数：超连通性 超连通性（super-connectivity）要求移除任意最小顶点割后，剩余图不仅连通且不含孤立顶点。若图 \( G \) 的每个最小顶点割均孤立一个顶点，则称 \( G \) 是超连通的。类似地， 超边连通性 （super-edge-connectivity）要求最小边割只孤立一条边。这类参数适用于对故障更敏感的网络设计。 4 容错直径与距离参数 容错直径（fault-tolerant diameter）定义为：在移除最多 \( k \) 个顶点（或边）后，剩余图的直径最大值。例如，若容错直径为 \( d \)，则即使出现 \( k \) 个故障，任意两顶点间仍存在长度不超过 \( d \) 的路径。相关概念包括 条件直径 （conditional diameter），限制故障后剩余图需满足特定条件（如最小度约束）。 5 容错参数的计算复杂性 多数容错参数的计算是NP困难的。例如，确定图的坚韧度 \( t(G) \) 是NP难问题，因为需找到顶点子集 \( S \) 使得 \( |S| \) 与剩余分支数之比最小。近似算法和参数化算法（如基于树宽）常被用于求解实际场景中的容错参数。 6 应用与扩展 容错参数在分布式系统、通信网络设计中至关重要。例如，在数据中心网络拓扑中，高顶点连通度确保服务器故障时路由冗余。近年研究扩展到 动态图容错 ，即边或顶点故障随时间动态发生，需结合时序分析评估长期可靠性。