图论与网络优化3

2023-12-13 05:43:12

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

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

6 独立集及其算法

6.1 独立集和覆盖

6.1.1 独立数和覆盖数

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


6.1.2 性质

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


6.1.3 极大独立集的计算

G = ( V , E ) G=(V,E) G=(V,E) 是简单图,且 V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1?,v2?,...,vn?},约定 (1) G G G 的每个顶点 v i v_i vi? 当作一个布尔变量;(2)布尔积 v i v j v_iv_j vi?vj? 表示包含 v i , v j v_i,v_j vi?,vj?,相应于交运算 v i ∩ v j v_i \cap v_j vi?vj?;(3) 布尔和 v i + v j v_i+v_j vi?+vj? 表示包含 v i v_i vi? v j v_j vj?,相应于并运算 v i ∪ v j v_i \cup v_j vi?vj?
计算 ?  ̄ \overline{\phi} ??,等于若干个 右边两点的补的并,例如 ?  ̄ = ( v 1  ̄ + v 2  ̄ ) ( v 1  ̄ + v 3  ̄ ) ( v 1  ̄ + v 4  ̄ ) ( v 3  ̄ + v 4  ̄ ) ( v 3  ̄ + v 6  ̄ ) ( v 4  ̄ + v 5  ̄ ) ( v 5  ̄ + v 6  ̄ ) = v 2  ̄ v 3  ̄ v 4  ̄ v 6  ̄ + v 2  ̄ v 3  ̄ v 4  ̄ v 5  ̄ + v 1  ̄ v 3  ̄ v 4  ̄ v 6  ̄ + v 1  ̄ v 3  ̄ v 5  ̄ + v 1  ̄ v 2  ̄ v 4  ̄ v 6  ̄ \overline{\phi} = (\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} ??=(v1??+v2??)(v1??+v3??)(v1??+v4??)(v3??+v4??)(v3??+v6??)(v4??+v5??)(v5??+v6??)=v2??v3??v4??v6??+v2??v3??v4??v5??+v1??v3??v4??v6??+v1??v3??v5??+v1??v2??v4??v6??,因此所有极大独立集为 { 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?} α ( G ) = 3 \alpha(G)=3 α(G)=3


6.1.4 独立集与连通度的关系

定理:设 G G G n ( n ≥ 2 ) n(n \geq 2) n(n2) 阶简单图,且对 G G G 中任何不相邻的相异顶点 x , y x,y x,y,均有 d ( x ) + d ( y ) ≥ n d(x)+d(y) \geq n d(x)+d(y)n,则 α ( G ) ≤ K ( G ) \alpha(G) \leq K(G) α(G)K(G)
证明:完全图下,结论显然成立。
(反证法)若 α ( G ) ≥ K ( G ) + 1 \alpha(G) \geq K(G) + 1 α(G)K(G)+1,设 S , T S,T S,T 分别是 G G G 中最大独立集和最小顶点割,则有 ∣ S ∣ = α ( G ) = α ≥ 2 |S| = \alpha(G) = \alpha \geq 2 S=α(G)=α2 ∣ T ∣ = K ( G ) = k |T| = K(G) = k T=K(G)=k。设 G 1 , G 2 , . . . , G l G_1,G_2,...,G_l G1?,G2?,...,Gl? G ? T G-T G?T 的连通分支, l ≥ 2 l \geq 2 l2,则由 S S S 是独立集知 ∣ N G ( x ) ∪ N G ( y ) ≤ n ? α , ? x , y ∈ S |N_G(x) \cup N_G(y) \leq n - \alpha, \forall x,y \in S NG?(x)NG?(y)n?α,?x,yS。于是 ? x , y ∈ S \forall x,y \in S ?x,yS,有 ∣ N G ( x ) ∪ N G ( y ) ∣ = ∣ N G ( x ) ∣ + ∣ N G ( y ) ∣ ? ∣ N G ( x ) ∪ N G ( y ) ∣ = d G ( x ) + d G ( y ) ? ∣ N G ( x ) ∪ N G ( y ) ∣ ≥ n ? ( n ? α ) = α ≥ k + 1 > ∣ T ∣ |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)| \geq n-(n-\alpha)=\alpha \geq k + 1 > |T| NG?(x)NG?(y)=NG?(x)+NG?(y)?NG?(x)NG?(y)=dG?(x)+dG?(y)?NG?(x)NG?(y)n?(n?α)=αk+1>T
注意到,与属于 G ? T G-T G?T 的不同连通分支的两个顶点同时相邻的顶点只能属于 T T T,故上式表明,在 G ? T G-T G?T 中,恰有一个连通分支含 S S S 中顶点。不妨设 S ? V ( G 1 ) ∪ T , x ∈ V ( G 1 ) ∩ S S \subseteq V(G_1) \cup T, x \in V(G_1) \cap S S?V(G1?)T,xV(G1?)S,令 y ∈ V ( G 2 ) y \in V(G_2) yV(G2?),则 ∣ N G ( x ) ∪ N G ( y ) ∣ ≤ n ? ∣ S ? V ( G 1 ) ? 1 ∣ = n ? α + ∣ S ∩ T ∣ ? 1 |N_G(x) \cup N_G(y)| \leq n - |S-V(G_1)-1| = n - \alpha + |S \cap T| -1 NG?(x)NG?(y)n?S?V(G1?)?1∣=n?α+ST?1。又因为 N G ( x ) ∩ N G ( y ) ? T N_G(x) \cap N_G(y) \subseteq T NG?(x)NG?(y)?T \ S S S,.所以 ∣ N G ( x ) ∩ N G ( y ) ≤ k ? ∣ S ∩ T ∣ |N_G(x) \cap N_G(y) \leq k - |S \cap T| NG?(x)NG?(y)k?ST。综合两个式子,得 d G ( x ) + d G ( y ) = ∣ N G ( x ) ∪ N G ( y ) ∣ + ∣ N G ( x ) ∩ N G ( y ) ∣ ≤ ( n ? α + ∣ S ∩ T ∣ ? 1 ) + ( k ? ∣ S ∩ T ∣ ) = n ? α + k ? 1 ≤ n ? 2 d_G(x)+d_G(y) = |N_G(x) \cup N_G(y)| + |N_G(x) \cap N_G(y)| \leq (n-\alpha+|S \cap T| -1) + (k - |S \cap T|) = n - \alpha + k - 1 \leq n - 2 dG?(x)+dG?(y)=NG?(x)NG?(y)+NG?(x)NG?(y)(n?α+ST?1)+(k?ST)=n?α+k?1n?2 与已知矛盾,所以 α ( G ) ≤ K ( G ) \alpha(G) \leq K(G) α(G)K(G)


6.2 Ramsey数

6.2.1 Ramsey数

Ramsey数:给定正整数 k , l k,l k,l,若存在一个正整数 n n n,使得任何 n n n 阶简单图或者含有 k k k 团,或者含有 l l l 独立集,则记之为 n → ( k , l ) n \rightarrow (k,l) n(k,l),并称使 n → ( k , l ) n \rightarrow (k,l) n(k,l) 成立的最小正整数 n n n R a m s e y Ramsey Ramsey 数,记作 r ( k , l ) r(k,l) r(k,l)
R a m s e y Ramsey Ramsey 数的定义,容易得到如下结论:

  1. n ′ ≥ n n' \geq n nn,且 n → ( k , l ) n \rightarrow (k,l) n(k,l),则 n ′ → ( k , l ) n' \rightarrow (k,l) n(k,l)
  2. r ( k , l ) r(k,l) r(k,l) 存在,则 r ( l , k ) r(l,k) r(l,k) 也存在,且 r ( k , l ) = r ( l , k ) r(k,l)=r(l,k) r(k,l)=r(l,k)
  3. r ( 1 , l ) = r ( l , 1 ) = 1 r(1,l)=r(l,1)=1 r(1,l)=r(l,1)=1
  4. r ( 2 , l ) = r ( l , 2 ) = l r(2,l)=r(l,2)=l r(2,l)=r(l,2)=l

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


6.2.2 Ramsey数的上界

