支配集、覆盖集、独立集、匹配

支配集与支配数

支配集：设 $G = ⟨ V, E ⟩$ ， $V^{*} \subseteq V$ 。若 $\forall v \in V$ ， $\exists u \in V^{*}$ 使得 $(u, v) \in E$ ，则称 $V^{*}$ 为 $G$ 的一个支配集。

极小支配集： $V^{*}$ 的真子集不是支配集。
最小支配集：元素最少的支配集。
支配数 $γ_{0} (G)$ ：最小支配集中的元素个数。

最小支配集为极小支配集，但反之不真。完全图、轮图、星形图的支配数均为 $1$ 。

点独立集

点独立集：顶点彼此不相邻的顶点集。

极大点独立集：加入任何顶点就不是点独立集。
最大点独立集：元素最多的点独立集。
点独立数 $β_{0} (G)$ ：最大点独立集中的元素个数。

定理：设 $G = ⟨ V, E ⟩$ 中无孤立点，则 $G$ 的极大点独立集都是极小支配集。

点覆盖集

点覆盖集： $V^{*} \subseteq V$ ，使得 $\forall e \in E$ ， $\exists v \in V^{*}$ 与 $e$ 关联。

极小点覆盖集：任何真子集都不是点覆盖集。
最小点覆盖集：顶点数最少的点覆盖集。
点覆盖数 $α_{0} (G)$ ：最小点覆盖的元素个数。

定理：设 $G = ⟨ V, E ⟩$ 无孤立点， $I \subseteq V$ ，则 $I$ 是点覆盖集当且仅当 $V - I$ 为点独立集。

推论：设 $G$ 为 $n$ 阶无孤立顶点图，则 $V^{*}$ 是极小（最小）点覆盖当且仅当 $V - V^{*}$ 是极大（最大）点独立集，从而 $α_{0} + β_{0} = n$ 。

边覆盖集

边覆盖集： $E^{*} \subseteq E$ ，使得 $\forall v \in V$ ， $\exists e \in E^{*}$ 与 $v$ 关联。

极小边覆盖： $E^{*}$ 的真子集不是边覆盖。
最小边覆盖：边数最少的边覆盖。
边覆盖数 $α_{1} (G)$ ：最小边覆盖中元素个数。

匹配（边独立集）

匹配（边独立集）： $E^{*} \subseteq E$ 中各边均不相邻。

极大匹配：不能再添加其他边。
最大匹配：边数最多的匹配。
匹配数 $β_{1} (G)$ ：最大匹配中的边数。
$M$ 饱和点：与 $M$ 中边关联的顶点。
$M$ 非饱和点：不与 $M$ 中边关联的顶点。
完美匹配：图中无 $M$ 非饱和点的匹配。
交错路径：从 $M$ 与 $E - M$ 中交替取边构成的路径。
可增广交错路径：起点和终点都是 $M$ 非饱和点的交错路径。
交错圈：由 $M$ 与 $E - M$ 中的边交替出现构成的圈，一定为偶圈。

定理（贝尔热）： $M$ 为 $G$ 中最大匹配当且仅当 $G$ 中不含 $M$ 的可增广交错路径。

最大匹配与最小边覆盖的关系

定理：设 $n$ 阶图 $G$ 中无孤立顶点：

设 $M$ 为 $G$ 中一个最大匹配，对于 $G$ 中每个 $M$ 非饱和点均取一条与其关联的边，组成边集 $N$ ，则 $M \cup N$ 为 $G$ 中最小边覆盖。
设 $W$ 为 $G$ 中一个最小边覆盖，若 $W$ 中存在相邻的边就移去其中的一条，设移去的边集为 $N$ ，则 $M = W - N$ 为 $G$ 中一个最大匹配。
$G$ 中边覆盖数 $α_{1}$ 与匹配数 $β_{1}$ 满足 $α_{1} + β_{1} = n$ 。

匈牙利算法

匈牙利算法用于求解二部图的最大匹配，核心思想是利用可增广交错路径不断增广匹配。

定理（Hall 定理）：设二部图 $G = ⟨ V_{1}, V_{2}, E ⟩$ ， $∣ V_{1} ∣ \leq ∣ V_{2} ∣$ ， $G$ 中存在从 $V_{1}$ 到 $V_{2}$ 的完备匹配当且仅当 $V_{1}$ 中任意 $k$ 个顶点至少与 $V_{2}$ 中的 $k$ 个顶点相邻。