CSDN 有字數限制，因此筆記分別發布，目前：

1. 【筆記1】概念與計算、樹及其算法
2. 【筆記2】容量網絡模型、遍歷性及其算法
3. 【筆記3】獨立集及其算法

---

6 獨立集及其算法

6.1 獨立集和覆蓋

6.1.1 獨立數和覆蓋數

獨立集：設 $S?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?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{?}$，等于若干個 右邊兩點的補的并，例如 $\overline{?}=(\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 ,?x,y\in S$。于是 $?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?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)?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?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?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=?$，且 $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)(?x\in V)$，而且若 $d_G(x)=d_H(x)(?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})$