图论与网络优化3

CSDN 有字数限制，因此笔记分别发布，目前：

1. 【笔记1】概念与计算、树及其算法
2. 【笔记2】容量网络模型、遍历性及其算法
3. 【笔记3】独立集及其算法

6 独立集及其算法

6.1 独立集和覆盖

6.1.1 独立数和覆盖数

独立集：设 $S\subseteq V(G)$，若 $S$ 中任意两个顶点在 $G$ 中都不相邻，即 $G[S]$ 是空图，则称顶点子集 $S$ 是 $G$ 的一个顶点独立集，简称独立集。
团：若 $S$ 中任何两个相异顶点都相邻，则称 $S$ 为团。含有 $k$ 个顶点的独立集，称为 $k$ 独立集。含有 $k$ 个顶点的团称为 $k$ 团。
极大独立集：设 $S$ 是图 $G$ 的独立集，但是任意增加一个顶点不再是独立集，则称 $S$ 为极大独立集。
最大独立集：$G$ 中顶点数最多的独立集，称为 $G$ 的最大独立集，数量大小记作 $\alpha (G)$。
覆盖：$G$ 的顶点集的一个子集，包含 $G$ 的每一条边的至少一个顶点。若 $K$ 是图 $G$ 的覆盖，但对任何 $v\in K$，都不是覆盖，则称 $K$ 为极小覆盖。
最小覆盖：顶点数最少的覆盖称为最小覆盖，顶点数记作 $\beta (G)$。

6.1.2 性质

定理：设 $S\subset V(G)$ 为顶点子集，则 $S$ 是 $G$ 的独立集的充要条件是 $\overline{S}$ 为 $G$ 的覆盖。
证明：设 $S$ 是 $G$ 的独立集，则 $G$ 的任何一条边都至少有一个端点是 $\overline{S}$ 中的顶点，故 $\overline{S}$ 是 $G$ 的覆盖。
设 $\overline{S}$ 是 $G$ 的覆盖，则 $G$ 的任何一条边都至少有一个端点属于 $\overline{S}$，从而 $G$ 的任何一条边都不可能两个端点都在 $S$中，亦即 $S$ 中任何两个顶点都不想林，故 $S$ 是 $G$ 的独立集。
定理：对于任何图 $G$，有 $\alpha (G)+\beta (G)=v(G)$。
证明：设 $S$ 是 $G$ 的一个最大独立集， $K$ 是 $G$ 的最小覆盖， $V(G)$ \ $K$ 是 $G$ 的独立集，$V(G)$ \ $S$ 是 $G$ 的覆盖。因此， $v(G)-\beta (G)\le |V(G)$ \ $K|\le \alpha (G)$，$v(G)-\alpha (G)\le |V(G)$ \ $S|\le \beta (G)$,移项得证。

6.1.3 极大独立集的计算

设 $G=(V,E)$ 是简单图，且 V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={ v1​,v2​,...,vn​}，约定 (1) $G$ 的每个顶点 $v_i$ 当作一个布尔变量；(2)布尔积 $v_i{v}_j$ 表示包含 $v_i,v_j$，相应于交运算 $v_i\cap v_j$；(3) 布尔和 $v_i+v_j$ 表示包含 $v_i$ 或 $v_j$，相应于并运算 $v_i\cup v_j$。
计算 $\overline{\varphi }$，等于若干个 右边两点的补的并，例如 $\overline{\varphi }=(\overline{v_1}+\overline{v_2})(\overline{v_1}+\overline{v_3})(\overline{v_1}+\overline{v_4})(\overline{v_3}+\overline{v_4})(\overline{v_3}+\overline{v_6})(\overline{v_4}+\overline{v_5})(\overline{v_5}+\overline{v_6})=\overline{v_2}\overline{v_3}\overline{v_4}\overline{v_6}+\overline{v_2}\overline{v_3}\overline{v_4}\overline{v_5}+\overline{v_1}\overline{v_3}\overline{v_4}\overline{v_6}+\overline{v_1}\overline{v_3}\overline{v_5}+\overline{v_1}\overline{v_2}\overline{v_4}\overline{v_6}$，因此所有极大独立集为 { v 1 , v 5 } , { v 1 , v 6 } , { v 2 , v 5 } , { v 2 , v 4 , v 6 } , { v 3 , v 5 } \{v_1,v_5\},\{v_1,v_6\},\{v_2,v_5\},\{v_2,v_4,v_6\},\{v_3,v_5\} { v1​,v5​},{ v1​,v6​},{ v2​,v5​},{ v2​,v4​,v6​},{ v3​,v5​}，最大独立集为 { v 2 , v 4 , v 6 } \{v_2,v_4,v_6\} { v2​,v4​,v6​}，$\alpha (G)=3$。

