图论与网络优化-CSDN博客
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
2.概念与计算
2.1 图的定义
图(graph)
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) 是顶点集。
E
(
G
)
E(G)
E(G) 是边集。
ψ
(
G
)
\psi (G)
ψ(G) 是关联函数例如
ψ
G
(
e
)
=
v
i
v
j
\psi_G (e)=v_iv_j
ψG(e)=vivj。
N
G
(
v
)
N_G(v)
NG(v) 表示点
v
v
v 的一阶邻域点。
相邻与同一个顶点关联的两条边是相邻的。
环两个端点重合的边称为环。
连杆端点不重合的边成为连杆。
k
k
k 重边连接同一对顶点的
k
k
k 条边。
单边一对顶点之间只有一条边。
简单图无环无重边
度与顶点
v
v
v 关联的边的数目记作
d
(
v
)
d(v)
d(v)。
度序列
(
d
(
v
1
)
,
d
(
v
2
)
,
.
.
.
,
d
(
v
v
)
)
(d(v_1),d(v_2),...,d(v_v))
(d(v1),d(v2),...,d(vv))
孤立点度为
0
0
0。
悬挂点度为
1
1
1。
悬挂边与悬挂点相关联的边。
偶点度为偶数的顶点。
奇点度为奇数的顶点。
最小度
δ
(
G
)
\delta(G)
δ(G)图
G
G
G 顶点度的最小值。
最大度
Δ
(
G
)
\Delta(G)
Δ(G)图
G
G
G 顶点度的最大值。
握手引理
∑
v
∈
V
=
2
ϵ
\sum_{v\in V} = 2 \epsilon
∑v∈V=2ϵ。
例题空间中不存在有奇数个面并且每个面只有奇数个棱的多面体。
思路将面抽象为点两面之间的棱为边则转化成了有奇数个点且每个点都是奇数度的图与握手引理矛盾得证。
例题证明非负整数序列
(
d
1
,
d
2
,
.
.
.
,
d
v
)
(d_1,d_2,...,d_v)
(d1,d2,...,dv) 是某个图的度序列当且仅当
∑
i
=
1
v
d
i
\sum_{i=1}^{v} d_i
∑i=1vdi 是偶数。
思路先画出
v
v
v 个孤立点然后选序列中度大于
1
1
1 的点连环直至将每个点仍需添加的度为
0
0
0 或
1
1
1。然后将两两选择度为
1
1
1 的点。能连通即可得证。
图序列简单图的度序列。
判断是否为图序列非负整数序列
(
d
1
,
d
2
,
.
.
.
,
d
v
)
(
d
1
≥
d
2
≥
.
.
.
≥
d
v
)
(d_1,d_2,...,d_v)(d_1 \geq d_2 \geq ... \geq d_v)
(d1,d2,...,dv)(d1≥d2≥...≥dv) 是图序列当且仅当
∑
i
=
1
v
d
i
\sum_{i=1}^v d_i
∑i=1vdi 是偶数并且对一切整数
k
(
1
≤
k
≤
v
−
1
k(1\leq k\leq v-1
k(1≤k≤v−1有
∑
i
=
1
k
≤
k
(
k
−
1
)
≤
∑
i
=
k
+
1
v
m
i
n
{
k
,
d
i
}
\sum_{i=1}^{k} \leq k(k-1) \leq \sum_{i=k+1}^{v}min \{k,d_i\}
∑i=1k≤k(k−1)≤∑i=k+1vmin{k,di}.
例题(1,2,2,4,5);(1,2,3,3,4,5);(1,2,3,4,4,5) 三个是否是图序列
思路第一个不是图序列当点数为
5
5
5 时不存在度为
5
5
5 的简单图。第二个是图序列。 第三个不是图序列先画出度为
5
5
5 的点的连边然后只有三个点还能连边需要的度依次为
2
,
3
,
3
2,3,3
2,3,3简单图中的三个点不可能连出度为
3
3
3 的连边情况。
同构若两个图顶点之间建立一一对应的关系且任意一对顶点的边数对应相同则称两图是同构的。
2.2 子图和连通分支
2.2.1 子图
子图设
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 为两个图。若
V
(
H
)
=
V
(
G
)
V(H) = V(G)
V(H)=V(G) 且
E
(
H
)
=
E
(
G
)
E(H) = E(G)
E(H)=E(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。
支撑(生成)子图若
V
(
H
)
=
V
(
G
)
V(H) = 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 的支撑子图或生成子图。
基础简单图对图
G
G
G 去除重边和环后的图
H
H
H。
2.2.2 导出子图
导出子图设 V ′ V' V′ 是 V ( G ) V(G) V(G) 的非空子集以 V ′ V' V′ 为顶点集以 E ′ = u v ∈ E ( G ) ∣ u , v ∈ V ′ E'= {uv \in E(G) | u,v \in V'} E′=uv∈E(G)∣u,v∈V′ 为边集的 G G G 的子图称为 G 的由 V ′ V' V′ 导出的子图记作 G [ V ′ ] G[V'] G[V′]简称为 G G G 的导出子图。
2.2.3 连通分支
途径的起点/终点/长度/逆转/衔接/节 W = v o e 1 v 1 e 2 . . . e k v k W=v_oe_1v_1e_2...e_kv_k W=voe1v1e2...ekvk这里 v i ∈ V ( 0 ≤ i ≤ k ) , e j = v j − 1 v j ∈ E ( 1 ≤ j ≤ k ) v_i\in V(0\leq i \leq k),e_j=v_{j-1}v_j \in E(1 \leq j \leq k) vi∈V(0≤i≤k),ej=vj−1vj∈E(1≤j≤k) v 0 v_0 v0 称为 W W W 的起点 v k v_k vk 称为 W W W 的终点之间的 v v v 称为 W W W 的内部点。 W W W 称为 G G G 的 ( v 0 , v k ) (v_0,v_k) (v0,vk) 途径。 k k k 为 W W W 的长度。逆转如字面意思。衔接意味对于两个不同的 W W W其中一条 W W W 的终点为另一个 W W W 的起点则两条 W W W 可以衔接。节是 W W W 序列中的子集。
迹途径
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 的连通分支数。
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |