图论与网络优化3
CSDN 有字数限制,因此笔记分别发布,目前:
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
v∈K,都不是覆盖,则称
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(n≥2) 阶简单图,且对
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
l≥2,则由
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,y∈S。于是
?
x
,
y
∈
S
\forall x,y \in S
?x,y∈S,有
∣
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,x∈V(G1?)∩S,令
y
∈
V
(
G
2
)
y \in V(G_2)
y∈V(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?α+∣S∩T∣?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?∣S∩T∣。综合两个式子,得
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?α+∣S∩T∣?1)+(k?∣S∩T∣)=n?α+k?1≤n?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 数的定义,容易得到如下结论:
- n ′ ≥ n n' \geq n n′≥n,且 n → ( k , l ) n \rightarrow (k,l) n→(k,l),则 n ′ → ( k , l ) n' \rightarrow (k,l) n′→(k,l)
- 若 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)
- r ( 1 , l ) = r ( l , 1 ) = 1 r(1,l)=r(l,1)=1 r(1,l)=r(l,1)=1
- 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
k≥2,l≥2。假设
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)
v∈V(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)
∣S∣≥r(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
k≥2,l≥2,有
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+l≤5 时,结论成立。设
m
,
n
m,n
m,n 为正整数,假设结论满足
5
≤
k
+
l
<
m
+
n
5 \leq k+l < m+n
5≤k+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 1≤i<j≤k),则称 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)(?x∈V),而且若
d
G
(
x
)
=
d
H
(
x
)
(
?
x
∈
V
)
d_G(x)=d_H(x) (\forall x \in V)
dG?(x)=dH?(x)(?x∈V),则
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?)
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!