“离散数学”复习要点.pdfVIP

“离散数学”复习要点 一．集合与关系 1. 集合的运算（交、并、差、补、对称差） 2. 集合的笛卡儿积，二元关系、关系的定义域、值域，关系矩阵（布尔积），关系图。 3. 关系的逆、关系的合成，关系的性质（五种特性）及其判别（关系法、矩阵法、图法）。 4. 关系的闭包的求法，等价关系的定义（等价类与商集、集合的划分），序关系（偏序、拟序）定义。 二．图论 1. 图的有关概念：结点、边（有向边、无向边），图的阶，有向图、无向图，基础图，加权图，多重图与简 d (v) d  (v) d  (v) d n 单图，结点的度数 （出度 与入度 ）， 度正则图、 阶完全图。 2. 子图和图的运算：子图、真子图、生成子图、导出子图；图的并、交、环和。 3. 路径、回路和连通性：路径（闭路径与开路径、简单路径与回路、基本路径与基本回路），路径的长度， 结点到结点的距离，路径的加权长度与加权距离 （求最短路径）。 连通性（连通图，单向连通图，强连通图，弱连通图）。 4. 图的矩阵表示：邻接矩阵，可达性矩阵；图的矩阵与图的连通性。 5. 欧拉图和哈密顿图：欧拉路径、欧拉回路的定义，欧拉路径、欧拉回路的充分必要条件；哈密顿路径、哈 密顿回路的定义，哈密顿图的充分条件；最邻近法求权为最小的哈密顿回路。 6. 树、有向树和有序树 ：树 （树叶、分枝点、森林 ），生成树 （枝、弦）求最小生成树 ； 有向树，根树 （概、树叶、分枝点，儿子、兄弟、父亲、袓辈、子孙，层数、高 ）； m m 有序树 （ 元树，完全 元有序树 ），二叉树，求最优二叉树 。