Skip to content

L004 连通度

块

图 \(G\) 的极大无割点的连通子图称作 \(G\) 的「块」（block）。

Th.4.1 块为边集定义了一种等价关系。

Th.4.2 对于阶至少为 \(3\) 的图 \(G=\left\langle V,E\right\rangle\)，块的几个等价定义：

  • \(G\) 没有割点。
  • \(\forall u,v\in V\)，\(G\) 含两条无公共内顶点的 \(u\)-\(v\) 路。
  • \(\forall u,v\in V\)，\(G\) 含圈经过 \(u\) 和 \(v\).
  • \(\forall v\in V,e\in E\)，\(G\) 含圈经过 \(v\) 和 \(e\).
  • \(\forall e,f\in E\)，\(G\) 含圈经过 \(e\) 和 \(f\).
  • \(\forall u,v\in V,e\in E\)，\(G\) 含 \(u\)-\(v\) 路经过 \(e\).
  • \(\forall u,v,w\in V\)，\(G\) 含 \(u\)-\(v\) 路经过 \(w\).
  • \(\forall u,v,w\in V\)，\(G\) 含 \(u\)-\(v\) 路不经过 \(w\).

对于图 \(G\)，将图的所有割点的集合记为 \(C\)，构造二分图 \(H=\left\langle B\cup C,E'\right\rangle\)，其中 \(B\) 中每个顶点表示 \(G\) 的一个块，边 \((b,v)\in E'\) 当且仅当 \(b\in B\) 表示的块含顶点 \(c\in C\)，\(H\) 称作 \(G\) 的「块-割点图」（block-cut graph）。

Th.4.3 对于图 \(G=\left\langle V,E\right\rangle\) 和顶点 \(v\in V\)，\(v\) 是 \(G\) 的割点当且仅当 \(G\) 的至少两个块含 \(v\).

【Algo.4.1】

Th.4.4 Th.4.5

割集和连通度

对于图 \(G=\left\langle V,E\right\rangle\) 和顶点子集 \(S\subseteq V\)，若图 \(G-S\) 的连通分支数量大于 \(G\) 的连通分支数量，则 \(S\) 称作 \(G\) 的「点割集」（vertex cut），又称「分离集」（separating set），因此割点对应单元素点割集。

若 \(G\) 的任何点割集都不是点割集 \(S\) 的真子集，那么 \(S\) 为 \(G\) 的「极小点割集」（minimal vertex cut）。顶点数量最少的点割集称为 \(G\) 的「最小点割集」（minimum vertex cut）。

使得 \(G\) 不连通或成为平凡图而至少从 \(G\) 中删除的顶点数量称作 \(G\) 的「点连通度」（vertex connectivity），简称「连通度」（connectivity），记作 \(\kappa(G)\). 若正整数 \(k\le \kappa(G)\)，则称 \(G\) 为「\(k\) 点连通图」（\(k\)-vertex-connected graph），简称「\(k\) 连通图」（\(k\)-connected graph）。

对于图 \(G=\left\langle V,E\right\rangle\) 和边子集 \(S'\subseteq E\)，若图 \(G-S'\) 的连通分支数量大于 \(G\) 的连通分支数量，则 \(S'\) 称作 \(G\) 的「边割集」（edge cut），因此割边对应单元素边割集。

若 \(G\) 的任何边割集都不是边割集 \(S'\) 的真子集，那么 \(S'\) 为 \(G\) 的「极小边割集」（minimal edge cut）。边数量最少的边割集称为 \(G\) 的「最小边割集」（minimum edge cut）。

使得 \(G\) 不连通或成为平凡图而至少从 \(G\) 中删除的边数量称作 \(G\) 的「边连通度」（edge connectivity），记作 \(\kappa'(G)\). 若正整数 \(k\le \kappa'(G)\)，则称 \(G\) 为「\(k\) 边连通图」（\(k\)-edge-connected graph）。平凡图的边连通度为 \(0\).

Th.4.6 对于任一图 \(G\)：\(\kappa(G)\le \kappa'(G)\le \delta(G)\).

Th.4.7 （Menger 定理）：对于图 \(G=\left\langle V,E\right\rangle\) 和两个不相邻顶点 \(u,v\in V\)，使 \(u\) 和 \(v\) 不连通需要从 \(G\) 中删除的顶点数量等于 \(G\) 中两两无公共内顶点的 \(u\)-\(v\) 路的最大数量。

Cor.4.1 非平凡图 \(G\) 是 \(k\) 连通图当且仅当 \(G\) 中任意两个顶点间存在至少 \(k\) 条两两无公共内顶点的路。

Th.4.8 （Menger 定理，边版本）：对于图 \(G=\left\langle V,E\right\rangle\) 和两个顶点 \(u,v\in V\)，使 \(u\) 和 \(v\) 不连通需要从 \(G\) 中删除的边数量等于 \(G\) 中两两无公共边的 \(u\)-\(v\) 路的最大数量。

Cor.4.2 非平凡图 \(G\) 是 \(k\) 边连通图当且仅当 \(G\) 中任意两个顶点间存在至少 \(k\) 条两两无公共边的路。