6.1.4 独立集与连通度的关系

定理：设 $G$ 是 $n(n\ge 2)$ 阶简单图，且对 $G$ 中任何不相邻的相异顶点 $x,y$，均有 $d(x)+d(y)\ge n$，则 $\alpha (G)\le K(G)$。
证明：完全图下，结论显然成立。
(反证法)若 $\alpha (G)\ge K(G)+1$，设 $S,T$ 分别是 $G$ 中最大独立集和最小顶点割，则有 $|S|=\alpha (G)=\alpha \ge 2$，$|T|=K(G)=k$。设 $G_1,G_2,...,G_l$ 是 $G-T$ 的连通分支，$l\ge 2$，则由 $S$ 是独立集知 $|N_G(x)\cup N_G(y)\le n-\alpha ,\forall x,y\in S$。于是 $\forall x,y\in S$，有 $|N_G(x)\cup N_G(y)|=|N_G(x)|+|N_G(y)|-|N_G(x)\cup N_G(y)|=d_G(x)+d_G(y)-|N_G(x)\cup N_G(y)|\ge n-(n-\alpha )=\alpha \ge k+1>|T|$。
注意到，与属于 $G-T$ 的不同连通分支的两个顶点同时相邻的顶点只能属于 $T$，故上式表明，在 $G-T$ 中，恰有一个连通分支含 $S$ 中顶点。不妨设 $S\subseteq V(G_1)\cup T,x\in V(G_1)\cap S$，令 $y\in V(G_2)$，则 $|N_G(x)\cup N_G(y)|\le n-|S-V(G_1)-1|=n-\alpha +|S\cap T|-1$。又因为 $N_G(x)\cap N_G(y)\subseteq T$ \ $S$,.所以 $|N_G(x)\cap N_G(y)\le k-|S\cap T|$。综合两个式子，得 $d_G(x)+d_G(y)=|N_G(x)\cup N_G(y)|+|N_G(x)\cap N_G(y)|\le (n-\alpha +|S\cap T|-1)+(k-|S\cap T|)=n-\alpha +k-1\le n-2$ 与已知矛盾，所以 $\alpha (G)\le K(G)$。

6.2 Ramsey数

6.2.1 Ramsey数

Ramsey数：给定正整数 $k,l$，若存在一个正整数 $n$，使得任何 $n$ 阶简单图或者含有 $k$ 团，或者含有 $l$ 独立集，则记之为 $n\to (k,l)$，并称使 $n\to (k,l)$ 成立的最小正整数 $n$ 为 $Ramsey$ 数，记作 $r(k,l)$。
由 $Ramsey$ 数的定义，容易得到如下结论：

1. $n^{\prime }\ge n$，且 $n\to (k,l)$，则 $n^{\prime }\to (k,l)$
2. 若 $r(k,l)$ 存在，则 $r(l,k)$ 也存在，且 $r(k,l)=r(l,k)$
3. $r(1,l)=r(l,1)=1$
4. $r(2,l)=r(l,2)=l$

