图论/k-连通图

连通性的定义

设 u 和 v 是图 $G$ 的顶点。

• 如果在 $G$ 中存在一条 $u-v$ 路径，则称 $u$ 和 $v$ 是连通的。
  
• 如果对于 $G$ 中的每一对顶点 $u$ 和 $v$ 都存在一条 $u-v$ 路径，则称 $G$ 是连通的，或称连通图。

边连通度

从图 $G$ 中删除使其断开的边数的最小值 lambda($G$)，也称为线连通度。断开图的边连通度为 0，而具有图桥的连通图的边连通度为 1。

顶点连通度

从图 $G$ 中删除使其断开的顶点数的最小值 kappa($G$)。

设 lambda($G$) 是图 $G$ 的边连通度，delta($G$) 是其最小度，那么对于任何图，
kappa($G$) ≤ lambda($G$) ≤ delta($G$)

k-连通图

• k-边连通图
  

如果一个图的最小割集包含k条边，并且删除这些边会导致图断开连接，那么该图的边连通度为k。

• k-顶点连通图
  

如果一个图的最小割集包含k个顶点，并且删除这些顶点会导致图断开连接，那么该图的顶点连通度为k。
1-连通图被称为连通图；2-连通图被称为双连通图；3-连通图被称为三连通图。

门格尔定理

• 边连通度

对于$u$和$v$，最小边割集的大小（即删除最少数量的边会导致$u$和$v$断开连接）等于从$u$到$v$的成对边不相交路径的最大数量。

• 顶点连通度

对于$u$和$v$，最小顶点割集的大小（即删除最少数量的顶点会导致$u$和$v$断开连接）等于从$u$到$v$的成对顶点不相交路径的最大数量。
（边割集是指删除这些边会导致图断开的边集；顶点割集或分离集是指删除这些顶点会导致图断开的顶点集。）

最大流 (maximum flow) 最小割 (minimum cut) 定理

图$G$中顶点$u$和$v$之间的最大流量，恰好等于断开$G$连接并使$u$和$v$位于不同连通分量的最小边集的权重。

• 最大流：图$G$中顶点$u$和$v$之间的最大流量
• 最小割集：断开 $G$ 中 $u$ 和 $v$ 所在的不同连通分量的最小边集。