【免费】正确版离散数学II第7-9章重难点总结1资源-CSDN文库

需积分: 0 67 浏览量 2022-08-08 18:25:44 上传评论收藏 16KB DOCX 举报

资源详情

资源评论

资源推荐

离散数学 II 第 7-9 章重难点概要

第 7 章图

7.1 零图，基图，标定图，关联，相邻，关联集，邻域，点 v 的度数，出度，入度，孤立点，

G 的最大（小）度，握手定理（有向图和无向图），度数列，可简单图化的判断及画图，

图的同构定义，必要条件；简单图，平凡图，竞赛图，k-正则图，n 阶无向完全图 Kn，n

阶有向完全图，彼得森图，二部图（偶图，不含有奇圈），完全二部图，二部图的充要条

件，子图，生成子图，，同构定义及必要条件，自补图，图的运算（边的收缩，加新边，

G1∪G2，G1∩G2，G1-G2，环和 G1⊕G2，

7.2 通路，回路，路径，圈，周长，围长，直径，扩大路径法（证明圈的存在），

7.3 连通图，不连通图，连通分支，连通分支数 p(G),

7.4 点连通度，最小点割集 V’，边连通度，最小边割集 E’，断集 E’’, p(G-V’)>=2, p(G-E’)=2, p(G-

E’’)>=2, 扇形割集, Whitney 定理，Th7.14，不含割点（2-连通）的无向图的充要条件，不

含割边（2-边连通）的图的充要条件，块，含有割点的图的充要条件，含割边的图的充

要条件，

7.5 可达，短程线，弱连通，单向连通，强连通

第 8 章欧拉图和哈密顿图

8.1（半）欧拉图：定义（必须是连通图）；充要条件（通过度数，或圈）；如何将非（半）

欧拉图通过添边的方式改成（半）欧拉图；列出欧拉图的欧拉回路；欧拉图与中国邮递

员问题的联系；轮盘设计中的欧拉图。欧拉图中的圈，欧拉回路与连通度，连通性的联

系；

8.2（半）哈密顿图：定义（必须是连通图）；充分条件，必要条件；棋盘走马，旅行商问题。

第 9 章树

9.1 无向树的 6 个等价定义的内容；树的边数和点数的关系 m=n-1；树中不相邻结点间添加

任意一条新边，均产生一个唯一的圈；非平凡树至少含有两片树叶；星形图；

9.2 生成树与连通图的联系，树枝，余树，弦，n 阶连通图的边数 m>=n-1, 其生成树含 n-1

条边，余树的边（弦）m-n+1 条；基本回路，基本回路系统；基本割集，基本割集系统；

连通图中所有不同的生成树，不同生成树的个数计算；

9.3-9.4 环路，环路空间；断集，断集空间；

9.5 有向树，根树，数额，分支点，层高，树高，r 叉完全正则有序树，根树的前（中，后）

序遍历，Huffman 编码，平均码字长度；

注意:

（1）用图论的语言描述问题和解决问题，

（2）建模过程中，G=<V,E>，V 的定义，E 的定义，是否有（无）向图，简单图，二部图。

（3）学习中总结图论的实际应用，和重要算法。

（4）若证明某个点不是割点，可以通过证明该点在回路上（如欧拉回路，哈密顿回路，圈

等），或者证明该点是生成树的树叶（不是生成树的分支点）

（5）证明某边不是割边，可通过证明该边在回路上，或不是该连通图生成树的树枝。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载

评论0

内容反馈

丽龙

粉丝: 25
资源: 332

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip