一、图与网络的基本概念
- 生成子图:生成子图
G
’
G’
E
’
∈
E
E’∈E
E’∈E即可。
- 顶点集导出子图:
V
1
⊆
V
V1⊆V
V1⊆V,以
V
1
V1
V
V
V中的边为边集的
G
G
G的子图。
- 边集导出子图:
E
1
⊆
E
E1⊆E
E1⊆E,以
E
1
E1
E1为边集,
E
1
E1
E1的端点集为顶点集的图
G
G
G的子图。
- 简单图:既无环又无重边的图为简单图
- 完备图:任二顶点相邻的简单图,称为完备图,记为
K
- 二部图:一个图是偶图(二部图)当且当它不包含奇圈
- 握手定理:图
G
=
(
V
,
E
)
G= (V, E)
- 同构:顶点集之间存在一一对应关系,边也有一一对应的关系,则称图
G
G
G与
H
H
H同构,有向图的同构对应边的方向要相同。必要条件 (1) 顶点数相同(2) 边数相同(3) 关联边数相同的顶点个数相同。
二、树
- 树:无圈连通图称为树
- 树充要条件:
G
G
- 树充要条件:
G
G
G连通,且
(
G
)
=
V
(
G
)
−
1
e(G)=V(G)-1
e(G)=V(G)−1
- 树充要条件:
G
G
G连通,且对
G
G
G的任一边
e
,
G
−
e
e,G-e
e,G−e不连通
- 生成树:
G
G
三、连通性
- 点连通度:设
G
G
G连通,
V
⊂
V
(
G
)
,
G
[
V
−
V
]
V⊂V(G), G[V-V]
V⊂V(G),G[V−V]不连通,则称
V
V
V为
G
G
G
G
G的连通度记为
K
(
G
)
K(G)
K(G),若
G
G
G无点断集,则规定
K
(
G
)
=
−
1
K(G)=n-1
K(G)=n−1,
平凡图、不连通图
=
0
平凡图、不连通图=0
平凡图、不连通图=0
- 边连通度:设
G
G
G连通,
E
⊂
E
(
G
)
E⊂E(G)
E⊂E(G),
G
−
E
G-E
G−E(从
G
G
G中删除
E
E
E中的边)不连通,则称
E
E
E是
G
G
G
G
G的边连通度记为
K
‘
(
G
)
K‘(G)
K‘(G),当
∣
E
′
∣
=
1
|E’|=1
∣E′∣=1时,称E中的边
e
e
e为割边,
平凡图、不连通图
=
0
平凡图、不连通图=0
平凡图、不连通图=0
- k连通图:若一个图的连通度至少为
k连通的。于是,非平凡连通图均是
1
1
1连通的;图
G
G
G是2连通的当且仅当
G
G
G连通、无割点且至少含有
3
3
3个点。
- 点连通度、边连通度、最小度:
K
(
G
)
<
=
K
′
(
G
)
<
=
δ
(
G
)
K(G)<=K'(G)<=δ(G)
K(G)<=K′(G)<=δ(G)
- 割边:设e是图G的一条边,若
ω
(
G
−
e
)
>
ω
(
G
)
ω(G-e)>ω(G)
ω(G−e)>ω(G), 则称
e
e
e为
G
G
G的割边。
e
e
e是图
G
G
G的割边,当且仅当
e
e
e不在
G
G
G的任何圈中。
- 割点:
v是
G
G
G的割点当且仅当
V
(
G
−
v
)
V(G-v)
V
1
V_1
V1与
V
2
V_2
V2,使
∈
V
1
,
∈
V
2
(
,
)
- 割集:
[
S
,
S
′
]
[S, S’]
S
S
S,另一个端点在
S
S
S的全体边组成的集合,设
G
G
G连通,若
[
S
,
S
’
]
[S,S’]
[S,S’]只把
G
G
[
S
,
S
′
]
[S, S’]
[S,S′]为
G
G
G的一个割集。
- 树和图:设
v
v
v是树的顶点,则
v
v
v是
G
G
G的割点当且仅当度
(
v
)
>
=
2
e
=
(
u
,
v
)
e= (u, v)
e=(u,v) ,在
G
−
e
G-e
G−e中
u
u
习题16:反证法,
e
=
(
u
,
v
)
e= (u, v)
e=(u,v) ,
G
−
e
G-e
G−e中
u
u
u所在的分支
G
1
G_1
G1,
G
1
G_1
G1为二部图,因为二部图所有子图均为二部图,则
Σ
(
G
1
)
=
k
∣
X
1
∣
=
k
∣
Y
1
∣
−
1
=
>
k
Σ(G1)=k∣X1∣=k∣Y1∣−1=>k,
(
∣
X
1
∣
−
∣
Y
1
∣
)
=
1
(
k
>
=
2
)
(|X_1|-|Y_1|)=1(k>=2)
(∣X1∣−∣Y1∣)=1(k>=2),不成立
四、路径算法
五、匹配
- 边独立集(匹配):如果
M
M
M是图
G
G
G的边子集(不含环),且
M
M
M
M
M是
G
G
G的一个匹配
- 最大匹配:如果
M
M
M是图
G
G
M
M
M是
G
G
G
G
G的所有顶点,称它为
G
G
G的一个完美匹配(理想匹配)
- 二部图理想匹配:若
G
G
G是
k
(
k
>
0
)
k (k>0)
k(k>0)正则偶图,则
G
G
G存在完美匹配
- 贝尔热定理:
G
G
G的匹配
M
M
M是最大匹配,当且仅当
G
G
G不包含M可扩路
- Hall定理:二分图存在完美匹配当且仅当
∀
S
⊆
A
∀S⊆A,都有
∣
N
(
S
)
∣
⩾
∣
S
∣
∣N(S)∣⩾∣S∣
- 哥尼定理:在偶图中,最大匹配的边数等于最小覆盖的顶点数
- 托特定理:图
G
G
G有完美匹配当且仅当对V的任意非空真子集S, 有:
)
∣
(
G
−
S
)
∣
⩽
∣
S
∣
六、行遍性问题
- 欧拉巡回:经过
G
G
- 欧拉图:存在欧拉巡回的图称为欧拉图或E图
- 欧拉图的充要条件:连通、无奇度顶点
- 欧拉道路的充要条件:连通、最多只有两个奇度顶点
- 哈米尔顿路径:经过图
G
G
H
H
H路径。
- 哈米尔顿图:经过
G
G
H
H
H图。
- H图的必要条件:
其
∀
S
⊂
V
,
S
≠
∅
ω
(
G
−
S
)
≤
∣
S
∣
其 forall S subset V ,S neq varnothing \ omega ( G – S ) leq | S |
其∀S⊂V,S=∅ω(G−S)≤∣S∣
七、平面图
- 平面图:一个图若能在曲面
S
S
S
S
S上嵌人。可嵌入平面的图称为可嵌平面图,否则称为非平面图。可嵌平面图
G
G
G嵌人平面形成的图,称为
G
G
G的平面嵌入。
- 欧拉公式:设
G
=
(
n
,
)
G=(n, m)
G=(n,m)是连通平面图,
ϕ
ϕ是G的面数,
n
−
+
ϕ
=
2
n−m+ϕ=2
- 平面图推论:
G
G
G是
v
>
=
3
v>=3
v>=3的简单平面图,
ε
≤
3
v
−
6
ε≤3v−6,
δ
(
G
)
≤
5
δ(G)≤5
- 库拉托夫斯基定理:图
G
G
G是非可平面的,当且仅当它含有
K
5
K_5
K5或
K
3
,
3
K_{3,3}
K3,3细分的子图
原文地址:https://blog.csdn.net/qq_25601345/article/details/134725766
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_40916.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!