定理:对任何正整数 k ≥ 2 , l ≥ 2 k \geq 2, l \geq 2 k2,l2,有 r ( k , l ) ≤ r ( k ? 1 , l ) + r ( k , l ? 1 ) r(k,l) \leq r(k-1,l) + r(k,l-1) r(k,l)r(k?1,l)+r(k,l?1),并且若 r ( k ? 1. l ) r(k-1.l) r(k?1.l) r ( k , l ? 1 ) r(k,l-1) r(k,l?1) 都是偶数,则有 r ( k , l ) ≤ r ( k ? 1 , l ) + r ( k , l ? 1 ) ? 1 r(k,l) \leq r(k-1,l) + r(k,l-1) - 1 r(k,l)r(k?1,l)+r(k,l?1)?1
证明…
定理:对于任何正整数 k , l k,l k,l,都有 r ( k , l ) ≤ C k + l ? 2 k ? 1 r(k,l) \leq C_{k+l-2}^{k-1} r(k,l)Ck+l?2k?1?
证明:对 k + l k+l k+l 用数学归纳法,利用 r ( 1 , l ) = r ( k , 1 ) = 1 r(1,l) = r(k,1) = 1 r(1,l)=r(k,1)=1 r ( 2 , l ) = l , r ( k , 2 ) = k r(2,l)=l,r(k,2)=k r(2,l)=l,r(k,2)=k 知, k + l ≤ 5 k+l \leq 5 k+l5 时,结论成立。设 m , n m,n m,n 为正整数,假设结论满足 5 ≤ k + l < m + n 5 \leq k+l < m+n 5k+l<m+n 的一切正整数 k , l k,l k,l 都成立,于是有 r ( m , n ) ≤ r ( m , n ? 1 ) + r ( m ? 1 , n ) ≤ C m + n ? 3 m ? 1 + C m + n ? 3 m ? 2 = C m + n ? 2 m ? 1 r(m,n) \leq r(m,n-1) + r(m-1,n) \leq C_{m+n-3}^{m-1} + C_{m+n-3}^{m-2}=C_{m+n-2}^{m-1} r(m,n)r(m,n?1)+r(m?1,n)Cm+n?3m?1?+Cm+n?3m?2?=Cm+n?2m?1?,由归纳原理,结论对一切正整数 k , l k,l k,l 成立。


6.2.3 Ramsey数的下界

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


6.2.4 Turan定理

k k k 部图:若图 G G G 的顶点集 V V V 可以划分成 V = V 1 ∪ V 2 ∪ . . . ∪ V k V=V_1 \cup V_2 \cup ... \cup V_k V=V1?V2?...Vk?,这里 V i ∩ V j = ? V_i \cap V_j = \emptyset Vi?Vj?=?,且 V i V_i Vi? 中任何两个顶点在 G G G 中都不相邻,则称 G G G k k k 部图,且 V i V_i Vi? 中任一顶点与 V j V_j Vj? 任一顶点之间恰有一条边相连 ( 1 ≤ i < j ≤ k 1 \leq i < j \leq k 1i<jk),则称 G G G 是完全 k k k 部图。

定理:若简单图 G G G 不包含 K k + 1 K_{k+1} Kk+1?,则存在一个以 V = V ( G ) V=V(G) V=V(G) 为顶点集的完全 k k k 部图 H H H,使得 d G ( x ) ≤ d H ( x ) ( ? x ∈ V ) d_G(x) \leq d_H(x)(\forall x \in V) dG?(x)dH?(x)(?xV),而且若 d G ( x ) = d H ( x ) ( ? x ∈ V ) d_G(x)=d_H(x) (\forall x \in V) dG?(x)=dH?(x)(?xV),则 G G G H H H
证明:…
Turan图:设 v v v n n n 阶完全 k k k 部图,若每一个 V i V_i Vi? 取值都在 v k \frac{v}{k} kv? 的下界与上界范围内,则把 G G G 记作 T v , k T_{v,k} Tv,k?,即 T v , k T_{v,k} Tv,k? 中任何两个 V i , V j V_i,V_j Vi?,Vj? 的顶点数最多相差 1 1 1
引理:设 G G G v v v 阶完全 k k k 部图,则 ε ( G ) ≤ ε ( T v , k ) \varepsilon(G) \leq \varepsilon(T_{v,k}) ε(G)ε(Tv,k?),并且若 ε ( G ) = ε ( T v , k ) \varepsilon(G)=\varepsilon(T_{v,k}) ε(G)=ε(Tv,k?),则 G G G T v , k T_{v,k} Tv,k?
证明:…
定理: e x ( v , K k + 1 ) = ε ( T v , k ) ex(v,K_{k+1}) = \varepsilon(T_{v,k}) ex(v,Kk+1?)=ε(Tv,k?)

文章来源:https://blog.csdn.net/LH_991215/article/details/134896740
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。