L011 独立、覆盖和支配

「边独立集」、「极大边独立集」、「最大边独立集」、「边独立数」

「边覆盖集」、「极小边覆盖集」、「最小边覆盖集」、「边覆盖数」

「边支配集」、「极小边支配集」、「最小边支配集」、「边支配数」

Th.8.1-8.3 Cor.8.1

Th.8.4 对于任意一个图，存在一个最小边支配集是极大边独立集。

Cor.8.2 对于任意一个图，边支配数是最小的极大边独立集包含的边数。

最大边独立集即最大匹配。

【Algo.8.1】

Th.8.5

最小边支配集的计算是一个 NP 难的优化问题。

【Algo.8.2】

Th.8.6

Th.8.7 极大边独立集包含的边数不超过最小边支配集包含的边数的 2 倍。

「点独立集」、「极大点独立集」、「最大点独立集」、「点独立数」

「点覆盖集」、「极小点覆盖集」、「最小点覆盖集」、「点覆盖数」

「点支配集」、「极小点支配集」、「最小点支配集」、「点支配数」

Th.8.8-8.16

最大点独立集即补图的最大团。

对于图 $H=\langle V,E\rangle $ 和顶点子集 $C\subseteq V$，若 $C$ 中顶点两两相邻，则 $C$ 称为 $H$ 的「团」（clique），顶点数量最多的团称作 $H$ 的「最大团」（maximum clique）。最大团的计算是一个 NP 难的优化问题。

【Algo.8.3】计算了一个点独立集合 $I$，称其为较大点独立集。

Th.8.17

Th.8.18 $\alpha(G)\le (\Delta(G)+1)|I|$.

Th.8.19 $\alpha(G)\le \dfrac{\Delta(G)+2}{3}|I|$.

最小点覆盖集的计算是一个 NP 难的优化问题。

【Algo.8.4】计算了一个点覆盖集合 $C$，称其为较小点覆盖集。

Th.8.20

Th.8.21 $|C|\le 2\beta(G)$.

最小点支配集的计算是一个 NP 难的优化问题，该问题可归约为「集合覆盖问题」（set covering problem）。

【Algo.8.5】计算了一个点支配集合 $D$，称其为较小点支配集。

Th.8.22

Th.8.23 对于阶为 $n$ 的图 $G$，有：$|D|\le (\ln n-\ln\ln n+\Theta(1))\gamma(G)$.