没有合适的资源?快使用搜索试试~ 我知道了~
首页图论复习资料:匹配与因子分解详解
图论复习资料:匹配与因子分解详解
需积分: 9 2 下载量 137 浏览量
更新于2024-07-09
收藏 2.42MB PDF 举报
《图论及其应用》期末复习资料是由基础与前沿研究院的谭兵整理自电子科技大学王也洲老师的课堂PPT和作业习题,主要用于研究生课程的期末复习。主要内容包括: 1. 图的基本概念: - 图被定义为由顶点和边组成,非同构简单图的分析,如点数(n)和边数(m)的关系,以及自补图、连通图等的概念。 - 图的度数和特征值,如每个顶点的度数,以及矩阵aij与图结构的关系,如最大特征值与完全偶图的关系。 2. 树的性质: - 阶数为2、3、6的非同构树的数量,以及欧拉公式的应用,指出简单平面图的边数与顶点数的关系。 - 可以由k棵树组成的森林满足的条件,如欧拉特征与树的数量关系。 3. 平面图与森林: - 欧拉公式扩展到平面图,说明简单平面图的性质,如可平面图的边数限制和至少需要的点数。 - 极大平面图的概念,连通性和边的性质,例如极大平面图必定是连通的,并且与K5或K3,3不同构。 4. 匹配与因子分解: - 完美匹配和因子分解的概念,以及正则图中完美匹配的存在性条件,如无割边的正则图可能不存在因子分解。 - Hall定理的阐述,即在一个图中,如果对于任意集合S,|N(S)|(S的邻接顶点数量)大于等于|S|,那么存在完美匹配。 5. 特殊图的性质: - 奇数阶图和因子分解的限制,以及连通图的可因子化条件。 - 具有H圈的正则图的可因子化特性,以及对连通图的无环性质的讨论。 复习资料强调了做题时的细心和时间管理,因为错误往往源于已知的知识,祝愿学生考试取得好成绩。这份资料不仅是课堂学习的补充,还提示了更多知识来源于课堂外的学习和实践。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/19201439/bga.jpg)
3.2 块及其性质
没有割点的连通图称为块图,简称块.
1. 仅有一条边的块,要么是割边,要么是环;
2. 仅有一个点的块,要么是孤立点,要么是环;
3. 至少有两个点的块无环;
4. 至少有三个点的块无割边,无自环.
Example 13. 图 G 如图 (a) 所示,G 的所有块如图 (b) 所示.
Theorem 20. 设图 G 的阶至少为 3,则 G 是块当且仅当G 无环并且任意两点都位于同一个
圈上.
Theorem 21. 设图 G 的阶至少为 3,则 G 是块当且仅当G 无孤立点且任意两边都位于同一
个圈上.
Theorem 22. 点 v 是图 G 的割点当且仅当 v 至少属于 G 的两个不同的块.
注:两个不同块的公共顶点只能是割点,即块与块只能由割点相联结,因此可以通过割
点搜寻块.
注:(k ≥ 3) 块没有割边,块有圈.
图 6: 它的块的数目是 4.
3.3 连通度
点连通度可描述为“使图不连通或成为平凡图,最少需要删去的点数”.
(1)κ (K
n
) = n − 1, (2)κ (C
n
) = 2� 其中C
n
为n圈, n ≥ 3.
Theorem 23. 若一个图的连通度至少为 k,则称该图是 k 连通的.
10
![](https://csdnimg.cn/release/download_crawler_static/19201439/bgb.jpg)
注:k 连通:要想破坏连通性,至少要删去 k 个点.
注:K
2
连通、无割点,但连通度为 1.
边连通度可描述为“使图不连通或成为平凡图,最少需要删去的边数”.
(1)λ (K
n
) = n − 1, (2)λ (C
n
) = 2� 其中C
n
为n圈, n ≥ 2.
Theorem 24. 若一个图的边连通度至少为 k,则称该图是 k 边连通的.
注:k 边连通:要想破坏连通性,至少要删去 k 条边.
注:k 连通一定是 k 边连通的.
Theorem 25. 对任意的图 G,有
κ(G) ≤ λ(G) ≤ δ(G)
Theorem 26. 设 G 是具有 m 条边的 n 阶连通图,则
κ(G) ≤ ⌊2m/n⌋.
Example 14. n 阶 k 连通图至少 ⌈kn/2⌉ 有条边.
图 G 的顶点数为 n 且 7 连通,则其边数至少为 ⌈7n/2⌉.
Lemma 1. 设 G 是 n 阶简单图,若 δ(G) ≥ ⌊n/2⌋,则 G 必连通,且 λ(G) = δ(G).
证明. 若 G 不连通,则 G 至少有两个连通分支,从而必有一个分支 H 满足 |V (H)| ≤ ⌊n/2⌋.
因 G 是简单图,从而
∆(H) ≤ ⌊n/2⌋ − 1 < ⌊n/2⌋
于是
δ(G) ≤ δ(H) ≤ ∆(H) < ⌊n/2⌋
这与已知矛盾,所以 G 必连通.
Menger 定理是图的连通性问题的核心定理之一,它揭示了图的连通度与不同顶点对间的
不相交路的数目之间的关系.
Theorem 27. 1. 设 x 和 y 是图 G 中的两个不相邻点,则 G 中分离 x 和 y 的最少点数
等于独立的 (x, y) 路的最大数目.
2. 设 x 和 y 是图 G 中的两个不同点,则 G 中分离 x 和 y 的最少边数等于边不重的 (x, y)
路的最大数目.
11
![](https://csdnimg.cn/release/download_crawler_static/19201439/bgc.jpg)
在该图中,独立的 (u, v) 路的最大条数是 2,分离点 u 与 v 的最小点集是 {u
1
, u
2
},包含
2 个顶点.
在该图中,边不重的 (u, v) 路的最大条数是 3,分离点 u 与 v 的最小边集是 u
1
v, u
2
v, u
2
u
3
,
包含 3 条边.
Theorem 28 (Menger 定理). 1. 一个非平凡图 G 是 k(k ≥ 2) 连通的当且仅当 G 的任意
两个不同顶点间至少存在 k 条独立的路;
2. 一个非平凡图 G 是 k (k ≥ 2) 边连通的当且仅当 G 的任意两个不同顶点间至少存在 k
条边不重的路.
注:由“任意两个不相邻的顶点之间存在 k 条独立的路”必能推出“任意两个相邻的顶
点之间也存在 k 条独立的路”.
3.4 图的宽距离和宽直径 (不做要求)
4 Euler 图与 Hamilton 图
4.1 欧拉图
Definition 8. 经过 G 的每条边的 (闭) 迹被称为 Euler (闭) 迹,存在 Euler 闭迹的图称为
Euler 图,简称 E 图.Euler 闭迹又称为 Euler 回路.
Theorem 29. 假定 G 是一个连通图,则下列命题等价:
1. G 是欧拉图.
2. G 的每个点的度是偶数.
3. G 的边集能划分为边不重的圈的并.
Lemma 2. 连通图 G 有 Euler 迹当且仅当 G 最多有两个奇点.
注:
1. 图 G 有欧拉迹当且仅当 G 能“一笔画”.
2. 若奇度点数为零,则一笔画与起点无关;若奇度点数为
2
,则一笔画的起点与终点均为
奇点.
Theorem 30. 下列陈述对于一个连通有向图 D 是等价的:
1. D 是欧拉有向图;
2. D 的每个点的入度等于出度;
3. D 的弧集可划分为边不重的有向圈的并.
Euler 图没有割边,有可能有割点(八字形的图).
12
剩余56页未读,继续阅读
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
chenruize123
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)