定理：对于任何正整数 $k,l$，有 $(k,l)$ 存在。
证明：对 $k,l$ 使用双重归纳法。已知对任何正整数 $k,l$，$r(k,1)=r(1,l)=1$，下设 $k\ge 2,l\ge 2$。假设 $r(k-1,l)，r(k,l-1)$ 都存在，往证 $r(k-1,l)+r(k,l-1)\to (k,l)$。设 $G$ 是任意一个 $r(k-1,l)+r(k,l-1)$ 阶简单图，设 $v\in V(G)$，因为 $d_G(v)+d_{\overline{G}}(v)=r(k-1,l)+r(k,l-1)-1$，所以下列两种情况必有一种出现：（1）$d_G(v)\ge r(k-1,l)$，（2）$d_{\overline{G}}(v)\ge r(k,l-1)$。若（1）出现，记 $N_G(v)=S$，则 $|S|\ge r(k-1.l)$，从而 $G[S]$ 中或者含有 $k-1$ 团，或者含有 $l$ 独立集，于是 G [ S ∪ { v } ] G[S \cup \{v\}] G[S∪{ v}] 中或者含有 $k$ 团，或者含有 $l$ 独立集。若（2）出现，注意到 $r(k,l-1)=r(l-1,k)$，通过类似推理，也能得到上述推论，综上得证，从而 $r(k,l)$ 存在。

6.2.2 Ramsey数的上界

定理：对任何正整数 $k\ge 2,l\ge 2$，有 $r(k,l)\le r(k-1,l)+r(k,l-1)$，并且若 $r(k-1.l)$，$r(k,l-1)$ 都是偶数，则有 $r(k,l)\le r(k-1,l)+r(k,l-1)-1$。
证明…
定理：对于任何正整数 $k,l$，都有 $r(k,l)\le C_{k+l-2}^{k-1}$。
证明：对 $k+l$ 用数学归纳法，利用 $r(1,l)=r(k,1)=1$ 及 $r(2,l)=l,r(k,2)=k$ 知，$k+l\le 5$ 时，结论成立。设 $m,n$ 为正整数，假设结论满足 $5\le k+l<m+n$ 的一切正整数 $k,l$ 都成立，于是有 $r(m,n)\le r(m,n-1)+r(m-1,n)\le C_{m+n-3}^{m-1}+C_{m+n-3}^{m-2}=C_{m+n-2}^{m-1}$，由归纳原理，结论对一切正整数 $k,l$ 成立。

6.2.3 Ramsey数的下界

定理：对于任何正整数 $k$，有 $r(k,k)>k\cdot 2^{\frac{k}{2}-2}$。
证明：…
推论：对任何正整数 $k,l$，记 m = m i n { k , l } m=min\{k,l\} m=min{ k,l}，则 $r(k,l)>m\cdot 2^{\frac{m}{2}-2}$

6.2.4 Turan定理

$k$ 部图：若图 $G$ 的顶点集 $V$ 可以划分成 $V=V_1\cup V_2\cup ...\cup V_k$，这里 $V_i\cap V_j=\varnothing$，且 $V_i$ 中任何两个顶点在 $G$ 中都不相邻，则称 $G$ 是 $k$ 部图，且 $V_i$ 中任一顶点与 $V_j$ 任一顶点之间恰有一条边相连 ($1\le i<j\le k$)，则称 $G$ 是完全 $k$ 部图。

定理：若简单图 $G$ 不包含 $K_{k+1}$，则存在一个以 $V=V(G)$ 为顶点集的完全 $k$ 部图 $H$，使得 $d_G(x)\le d_H(x)(\forall x\in V)$，而且若 $d_G(x)=d_H(x)(\forall x\in V)$，则 $G$ ≌ $H$。
证明：…
Turan图：设 $v$ 是 $n$ 阶完全 $k$ 部图，若每一个 $V_i$ 取值都在 $\frac{v}{k}$ 的下界与上界范围内，则把 $G$ 记作 $T_{v,k}$，即 $T_{v,k}$ 中任何两个 $V_i,V_j$ 的顶点数最多相差 $1$。
引理：设 $G$ 是 $v$ 阶完全 $k$ 部图，则 $\epsilon (G)\le \epsilon (T_{v,k})$，并且若 $\epsilon (G)=\epsilon (T_{v,k})$，则 $G$ ≌ $T_{v,k}$。
证明：…
定理：$ex(v,K_{k+1})=\epsilon (T_{v,k})$