《图论与网络优化》学习笔记(第1-5章)
上课时间:2023年10月——2024年1月
上课地点:国防科技大学
授课老师:戴丽
教材:戴丽.《图论与网络优化》
注:部分笔记根据自己的理解进行改动,可能不是很严谨,但便于理解。
第一章 图论发展历史
1.1 图论的起源与发展
1736年,Euler研究并解决了konigsberg七桥问题(格林森堡七桥问题)。20世纪图论经历了一场爆炸性的发展,1936年第一本图论著作《有限图和无限图理论》诞生。
- 电网络中的图论
- 有机化学中的图论
- 四色问题
1.2 图论的现状与应用
图论具有很高的实用价值,例如:地图导航、人物关系图、蛋白质网络图、无人机集群网络图等。
第二章 基本概念与运算
2.1 图的定义
图的组成:
图:图
G
G
G 是一个有序的三元组,记作
G
=
<
V
(
G
)
,
E
(
G
)
,
ψ
(
G
)
>
G = <V(G), E(G), \psi(G)>
G=<V(G),E(G),ψ(G)> 。
顶点集:表示为
V
(
G
)
V(G)
V(G) ,顶点数表示为
ν
(
G
)
\nu(G)
ν(G) 。
边集:表示为
E
(
G
)
E(G)
E(G) ,边数表示为
ϵ
(
G
)
\epsilon(G)
ϵ(G) 。
关联函数:表示为
ψ
(
G
)
=
{
u
v
∣
u
∈
V
(
G
)
,
v
∈
V
(
G
)
,
u
≠
v
}
\psi(G) = \{uv | u \in V(G), v \in V(G), u \neq v\}
ψ(G)={uv∣u∈V(G),v∈V(G),u=v} ,也就是顶点对表示的边集。
关联,端点,相邻:设
e
e
e 是图
G
G
G 中的边,
u
,
v
u,v
u,v 为顶点,且
ψ
(
e
)
=
u
v
\psi(e) = uv
ψ(e)=uv ,则称
e
e
e 与
u
u
u 及
v
v
v 关联,称
u
u
u 和
v
v
v 是
e
e
e 的端点,称
u
u
u 与
v
v
v 是相邻的。
邻域:图
G
G
G 中所有与顶点
ν
\nu
ν 相邻的顶点的集合称为
ν
\nu
ν 的邻域,记作
N
(
ν
)
N(\nu)
N(ν) 。
环:两个端点重合的边称为环。
连杆:两个端点不重合的边称为连杆。
k
k
k重边:连接同一对顶点的
k
(
k
≥
2
)
k(k\ge2)
k(k≥2) 条边称为
k
k
k重边。
单边:若一对顶点之间只有一条边,该边称为单边。
简单图:既没有环,也没有重边的图,称为简单图。
度:与顶点
v
v
v 关联的边的数目称为顶点的度,记作
d
(
v
)
d(v)
d(v) 。
度序列:若
v
1
,
v
2
,
.
.
.
,
v
ν
v_1,v_2,...,v_\nu
v1,v2,...,vν 为图的全部顶点,则
(
d
(
v
1
)
,
d
(
v
2
)
,
.
.
.
,
d
(
v
ν
)
)
(d(v_1),d(v_2),...,d(v_\nu))
(d(v1),d(v2),...,d(vν)) 为图的度序列。
孤立点:度为 0 的顶点称为孤立点。
悬挂点:度为 1 的顶点称为悬挂点。
悬挂边:与悬挂点相关联的边称为悬挂边。
偶点:度为偶数的顶点称为偶点。
奇点:度为奇数的顶点称为奇点。
最大度:图
G
G
G 中顶点度的最大值,记作
Δ
(
G
)
\Delta(G)
Δ(G) 。
最小度:图
G
G
G 中顶点度的最小值,记作
δ
(
G
)
\delta(G)
δ(G) 。
定理1 握手引理 对于任意图 G G G ,均有 ∑ v ∈ V d ( V ) = 2 ϵ \textstyle\sum_{v\in V}d(V) = 2\epsilon ∑v∈Vd(V)=2ϵ 。(顶点的度数和等于边数的两倍)
图序列:简单图的度序列称为图序列。
同构:如果能够在两个图
G
1
G_1
G1 和
G
2
G_2
G2 的顶点集之间建立一一对应关系,并且每对顶点之间的边数对应相等,则称
G
1
G_1
G1 和
G
2
G_2
G2 是同构的,表示为
G
1
≊
G
2
G_1 \approxeq G_2
G1≊G2 。
定理2 (给出一个顶点度的序列,判断能否构成图)
非负整数序列 ( d 1 , d 2 , . . . , d ν ) ( d 1 ≥ d 2 ≥ . . . , ≥ d ν ) (d_1,d_2,...,d_\nu)(d_1 \ge d_2 \ge ...,\ge d_\nu) (d1,d2,...,dν)(d1≥d2≥...,≥dν) 是图序列当且仅当 ∑ i = 1 ν d i \sum_{i=1}^{\nu}d_i ∑i=1νdi 是偶数,并且对于一切整数 k ( 1 ≤ k ≤ ν − 1 ) k(1 \le k \le \nu -1) k(1≤k≤ν−1) ,有 ∑ i = 1 k d i ≤ k ( k − 1 ) + ∑ i = k + 1 ν m i n { k , d i } \sum_{i=1}^kd_i\le k(k-1)+\sum_{i=k+1}^{\nu}min\{k,d_i\} ∑i=1kdi≤k(k−1)+∑i=k+1νmin{k,di} 。
2.2 子图和连通分支
子图相关概念:
子图:设
H
H
H 和
G
G
G 是两个图,若
V
(
H
)
⊆
V
(
G
)
V(H) \subseteq V(G)
V(H)⊆V(G) 且
E
(
H
)
⊆
E
(
G
)
E(H) \subseteq E(G)
E(H)⊆E(G) ,则称
H
H
H 为
G
G
G 的子图,记作
H
⊆
G
H \subseteq G
H⊆G 。
图的相等:两个图的顶点和边都对应相等,则称
H
H
H 与
G
G
G 相等,记作
H
=
G
H = G
H=G 。
真子集:若
H
⊆
G
H \subseteq G
H⊆G 且
H
≠
G
H \neq G
H=G ,则称
H
H
H 是
G
G
G 的真子图,记作
H
⊂
G
H \subset G
H⊂G 。
支撑子图 / 生成子图:若图
H
H
H 包括了图
G
G
G 全部顶点和部分边,则称
H
H
H 是
G
G
G 的支撑子图。
基础简单图:不含环且不含重边的图为基础简单图。
导出子图:由图
G
G
G 的部分顶点或部分边导出的子图。
顶点导出子图:取出图
G
G
G 的部分顶点,连接两端都与这些顶点相邻的边,生成顶点导出子图
H
H
H 。
边导出子图:取出图
G
G
G 的部分边,加入这些边相邻的顶点,生成边导出子图
H
H
H 。
连通分支相关概念:
途径:图
G
G
G 的途径是一个有限的非空序列
W
=
v
0
e
1
v
1
e
2
v
2
.
.
.
e
k
v
k
W=v_0e_1v_1e_2v_2...e_kv_k
W=v0e1v1e2v2...ekvk ,其中
v
n
v_n
vn 为
G
G
G 中的顶点,
e
n
e_n
en 为
G
G
G 中的边,也可简化记为
W
=
v
0
v
1
v
2
.
.
.
v
k
W=v_0v_1v_2...v_k
W=v0v1v2...vk 。
v
0
v_0
v0 称为
W
W
W 的起点,
v
k
v_k
vk 称为
W
W
W 的终点,其他的点称为内部点,
k
k
k 称为
W
W
W 的长。
迹:如果途径
W
W
W 的边互不相同,则
W
W
W 称为迹。(允许经过同一顶点)
链:如果途径
W
W
W 的顶点互不相同,则
W
W
W 称为链。(链必然也是迹)一个顶点也是一条链
闭途径:起点与终点重合的途径。
闭迹:起点与终点重合的迹。
圈:起点、内部点互不相同的闭迹称为圈,长为
k
k
k 的圈称为
k
k
k圈。
k
k
k 为奇数则为奇圈,
k
k
k 为偶数则为偶圈。
连通图:若图
G
G
G 中存在
(
u
,
v
)
(u, v)
(u,v) 链,则称顶点
u
u
u 和
v
v
v 在图
G
G
G 中是连通的。图中所有顶点都互相连通的图称为连通图。
连通分支:依据连通性将顶点集
V
V
V 划分为
V
1
,
V
2
.
.
.
V
ω
V_1,V_2...V_\omega
V1,V2...Vω ,导出子图
G
[
V
1
]
,
G
[
V
2
]
.
.
.
G
[
V
ω
]
G[V_1],G[V_2]...G[V_\omega]
G[V1],G[V2]...G[Vω] 称为
G
G
G 的连通分支。
ω
(
G
)
\omega(G)
ω(G) 表示图
G
G
G 的连通分支数。
距离:顶点
u
u
u 和
v
v
v 之间的最短链
(
u
,
v
)
(u, v)
(u,v) 的长为
u
,
v
u, v
u,v 之间的距离,记作
d
(
u
,
v
)
d(u, v)
d(u,v) 。
2.3 重要图类
完全图:每对顶点都相邻的简单图为完全图,记作
K
n
K_n
Kn 。
空图:边集为空的图。
平凡图:图中只有一个顶点的图。
非平凡图:不是平凡图的一切图。(顶点数大于1)
练习 证明:在任意6个人的聚会上,要么有3个人互相认识,要么有3个人互相不认识。
正则图:每个顶点的度都相等的图称为正则图。每个顶点的度都为
k
k
k 的正则图称为
k
k
k正则图。
τ
1
\tau1
τ1法则(偶数正则图生成法则):
τ
2
\tau2
τ2法则(奇数正则图生成法则):
定理1 n n n 阶 k k k正则简单图存在的充要条件是 k ≤ n − 1 k \le n-1 k≤n−1 且 n k nk nk 为偶数。
练习 证明: n n n 阶 k k k正则图一定存在,当且仅当对于任意的正整数 n n n ,若 n k nk nk 为偶数,且 n ≥ k + 1 n \ge k+1 n≥k+1 。
二部图:设图
G
G
G 的顶点集可以划分成两个子集
X
X
X 和
Y
Y
Y ,使得
G
G
G 中每条边的一个端点在
X
X
X 中,另一个端点在
Y
Y
Y 中,则称
G
G
G 图为二部图,记作
G
=
(
X
,
Y
,
E
)
G=(X,Y,E)
G=(X,Y,E) 。
完全二部图:若
X
X
X 中每个顶点与
Y
Y
Y 中每个顶点之间都恰有一条边,且
∣
X
∣
=
m
≠
0
|X|=m\neq 0
∣X∣=m=0 ,
∣
Y
∣
=
n
≠
0
|Y|=n\neq 0
∣Y∣=n=0 ,则称二部图
G
G
G 为完全二部图,记作
K
m
,
n
K_{m,n}
Km,n 。
定理2 二部图的判断
图 G G G 是二部图,当且仅当 G G G 中不含奇圈。
2.4 有向图
有向图的组成:
有向图:有向图
D
D
D 是一个有序三元组,记作
(
V
(
D
)
,
A
(
D
)
,
ψ
D
)
(V(D),A(D),\psi_D)
(V(D),A(D),ψD) 。
顶点集:记作
V
(
D
)
V(D)
V(D) ,其元素为
D
D
D 的顶点。
弧集:记作
A
(
D
)
A(D)
A(D) ,其元素为
D
D
D 的弧(即有向边)。
关联函数:表示弧
a
a
a 与有序顶点
(
u
,
v
)
(u,v)
(u,v) 对之间的关系,记作
ψ
D
(
a
)
=
(
u
,
v
)
\psi_D(a)=(u,v)
ψD(a)=(u,v) ,其中
u
u
u 称为
a
a
a 的尾,
v
v
v 称为
a
a
a 的头。
基础图:将有向图
D
D
D 的弧的方向都去掉,称为是
D
D
D 的基础图。
定向图:给无向图
G
G
G 的边加上方向,称为是
G
G
G 的定向图。
入弧、出弧、入度、出度:以顶点
v
v
v 为头(指向
v
v
v )的弧称为入弧;以顶点
v
v
v 为尾(离开
v
v
v )的弧称为出弧。顶点
v
v
v 的入弧总数称为顶点
v
v
v 的入度,记作
d
D
−
(
v
)
d_D^-(v)
dD−(v) ;顶点
v
v
v 的出弧总数称为顶点
v
v
v 的出度,记作
d
D
+
(
v
)
d_D^+(v)
dD+(v) 。
定理 对于任何有向图 D D D ,所有顶点的入度总和等于出度总和,即 ∑ v ∈ V d D − ( v ) = ∑ v ∈ V d D + ( v ) = ϵ ( D ) \displaystyle\sum_{v \in V}d_D^-(v)=\displaystyle\sum_{v \in V}d_D^+(v)=\epsilon(D) v∈V∑dD−(v)=v∈V∑dD+(v)=ϵ(D) 。
回路相关概念:
有向途径:将途径概念中的图
G
G
G 替换为有向图
D
D
D ,边
e
e
e 替换为弧
a
a
a ,则
W
W
W 为有向途径。其中,
v
0
v_0
v0 称为
W
W
W 的起点,
v
k
v_k
vk 称为
W
W
W 的终点,
k
k
k 称为
W
W
W 的长。
有向闭途径:起点与终点相同的途径。
有向迹:弧互不相同的有向途径。
有向链 / 有向路:顶点互不相同的有向途径。
有向闭迹/回路:起点与终点重合的有向迹。
强连通概念:
强连通:若在
D
D
D 中既存在
(
u
,
v
)
(u,v)
(u,v) 路,又存在
(
v
,
u
)
(v,u)
(v,u) 路,则称
u
u
u 和
v
v
v 在
D
D
D 中是强连通的。(两点之间互相可到达)
强连通分支:由强连通关系确定顶点集
V
(
D
)
V(D)
V(D) 的非空划分
V
1
,
V
2
,
.
.
.
,
V
ω
V_1,V_2,...,V_{\omega}
V1,V2,...,Vω ,它们在
D
D
D 中所导出的顶点子图
D
[
V
1
]
,
D
[
V
2
]
,
.
.
.
,
D
[
V
ω
]
D[V_1],D[V_2],...,D[V_{\omega}]
D[V1],D[V2],...,D[Vω] 称为
D
D
D 的强连通分支。
强连通有向图:只有一个强连通分支的有向图称为强连通有向图。
2.5 矩阵表示
邻接矩阵:
ν
\nu
ν 阶图
G
G
G 的邻接矩阵
A
(
G
)
=
(
a
i
j
)
A(G) = (a_{ij})
A(G)=(aij) 是一个
ν
×
ν
\nu \times \nu
ν×ν 矩阵,其中
a
i
j
a_{ij}
aij 等于第
i
i
i 个顶点与第
j
j
j 个顶点之间的边数。
有向图的邻接矩阵:在邻接矩阵的基础上,
a
i
j
a_{ij}
aij 等于以第
i
i
i 个顶点为尾、以第
j
j
j 个顶点为头的弧数。
邻接矩阵的性质:
(1) A ( G ) A(G) A(G) 是一个以非负整数为元素的 ν \nu ν 阶对称矩阵,即 A T ( G ) = A ( G ) A^T(G) = A(G) AT(G)=A(G) 。
(2) G G G 中第 i i i 个顶点的度等于 2 a i i + ∑ j ≠ i a i j 2a_{ii} + \sum_{j\neq{i}}a_{ij} 2aii+∑j=iaij 。(对角线上为环)
(3)图 G G G 中多个连通分支的邻接矩阵可以表示为对角块的形式。
有向图邻接矩阵的性质:
(1) A ( D ) A(D) A(D) 是一个以非负整数为元素的 ν \nu ν 阶方阵,但不一定是对称的。
(2) D D D 中第 i i i 个顶点的出/入度等于第 i i i 行/列元素之和。
(3)有向图 D D D 中多个连通分支的邻接矩阵可以表示为对角块的形式。
定理 邻接矩阵的 r 次方 A r ( G ) / A r ( D ) A^r(G) / A^r(D) Ar(G)/Ar(D) 表示对应顶点之间长度为 r 的不同途径的个数。
Laplace拉普拉斯矩阵:设 G G G 为非空无环图, A ( G ) A(G) A(G) 为图 G G G 的邻接矩阵,对角矩阵 D ( G ) D(G) D(G) 的对角线上元素为对应顶点的度,则称 L ( G ) = D ( G ) − A ( G ) L(G) = D(G) - A(G) L(G)=D(G)−A(G) 为图 G G G 的Laplace矩阵。
Laplace矩阵的性质:
(1)Laplace矩阵对角线上的值为顶点的度,非对角线上的值为对应顶点之间边数的负数。
(2)Laplace矩阵每行元素的和为 0 。
(3)Laplace矩阵的 0 特征值重数是图的连通分支个数 ω \omega ω 。(其特征值大于等于0,且一定包含0)
关联矩阵:设
G
G
G 是具有
ν
\nu
ν 个顶点和
ϵ
\epsilon
ϵ 条边的非空无环图,
G
G
G 的关联矩阵
M
(
G
)
=
(
m
i
j
)
M(G) = (m_{ij})
M(G)=(mij) 是一个
ν
×
ϵ
\nu \times \epsilon
ν×ϵ 矩阵,其中
m
i
j
m_{ij}
mij 为 1 表示第
i
i
i 个顶点与第
j
j
j 条边关联,否则为 0。
有向图的关联矩阵:在关联矩阵的基础上,
m
i
j
m_{ij}
mij 为 1 表示第
i
i
i 个顶点为第
j
j
j 条边的尾,为 -1 表示第
i
i
i 个顶点为第
j
j
j 条边的头,否则为 0。
关联矩阵的性质:
(1) M ( G ) M(G) M(G) 的每列恰好包含两个1。
(2) M ( G ) M(G) M(G) 中每行所包含的1的个数等于对应顶点的度。
(3)非空无环图 G G G 中多个连通分支的关联矩阵可以表示为对角块的形式。
有向图的关联矩阵的性质:
(1) M ( D ) M(D) M(D) 的每列恰好包含一个 1 和一个 -1,其他为 0。
(2) M ( D ) M(D) M(D) 中每行所包含的 1 的个数等于对应顶点的出度,所包含的 -1 的个数等于对应顶点的入度。
(3)非空无环有向图 D D D 中多个连通分支的关联矩阵可以表示为对角块的形式。
最短路径相关概念:
权:若图中的每一条边
e
e
e 都对应于一个实数
W
(
e
)
W(e)
W(e) ,则
W
(
e
)
W(e)
W(e) 称为边
e
e
e 的权。
无向网络:带权的无向图称为无向网络。
有向网络:带权的有向图称为有向网络。
正权网络:若网络的每条边的权都为正数,则称为正权网络。
最短路:一条路上的所有边对应的实数之和
∑
W
(
e
i
)
\sum{W(e_i)}
∑W(ei) 为路的权。对于顶点
v
i
v_i
vi 和
v
j
v_j
vj ,在网络所有的
(
v
i
,
v
j
)
(v_i, v_j)
(vi,vj) 路中,权最小的路称为
(
v
i
,
v
j
)
(v_i, v_j)
(vi,vj) 之间的最短路。
Dijkstra算法:
2.6 运算
边的删除:
G
−
F
G - F
G−F 表示从图
G
G
G 中将边集
F
F
F 删除,若
F
=
{
e
}
F = \{e\}
F={e} 则可简写为
G
−
e
G - e
G−e 。(删除边操作后得到的必然是支撑子图)
边的添加:
G
+
F
G + F
G+F 表示在图
G
G
G 中添加边集
F
F
F 。
顶点的删除:
G
−
S
G - S
G−S 表示从图
G
G
G 中删除顶点集
S
S
S 及与
S
S
S 中顶点关联的所有边后得到的图。
顶点的添加:
G
+
S
G + S
G+S 表示在图
G
G
G 中添加顶点集
S
S
S 。
图的交:
G
1
∩
G
2
=
(
V
1
∩
V
2
,
E
1
∩
E
2
)
G_1 \cap G_2 = (V_1 \cap V_2, E_1 \cap E_2)
G1∩G2=(V1∩V2,E1∩E2)
图的并:
G
1
∪
G
2
=
(
V
1
∪
V
2
,
E
1
∪
E
2
)
G_1 \cup G_2 = (V_1 \cup V_2, E_1 \cup E_2)
G1∪G2=(V1∪V2,E1∪E2)
图的收缩:设
e
=
u
v
e = uv
e=uv 是图
G
G
G 的一条连杆,在
G
G
G 中去掉
e
e
e ,把顶点
u
u
u 和
v
v
v 合并为一个新顶点,将除
e
e
e 以外其他与顶点
u
,
v
u, v
u,v 关联的边都与新顶点关联,就完成了图的收缩,记作
G
⋅
e
G \cdot e
G⋅e 。
图的剖分:去掉边
e
e
e ,然后添加一个顶点,分别与原先
e
e
e 的两个端点连边,就完成了对边
e
e
e 的剖分。
笛卡尔积:设
G
1
G_1
G1 和
G
2
G_2
G2 分别为两个图,则它们的笛卡尔积表示为
G
1
×
G
2
=
(
V
1
×
V
2
,
E
1
×
E
2
)
G_1 \times G_2 = (V_1 \times V_2, E_1 \times E_2)
G1×G2=(V1×V2,E1×E2) 。(笛卡尔积可用于生成
n
n
n立方体)
第三章 树及其算法
3.1 树和森林
树:连通且不含圈的图称为树,通常用
T
T
T 表示树。
n阶树:含有
n
n
n个顶点的树。
森林:不含圈的图(无圈图),每个连通分支都是树。
支撑树:若图
G
G
G 的支撑子图
T
T
T 是树,则称
T
T
T 为
G
G
G 的支撑树。
从图中获得支撑树的方法:
破圈法:将连通图
G
G
G 中的圈上的任意一条边删除,重复这个过程直到无圈,得到一个支撑树。
避圈法:从空图出发,每次添加一条确保无圈的边,重复这个过程直到加入所有顶点且连通,得到一个支撑树。
定理1 图 G G G 有支撑树当且仅当 G G G 连通
定理2 树的六个等价定义
设 T T T 是 ν \nu ν 阶图,下列命题等价:
- T T T 是树;
- T T T 是无环图,且 T T T 的任何两个顶点间有唯一一条链;
- T T T 是无圈图,且有 ν − 1 \nu - 1 ν−1 条边;
- T T T 是连通图,且有 ν − 1 \nu - 1 ν−1 条边;
- T T T 是连通图,但 ∀ e ∈ E ( T ) \forall e \in E(T) ∀e∈E(T) , T − e T - e T−e 是非连通图;
- T T T 是无圈图,但添加任何一条边后得到的图中将含有唯一的圈。
(证明方式:1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6 ⇒ \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 5 \Rightarrow 6 \Rightarrow ⇒2⇒3⇒4⇒5⇒6⇒ 1)
推论一:若树 T T T 的阶数 ν ≥ 2 \nu \ge 2 ν≥2,则 T T T 至少有两个悬挂点。
推论二:设 G G G 有 ν \nu ν 个顶点, ϵ \epsilon ϵ 条边, ω \omega ω 个连通分支,则 G G G 是森林当且仅当 ϵ = ν − ω \epsilon = \nu - \omega ϵ=ν−ω 。
常用的证明方法:反证法、数学归纳法、分类讨论法、极大极小值原则
3.2 支撑树的计数(给定一个图,判断其互不同构的支撑树的个数)
表示:在图 G G G 中,互不同构的支撑树的个数记作 τ ( G ) \tau(G) τ(G) 。
- 公式法(递推公式):
定理3 设 e e e 是 G G G 的连杆,则 τ ( G ) = τ ( G − e ) + τ ( G ⋅ e ) \tau(G) = \tau(G - e) + \tau(G \cdot e) τ(G)=τ(G−e)+τ(G⋅e) 。
eg.:
- 矩阵-树定理:
定理4 设 G G G 为非空无环连通图,则 τ ( G ) = ∣ L i ( G ) ∣ \tau(G) = |L_i(G)| τ(G)=∣Li(G)∣ ,其中 L i ( G ) L_i(G) Li(G) 表示删去Laplace矩阵 L ( G ) L(G) L(G) 的第 i i i 行和第 i i i 列后得到的矩阵。
- n n n 阶完全图的支撑树个数:
定理5 n n n 阶完全图 K n K_n Kn 的互不相同的支撑树个数 τ ( K n ) = n n − 2 \tau(K_n) = n^{n-2} τ(Kn)=nn−2 。
3.3 树上点和边的性质
割边:图 G G G 中使 ω ( G − e ) > ω ( G ) \omega(G - e) > \omega(G) ω(G−e)>ω(G) 的边 e e e 称为 G G G 的割边。(使连通分支个数增加)
引理1(1) ∀ e ∈ E ( G ) \forall e \in E(G) ∀e∈E(G) ,有 ω ( G ) ≤ ω ( G − e ) ≤ ω ( G ) + 1 \omega(G) \le \omega(G-e) \le \omega(G)+1 ω(G)≤ω(G−e)≤ω(G)+1 。
引理1(2) e e e 是 G G G 的割边 ⇔ ω ( G − e ) = ω ( G ) + 1 \Leftrightarrow \omega(G-e) = \omega(G)+1 ⇔ω(G−e)=ω(G)+1 。
定理1 e ∈ E ( G ) e \in E(G) e∈E(G) 是图 G G G 的割边,当且仅当 e e e 不在 G G G 的任何圈上。
利用割边可以把树的等价定义第五条表述为: T T T 为树 ⇔ T \Leftrightarrow T ⇔T 的每条边都是割边的连通图。
边割:将顶点集
V
(
G
)
V(G)
V(G) 划分为非空子集
S
S
S 和
S
ˉ
\bar{S}
Sˉ ,边割表示
S
S
S 与
S
ˉ
\bar{S}
Sˉ 之间所有的边,即
[
S
,
S
ˉ
]
=
{
u
v
∈
E
(
G
)
∣
u
∈
S
,
v
∈
S
ˉ
}
[S, \bar{S}] = \{uv \in E(G) | u \in S, v \in \bar{S}\}
[S,Sˉ]={uv∈E(G)∣u∈S,v∈Sˉ}
极小边割 / 补圈 / 余圈:任意真子集都不再是边割的边割。
k-边割:含有
k
k
k 条边的边割。
定理2 设 G G G 为连通图,则: G G G 的边割 [ S , S ˉ ] [S, \bar{S}] [S,Sˉ] 是补圈 ⇔ G [ S ] \Leftrightarrow G[S] ⇔G[S] 和 G [ S ˉ ] G[\bar{S}] G[Sˉ] 都连通。
推论1 图 G G G 的边割 [ S , S ˉ ] [S, \bar{S}] [S,Sˉ] 或者是补圈,或者是一些两两不交的补圈的并。
补树:设 G G G 是连通图, T T T 是 G G G 的一个支撑树,则称补图 T ˉ ( G ) \bar{T}(G) Tˉ(G) 为 G G G 的补树,记作 T ˉ \bar{T} Tˉ 。
定理3 设 T T T 是连通图 G G G 的支撑树, e ∈ E ( T ) e \in E(T) e∈E(T) ,则
(1)补树 T ˉ \bar{T} Tˉ 不含有任何极小边割;
(2) T ˉ + e \bar{T} + e Tˉ+e 中含有唯一的极小边割。
割点:把图 G G G 的边集 E E E 分为两个非空子集 E 1 E_1 E1 和 E 2 E_2 E2 ,使 G [ E 1 ] G[E_1] G[E1] 和 G [ E 2 ] G[E_2] G[E2] 有唯一的公共顶点,则该点为图 G G G 的割点。
引理2(1) 若顶点 v v v 满足 ω ( G − v ) > ω ( G ) \omega(G-v) > \omega(G) ω(G−v)>ω(G) ,则 v v v 是 G G G 的割点。
引理2(2) 若 G G G 的割点 v v v 上无环,则 ω ( G − v ) > ω ( G ) \omega(G-v) > \omega(G) ω(G−v)>ω(G) 。
定理4 树 T T T 的顶点 v v v 是割点,当且仅当 d ( v ) > 1 d(v) > 1 d(v)>1 。
3.4 最小支撑树
最小支撑树:树上所有边权之和为树的权,在图 G G G 的所有支撑树中,权最小的支撑树称为最小支撑树。
最小支撑树的生成算法:
Prim算法(贪婪思想):从空集出发(顶点集和边集都为空),每次添加一条边,满足:(1)不构成圈;(2)与已存在的某条边相邻;(3)在未添加的边集中权尽可能小。
Kruskal算法(贪婪思想):从
ν
\nu
ν 阶空图出发(边集为空),每次添加一条边,满足:(1)不构成圈;(2)在未添加的边集中权尽可能小。(Kruskal算法过程中的图可以不连通)
定理1 设 G G G 是连通加权图,由Prim算法构造的支撑树一定是图 G G G 的最小支撑树。
定理2 设 G G G 是连通加权图,由Kruskal算法构造的支撑树一定是图 G G G 的最小支撑树。
3.5 二叉树与前缀码
根:唯一一个入度为0的顶点。
叶子:出度为0的顶点。
根树:
T
T
T 是一棵有向树,且只有一个顶点入度为0,其余顶点入度都为1。
n
n
n元树:树上所有顶点的出度的最大值,即
∀
v
∈
V
(
T
)
,
d
+
(
v
)
≤
n
\forall v \in V(T), d^+(v) \le n
∀v∈V(T),d+(v)≤n 。
经典
n
n
n元树:除叶子顶点外,每个顶点都有
n
n
n 个儿子的根树。
有序树:每个顶点的儿子们有序的根树。
括号列:由左括号“(”和右括号“)”组成的有限序列
好括号列:满足:(1)空列是好的;(2)若A与B是好括号列,则AB也是;(3)若A是好括号列,则(A)也是;(4)除了上述三种情况下的括号列,再无其它好括号列。
引理1 一个括号列是好括号列的充要条件是它由偶数个括号组成,其中一半是左括号,一半是右括号,且从左向右读这个括号列时,任何时刻读出的右括号个数不超过读出的左括号个数。
引理2 由 2 n 2n 2n 个括号组成的好括号列个数是 c ( n + 1 ) = 1 n + 1 C 2 n n c(n+1)=\frac{1}{n+1}C_{2n}^n c(n+1)=n+11C2nn ,这个 c ( n + 1 ) c(n+1) c(n+1) 叫做Catalan数。
定理3 n n n 阶有序二元树的个数是Catalan数 c ( n + 1 ) c(n+1) c(n+1) 。
前缀码:设有一个序列的集合,如果在这个集合中,任何序列都不是另一个序列的前缀,则称这个集合位前缀码。
Huffman树 / 最优二元树:以
v
0
v_0
v0 为根,以
v
1
,
v
2
,
.
.
.
,
v
n
v_1,v_2,...,v_n
v1,v2,...,vn 为叶子的有序二元树中,称
(
v
0
,
v
i
)
(v_0,v_i)
(v0,vi) 链的长
l
i
l_i
li 为叶子
v
i
v_i
vi 的码长。若
v
i
v_i
vi 代表的事物出现的频率为
p
i
p_i
pi ,且
∑
i
=
1
n
p
i
=
1
\sum_{i=1}^np_i=1
∑i=1npi=1 ,则称使
m
(
T
)
=
∑
i
=
1
n
p
i
l
i
m(T)=\displaystyle\sum_{i=1}^np_i l_i
m(T)=i=1∑npili 达到最小的有序二元树
T
T
T 为带权
p
1
,
p
2
,
.
.
.
,
p
n
p_1,p_2,...,p_n
p1,p2,...,pn 的Huffman树。
Huffman树的构造算法:
第四章 最大流及其算法
4.1 容量网络模型
容量网络:容量网络是一个加权有向网络,并且满足:(1)存在唯一一个入度为0的顶点,称为源。(2)存在唯一一个出度为0的顶点,称为汇。(3)每条弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) 上赋权
c
i
j
c_{ij}
cij 是一个非负数,称为弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) 的容量。
流:设
D
D
D 是一个容量网络,
c
i
j
c_{ij}
cij 表示弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) 的容量,
f
f
f 是定义在
D
D
D 的弧集上的一个函数,使每条弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) 对应一个非负实数
f
i
j
f_{ij}
fij ,满足:(1)相容条件:每条弧上的流量小于其容量(2)守恒条件:每个顶点的流入量等于流出量,则称
f
f
f 为容量网络
D
D
D 的一个流,称
f
i
j
f_{ij}
fij 为弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) 上的流量。
流入量:
∑
(
v
i
,
v
j
)
∈
E
(
D
)
f
i
j
\sum_{(v_i,v_j)\in E(D)} f_{ij}
∑(vi,vj)∈E(D)fij 称为流入顶点
v
j
v_j
vj 的流入量。
流出量:
∑
(
v
j
,
v
i
)
∈
E
(
D
)
f
i
j
\sum_{(v_j,v_i)\in E(D)} f_{ij}
∑(vj,vi)∈E(D)fij 称为流入顶点
v
j
v_j
vj 的流出量。
饱和弧、非饱和弧:流量等于容量的弧称为饱和弧,流量小于容量的弧称为非饱和弧。
定理1 在图 D D D 的任意一个流 f f f 中,源的流出量等于汇的流入量。
推论: 弧上的流量之和 = 所有顶点的流入量之和 = 所有顶点的流出量之和。
流值:源的流出量(或汇的流入量)为流
f
f
f 的流值,记作
v
a
l
(
f
)
val(f)
val(f) 。
最大流:容量网络中流值最大的流称为最大流。
(
S
,
S
ˊ
)
(S, \acute{S})
(S,Sˊ) 表示从
S
S
S 指向
S
ˊ
\acute{S}
Sˊ 的弧的集合。
截:设
D
D
D 是一个容量网络,
S
S
S 为
D
D
D 中的一个包含源的顶点子集,其与顶点集的补集为
S
ˉ
\bar{S}
Sˉ ,且汇在
S
ˉ
\bar{S}
Sˉ 中,则记
(
S
,
S
ˉ
)
(S, \bar{S})
(S,Sˉ) 为
D
D
D 的一个截。(等价于一个有方向的边割)
截的容量:截
(
S
,
S
ˉ
)
(S, \bar{S})
(S,Sˉ) 中所有弧的容量之和,记作
c
(
S
,
S
ˉ
)
c(S, \bar{S})
c(S,Sˉ) 。
截的流量:截
(
S
,
S
ˉ
)
(S, \bar{S})
(S,Sˉ) 中所有弧的流量之和,记作
c
f
(
S
,
S
ˉ
)
c_f(S, \bar{S})
cf(S,Sˉ) 。
最小截:容量达到最小的截。
定理2 任意流值不大于任何一个截的流量 v a l ( f ) ≤ c ( S , S ˉ ) val(f) \le c(S, \bar{S}) val(f)≤c(S,Sˉ) 。
可推出公式: c f ( S , S ˉ ) = c f ( S ˉ , S ) + v a l ( f ) ≤ c ( S , S ˉ ) c_f(S,\bar{S})=c_f(\bar{S},S) + val(f) \le c(S, \bar{S}) cf(S,Sˉ)=cf(Sˉ,S)+val(f)≤c(S,Sˉ) ,即截面 f f f 的流量 = = = 截面的反向流量 + + + 源的流出量 ≤ \le ≤ 截面的容量。
规律 流值与截流量相等,当且仅当(1)截 ( S , S ˉ ) (S, \bar{S}) (S,Sˉ) 上的流量与容量相等。(每条弧都饱和)(2)截 ( S ˉ , S ) (\bar{S}, S) (Sˉ,S) 上的流量为0。(每条弧都为0)
4.2 最大流算法
正向弧、反向弧:设
P
P
P 是容量网络中一条从源
v
s
v_s
vs 到
v
t
v_t
vt 的路,则
P
P
P 中与规定方向一致的弧称为正向弧,否则称为反向弧。
f
f
f 饱和路、
f
f
f 非饱和路:设
P
P
P 是一条
(
v
s
,
v
j
)
(v_s,v_j)
(vs,vj) 路,如果同时满足:① 对
P
P
P 中每条正向弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) ,
f
i
j
<
c
i
j
f_{ij}<c_{ij}
fij<cij ;② 对
P
P
P 中每条反向弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) ,
f
i
j
>
0
f_{ij}>0
fij>0 ,则称
(
v
s
,
v
j
)
(v_s,v_j)
(vs,vj) 为
f
f
f 非饱和路,否则称为
f
f
f 饱和路。
f
f
f 可增路:从源到汇的
f
f
f 非饱和路
(
v
s
,
v
t
)
(v_s,v_t)
(vs,vt) 称为
f
f
f 可增路。
定理1 设容量网络 D D D 的源为 v s v_s vs 汇为 v t v_t vt , f f f 为 D D D 的一个流,则 f f f 为最大流当且仅当 D D D 中不存在 f f f 可增路。
最大流构造算法(标号法)
Step1:从任意一个流开始,查找 f f f 可增路。
Step2:如果不存在 f f f 可增路,则得到最大流,算法结束;如果查找到一条 f f f 可增路,跳转到下一步。
Step3:令 Δ = m i n { m i n { c i j − f i j ∣ ( v i , v j ) 为正向弧 } , m i n { f i j ∣ ( v i , v j ) 为反向弧 } } \Delta=min\{min\{c_{ij}-f_{ij}|(v_i,v_j)为正向弧\},min\{f_{ij}|(v_i,v_j)为反向弧\}\} Δ=min{min{cij−fij∣(vi,vj)为正向弧},min{fij∣(vi,vj)为反向弧}} ,修改 f f f 可增路中所有正向弧的流量增加 Δ \Delta Δ ,同时所有反向弧的流量减少 Δ \Delta Δ ,跳转到上一步。
标号法的特点:
(1)构造算法结束时获得最小截 ( S , S ˉ ) (S,\bar{S}) (S,Sˉ) ,其中 S S S 为最后一步获得标号的顶点集。
(2)对于整数容量网络,必然在有限步内构造出最大流;对于无理数容量网络,则不能再有限步内停止。
定理2 最大流最小截定理
在任何容量网络 D D D 中,最大流的流值等于最小截的容量。
4.3 最小费用最大流
费用:设容量网络
D
D
D ,
f
f
f 是其上的一个流,
f
i
j
,
c
i
j
,
b
i
j
f_{ij},c_{ij},b_{ij}
fij,cij,bij 分别为弧
(
v
i
,
v
j
)
(v_i,v_j)
(vi,vj) 上的流量、容量和单位费用,则流
f
f
f 的费用为
b
(
f
)
=
∑
(
v
i
v
j
)
∈
E
(
D
)
f
i
j
b
i
j
b(f)=\displaystyle\sum_{(v_iv_j)\in E(D)}f_{ij}b_{ij}
b(f)=(vivj)∈E(D)∑fijbij
最小费用最大流:在容量网络
D
D
D 的所有最大流中,寻找费用最小的流,这样的流称为最小费用最大流。
最小费用最大流构造算法:
Step1:从容量网络 D D D 的任何一个最大流出发,
Step2:寻找某个圈,修改该圈上各弧的流量使流值保持不变且费用降低,
Step3:直到网络中不存在这样的圈为止。
增广圈:设容量网络
D
D
D ,
f
f
f 是其上的一个流,
Q
Q
Q 是一个具有指定正向的圈,
Q
+
Q^+
Q+ 记为圈
Q
Q
Q 上正向弧的集合,
Q
−
Q^-
Q− 记为圈
Q
Q
Q 上反向弧的集合。若
Q
+
Q^+
Q+ 中所有弧都满足
c
i
j
>
f
i
j
c_{ij}>f_{ij}
cij>fij ,并且
Q
−
Q^-
Q− 中所有弧都满足
f
i
j
>
0
f_{ij}>0
fij>0 ,则称
δ
=
m
i
n
{
m
i
n
{
c
i
j
−
f
i
j
∣
(
v
i
,
v
j
)
为正向弧
}
,
m
i
n
{
f
i
j
∣
(
v
i
,
v
j
)
为反向弧
}
}
\delta = min\{min\{c_{ij}-f_{ij}|(v_i,v_j)为正向弧\},min\{f_{ij}|(v_i,v_j)为反向弧\}\}
δ=min{min{cij−fij∣(vi,vj)为正向弧},min{fij∣(vi,vj)为反向弧}} 为允许修正量,圈
Q
Q
Q 为容量网络
D
D
D 上关于
f
f
f 的增广圈。
修正流:对每个正向弧的
f
i
j
f_{ij}
fij 加上
δ
\delta
δ ,每个反向弧的
f
i
j
f_{ij}
fij 减去
δ
\delta
δ ,圈外的弧流量不变,得到的新流
f
′
f'
f′ 为修正流。
增广圈的费用:
f
f
f 增广圈的费用
b
(
Q
,
f
)
=
∑
(
v
i
,
v
j
)
∈
Q
+
b
i
j
−
∑
(
v
i
,
v
j
)
∈
Q
−
b
i
j
b(Q,f) = \displaystyle\sum_{(v_i,v_j)\in Q^+}b_{ij}-\displaystyle\sum_{(v_i,v_j)\in Q^-}b_{ij}
b(Q,f)=(vi,vj)∈Q+∑bij−(vi,vj)∈Q−∑bij 。
负圈:费用小于0的增广圈称为负圈。
定理3 f f f 是最小费用最大流当且仅当任何 f f f 增广圈 Q Q Q 的费用 b ( Q , f ) ≥ 0 b(Q,f)\ge 0 b(Q,f)≥0 ,即无负圈。
Klein算法:
Step1:求容量网络 D D D 的一个最大流;
Step2:寻找网络中的负圈,若没有负圈,算法结束;若找到一个负圈 Q Q Q ,跳到 Step3。
Step3:修改负圈 Q Q Q 上各弧的流量得到修正流,转 Step2,继续寻找负圈。
第五章 遍历性及其算法
5.1 Euler图
Euler图/欧拉图:若图
G
G
G 中存在一条包含所有边的闭迹
W
W
W ,则称
G
G
G 为Euler图,
W
W
W 称为
G
G
G 的Euler闭迹。
半Euler图:若图
G
G
G 中存在一条包含所有边的迹
P
P
P ,则称
G
G
G 为半Euler图,
P
P
P 称为
G
G
G 的Euler迹。
定理1 设 G G G 是非空连通图,则下面三个命题等价:
(1) G G G 是Euler图;
(2) G G G 中不含奇点;
(3) G G G 可以表示为若干个没有公共边的圈的并。
有向Euler图:若图
D
D
D 中存在一条包含所有弧的有向闭迹
W
W
W ,则称
G
G
G 为有向Euler图,
W
W
W 称为
G
G
G 的有向Euler闭迹。
有向半Euler图:若图
D
D
D 中存在一条包含所有弧的有向迹
P
P
P ,则称
G
G
G 为有向半Euler图,
P
P
P 称为
G
G
G 的有向Euler迹。
定理2 设 D D D 是非空连通有向图,则下面三个命题等价:
(1) D D D 是有向Euler图;
(2) D D D 中所有顶点的入度等于出度;
(3) D D D 可以表示为若干个弧不交的回路的并。
推论1 连通有向图 D D D 是有向半Euler图而不是有向Euler图,当且仅当(1)起点的出度=入度+1,终点的入度=出度+1;(2)其他中间点的入度等于出度。
Fleury算法:从任意顶点出发,除非别无选择,总是选择一条不是割边(在圈上)且没走过的边,直到获得Euler闭迹为止。
定理3 设 G G G 是Euler图, W = v 0 e 1 v 1 . . . e n v n W=v_0e_1v_1...e_nv_n W=v0e1v1...envn 是Fleury算法结束时得到的迹,则 W W W 一定是图 G G G 的Euler闭迹。
Euler图的应用:
编码盘设计问题:对于一个四位二进制编码盘,如何设计盘上16个位置的0/1,使得盘转一周后刚好遍历 2 4 2^4 24 种编码?
解决方案:
Step1:定义一个含有8个编号分别为 ( 000 , 001 , 010 , . . . , 111 ) (000,001,010,...,111) (000,001,010,...,111) 的顶点的图,对于顶点 x 1 x 2 x 3 x_1x_2x_3 x1x2x3 ,添加弧使其与 x 2 x 3 0 x_2x_30 x2x30 和 x 2 x 3 1 x_2x_31 x2x31 以出弧的形式相邻(每个顶点的入度=出度=2),构造出一个有向Euler图 D D D 。
Step2:取图 D D D 的一条有向Euler闭迹 P P P ,如 000 → 000 → 001 → . . . → 100 → 000 000\rightarrow000\rightarrow001\rightarrow...\rightarrow100\rightarrow000 000→000→001→...→100→000 。
Step3:取 P P P 中每个顶点的最后一位 001...00 001...00 001...00 作为序列,即为所求结果。
推广:若编码盘上有 n n n 个顶点,则构造出的有向图为德布鲁英图 B ( 2 , n ) B(2,n) B(2,n) ,得到的序列为德布鲁英序列。
5.2 中国邮递员问题(管梅谷教授提出)
1. 问题描述:从邮局出发,每个街道经过至少一次,最终回到邮局,如何走使得总路程最少?
2. 图论问题转换:在加权连通图 G G G 中,寻找一条经过每条边至少一次且权和最小的闭迹,即寻找 G G G 的最优环游。
3. 算法:奇偶点图上作业法
Step1:若图是欧拉图,则欧拉闭迹是最优解;
Step2:若图不是欧拉图,在图中的每对奇点之间分别找一条链,链上的每条边添加一条重边;
Step3:若两顶点间有 k ( k ≥ 3 ) k(k\ge 3) k(k≥3) 重边,则删除其中的偶数条边。
Step4:检查图中的每一个圈,若圈上所有重边的权和大于所有单边的权和,则将所有重边去掉一条边变为单边,将单边添加一条边变为重边。
Step5:重复执行Step4,直到图中所有圈上的重边权和不超过圈权和的一半。
Step6:用Fleury算法求图的Euler闭迹,即为最优环游。
算法规模:因为需要遍历所有的圈,所以不可能在二项式时间内得解。
定理4 设 G G G 是加权连通图,则奇偶点图上作业法得到的闭途径是最优环游。
5.3 Hamilton图
Hamilton图:若图
G
G
G 中存在包含一切顶点的圈
C
C
C ,则称
G
G
G 为Hamilton图,
C
C
C 称为Hamilton圈。
半Hamilton图:若图
G
G
G 中存在包含一切顶点的链
P
P
P ,则称
G
G
G 为半Hamilton图,
P
P
P 称为Hamilton链。
定理1 Hamilton图的必要条件
(1)若 G G G 是Hamilton图,则 ω ( G − S ) ≤ ∣ S ∣ , ( ∀ S ⊂ V , S ≠ ∅ ) \omega(G-S)\le|S|,(\forall S\subset V,S\neq \varnothing) ω(G−S)≤∣S∣,(∀S⊂V,S=∅) 。(即从 G G G 中删除顶点子集 S S S 后,连通分支个数一定少于 S S S 中顶点个数)
(2)若 G G G 是半Hamilton图,则 ω ( G − S ) ≤ ∣ S ∣ + 1 , ( ∀ S ⊂ V , S ≠ ∅ ) \omega(G-S)\le|S|+1,(\forall S\subset V,S\neq \varnothing) ω(G−S)≤∣S∣+1,(∀S⊂V,S=∅) 。
推论1 对于二部图 G = ( X , Y , E ) G=(X,Y,E) G=(X,Y,E) ,若 G G G 是Hamilton图,则 ∣ X ∣ = ∣ Y ∣ |X|=|Y| ∣X∣=∣Y∣ ;若 G G G 是半Hamilton图,则 ∣ ∣ X ∣ − ∣ Y ∣ ∣ ≤ 1 ||X|-|Y||\le 1 ∣∣X∣−∣Y∣∣≤1 。
闭包:设 G G G 是简单图,反复连接 G G G 中度之和不小于 ν \nu ν 的不相邻顶点对,直到没有这种顶点对为止,这样得到的图称为 G G G 的闭包,记作 c ( G ) c(G) c(G) 。
引理1 设 G G G 是简单图, u u u 和 v v v 在 G G G 中不相邻, u ≠ v u\neq v u=v ,且 d ( u ) + d ( v ) ≥ v d(u)+d(v)\ge v d(u)+d(v)≥v ,则“ G G G 是Hamilton图”的充要条件是“ G + u v G+uv G+uv 是Hamilton图”。
定理2 一个简单图 G G G 是Hamilton图,当且仅当 c ( G ) c(G) c(G) 是Hamilton图。
推论2 设 G G G 是简单图,且 v ≥ 3 v\ge 3 v≥3 ,若 c ( G ) c(G) c(G) 是完全图,则 G G G 是Hamilton图。
推论3 设 G G G 是简单图, v ≥ 3 v\ge 3 v≥3 且对于 G G G 中任意一对不相邻相异顶点 u u u 和 v v v ,有 d ( u ) + d ( v ) ≥ v d(u)+d(v)\ge v d(u)+d(v)≥v ,则 G G G 是Hamilton图。
推论4 设 G G G 是简单图,且 v ≥ 3 v\ge 3 v≥3 , δ ≥ v − 1 2 \delta\ge \frac{v-1}{2} δ≥2v−1 ,则 G G G 是Hamilton图。
推论5 设 G G G 是简单图,且对 G G G 中任何一对不相邻的相异顶点 u u u 和 v v v ,有 d ( u ) + d ( v ) ≥ v − 1 2 d(u)+d(v)\ge\frac{v-1}{2} d(u)+d(v)≥2v−1 ,则 G G G 是半Hamilton图。
推论6 设 G G G 是简单图,并且 δ ≥ v − 1 2 \delta\ge\frac{v-1}{2} δ≥2v−1 ,则 G G G 是半Hamilton图。
定理3(范更华,1984)
设 G G G 连通简单图, ∀ v ∈ V ( G ) \forall v \in V(G) ∀v∈V(G) , G − v G-v G−v 仍连通,对 G G G 中满足 d ( u , v ) = 2 d(u,v)=2 d(u,v)=2 的任意顶点对 u u u 和 v v v 都有 m a x { d ( u ) , d ( v ) } ≥ v 2 max\{d(u),d(v)\}\ge\frac{v}{2} max{d(u),d(v)}≥2v ,则 G G G 是Hamilton图。
注:
(1)以上定理为Hamilton图的充分条件,推论为一些必要条件,尚不存在充分必要条件。
(2)重边和环在研究Hamilton图中没有意义。
格雷码:
- 格雷码即为立方体的Hamilton圈(n立方体是Hamilton图)
5.4 有向Hamilton图
定理1 强连通的充要条件
设 G G G 是连通图,则 G G G 有强连通定向图,当且仅当 G G G 中没有割边。
定理2 强连通的等价刻划
设 D = ( V , A ) D=(V,A) D=(V,A) 是 ν ≥ 2 \nu\ge2 ν≥2 的有向图,则下列命题等价:
(1) D D D 是强连通的;
(2) D D D 是连通的,且 D D D 的每条弧都在一个回路上;
(3) ∀ S ⊂ V \forall S\subset V ∀S⊂V , S ≠ ∅ S\neq\varnothing S=∅ 有 ( S , S ˉ ) ≠ ∅ (S,\bar{S})\neq\varnothing (S,Sˉ)=∅ , ( S ˉ , S ) ≠ ∅ (\bar{S},S)\neq\varnothing (Sˉ,S)=∅
推论1 设 D D D 是简单有向图,且 d D + ( u ) + d D − ( v ) ≥ ν − 1 d_D^+(u)+d_D^-(v)\ge\nu-1 dD+(u)+dD−(v)≥ν−1 , ∀ ( u , v ) ∉ A ( D ) \forall(u,v)\notin A(D) ∀(u,v)∈/A(D) , u ≠ v u\neq v u=v ,则 D D D 是强连通的。
有向Hamilton图:若有向图
D
D
D 中存在包含所有顶点的回路,则称
D
D
D 为有向Hamilton图,这种回路称为
D
D
D 的Hamilton回路。
有向半Hamilton图:若有向图
D
D
D 中存在包含所有顶点的路,则称
D
D
D 为有向半Hamilton图,这样的路称为
D
D
D 的Hamilton路。
竞赛图:任何两个顶点间都恰有一条弧相连的无环有向图,称为竞赛图,即竞赛图就是完全图的定向图。
定理3 任何 ν \nu ν 阶竞赛图 D D D 都是有向半Hamilton图。
定理4 对任何满足 3 ≤ k ≤ ν 3\le k\le \nu 3≤k≤ν 的整数 k k k , ν ≥ 3 \nu\ge3 ν≥3 的强连通竞赛图 D D D 的每个顶点都在 D D D 中某个 k k k 回路上。
推论2 v ≥ 3 v\ge3 v≥3 的竞赛图 D D D 是有向Hamilton图,当且仅当 D D D 是连通的。
定理5 有向Hamilton的充分条件
设 D D D 是 ν ≥ 2 \nu\ge2 ν≥2 的强连通简单有向图,若对任一对不相邻的相异顶点 u u u 和 v v v ,有 d ( u ) + d ( v ) ≥ 2 ν − 1 d(u)+d(v)\ge2\nu-1 d(u)+d(v)≥2ν−1 ,则 D D D 是有向Hamilton图。
5.5 连通度和边连通度
刻画图的连通程度:
顶点割:若在图
G
G
G 中去掉顶点子集
V
ˊ
\acute{V}
Vˊ 使得
G
−
V
ˊ
G-\acute{V}
G−Vˊ 不连通,则称
V
ˊ
\acute{V}
Vˊ 为
G
G
G 的顶点割,若
∣
V
ˊ
∣
=
k
|\acute{V}|=k
∣Vˊ∣=k ,则称
V
ˊ
\acute{V}
Vˊ 为
G
G
G 的
k
k
k顶点割。
连通度:
G
G
G 的最小顶点割中的顶点数为
G
G
G 的连通度,记作
κ
(
G
)
\kappa(G)
κ(G) 。规定完全图的连通度
κ
(
G
)
=
ν
−
1
\kappa(G)=\nu-1
κ(G)=ν−1 。
k
k
k连通图:若图
G
G
G 的连通度
κ
(
G
)
≥
k
\kappa(G)\ge k
κ(G)≥k ,则称
G
G
G 为
k
k
k连通图。(要使图
G
G
G 不连通,至少需要去掉
k
k
k 个顶点)
边连通度:
G
G
G 的最小边割中的边数为
G
G
G 的边连通度,记作
κ
ˊ
(
G
)
\acute\kappa(G)
κˊ(G) 。规定非平凡图或非连通图的边连通度
κ
ˊ
(
G
)
=
0
\acute\kappa(G)=0
κˊ(G)=0 。
k
k
k边连通图:若图
G
G
G 的边连通度
κ
ˊ
(
G
)
≥
k
\acute\kappa(G)\ge k
κˊ(G)≥k ,则称
G
G
G 为
k
k
k边连通图。(要使图
G
G
G 不连通,至少需要去掉
k
k
k 条边)
定理1 对于任何图 G G G 都有 κ ( G ) ≤ κ ˊ ( G ) ≤ δ ( G ) \kappa(G)\le\acute\kappa(G)\le\delta(G) κ(G)≤κˊ(G)≤δ(G) 。( 其中 δ ( G ) = m i n { d ( v ) ∣ d ( v ) ∈ V } \delta(G)=min\{d(v)|d(v)\in V\} δ(G)=min{d(v)∣d(v)∈V},为顶点的最小度)
定理2 对于任何满足 0 < l ≤ m ≤ n 0<l\le m\le n 0<l≤m≤n 的正整数 l , m , n l,m,n l,m,n 总存在一个简单图 G G G ,使得 κ ( G ) = l , κ ˊ ( G ) = m , δ ( G ) = n \kappa(G)=l,\acute\kappa(G)=m,\delta(G)=n κ(G)=l,κˊ(G)=m,δ(G)=n 。
定理3 一个 ν ≥ 3 \nu\ge3 ν≥3 的图 G G G 是2连通图,当且仅当 G G G 的任何两个顶点由至少两条内部不相交的链链接。
推论1 若 G G G 是2连通图,则 G G G 的任何两个顶点在一圈上。
推论2 若 G G G 是 ν ≥ 3 \nu\ge3 ν≥3 的块(2连通图),则 G G G 的任何两条边在一个圈上。
引理1 设 G G G 是 k k k连通图, k ≥ 2 k\ge2 k≥2 ,则对于 G G G 的任何连杆 e e e , G ⋅ e G\cdot e G⋅e 是 k − 1 k-1 k−1 连通图。
引理2 设 κ ( G ) = k ≥ 1 \kappa(G)=k\ge1 κ(G)=k≥1 ,且 V ˊ = { v 1 , v 2 , . . . , v k } \acute{V}=\{v_1,v_2,...,v_k\} Vˊ={v1,v2,...,vk} 是 G G G 的 k k k 顶点割, G 1 , G 2 , . . . , G p G_1,G_2,...,G_p G1,G2,...,Gp 是 G − V ˊ G-\acute{V} G−Vˊ 的全部连通分支,则对于 ∀ 1 ≤ i ≤ k \forall1\le i\le k ∀1≤i≤k 和 ∀ 1 ≤ j ≤ p \forall1\le j\le p ∀1≤j≤p ,顶点 v i v_i vi 必与连通分支 G j G_j Gj 的某个顶点在 G G G 中相邻。
定理4 设 G G G 是3连通图, ν ≥ 5 \nu\ge5 ν≥5 ,则存在 G G G 的连杆 e e e ,使 G ⋅ e G\cdot e G⋅e 仍然是3连通图。
5.6 坚韧度
坚韧度:设
G
G
G 是
ν
\nu
ν 阶图,且至少有一对相异顶点不相邻,则
G
G
G 的坚韧度
t
(
G
)
=
m
i
n
{
∣
S
∣
ω
(
G
−
S
)
∣
S
⊂
V
(
G
)
,
S
≠
∅
,
ω
(
G
−
S
)
≥
2
}
t(G)=min\{\frac{|S|}{\omega(G-S)}|S\subset V(G),S\neq\varnothing,\omega(G-S)\ge2\}
t(G)=min{ω(G−S)∣S∣∣S⊂V(G),S=∅,ω(G−S)≥2} 。对于完全图,规定
t
(
G
)
=
ν
(
G
)
−
1
2
t(G)=\frac{\nu(G)-1}{2}
t(G)=2ν(G)−1 。
t
t
t坚韧图:若图
G
G
G 的坚韧度
t
(
G
)
≥
t
t(G)\ge t
t(G)≥t ,则称
G
G
G 是
t
t
t坚韧图。
坚韧集:若存在
S
∗
⊂
V
(
G
)
S^{*}\subset V(G)
S∗⊂V(G) ,
ω
(
G
−
S
∗
)
≥
2
\omega(G-S^*)\ge2
ω(G−S∗)≥2 满足
t
(
G
)
=
∣
S
∗
∣
ω
(
G
−
S
∗
)
t(G)=\frac{|S^*|}{\omega(G-S^*)}
t(G)=ω(G−S∗)∣S∗∣ ,则称
S
∗
S^*
S∗ 为
G
G
G 的坚韧度顶点集,简称坚韧集。
定理1 设 ν ( ν ≥ 3 ) \nu(\nu\ge3) ν(ν≥3) 阶连通图 G G G ,则 1 ν ( G ) − 1 ≤ t ( G ) ≤ ν ( G ) − 1 2 \frac{1}{\nu(G)-1}\le t(G)\le\frac{\nu(G)-1}{2} ν(G)−11≤t(G)≤2ν(G)−1 。
定理2 设 T T T 是树, Δ \Delta Δ 表示 T T T 的最大度,则有 t ( T ) = 1 Δ t(T)=\frac{1}{\Delta} t(T)=Δ1 。
推论1 设 P P P 是 ν ( ν ≥ 3 ) \nu(\nu\ge3) ν(ν≥3) 的链,则 t ( P ) = 1 2 t(P)=\frac{1}{2} t(P)=21 。
边坚韧度:设 G G G 是一个非平凡连通图,则图 G G G 的边坚韧度 t ˊ ( G ) = m i n { ∣ E ˊ ∣ ω ( G − E ˊ ) − 1 ∣ E ˊ ⊆ E ( G ) , ω ( G − E ˊ ) ≥ 2 } \acute{t}(G)=min\{\frac{|\acute{E}|}{\omega(G-\acute{E})-1}|\acute{E}\subseteq E(G),\omega(G-\acute{E})\ge2\} tˊ(G)=min{ω(G−Eˊ)−1∣Eˊ∣∣Eˊ⊆E(G),ω(G−Eˊ)≥2} 。对于平凡图或非连通图,规定 t ˊ ( G ) = 0 \acute{t}(G)=0 tˊ(G)=0 。文章来源:https://www.toymoban.com/news/detail-816468.html
定理3 对于任何非平凡连通图 G G G ,有 κ ˊ ( G ) 2 < t ˊ ( G ) ≤ κ ˊ ( G ) \frac{\acute\kappa(G)}{2}<\acute{t}(G)\le\acute\kappa(G) 2κˊ(G)<tˊ(G)≤κˊ(G) 。文章来源地址https://www.toymoban.com/news/detail-816468.html
到了这里,关于《图论与网络优化》学习笔记(第1-5章)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!