离散数学复习１.ppt

《离散数学复习１.ppt》由会员分享，可在线阅读，更多相关《离散数学复习１.ppt（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学复习 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 第四部分第四部分基本知识点基本知识点：简单图，子图，简单图，子图，Kn,n阶有向完全图，可图化，同构，路径，阶有向完全图，可图化，同构，路径，圈，连通图（强连通图，弱连通图），割点，桥，二部图，圈，连通图（强连通图，弱连通图），割点，桥，二部图，邻接矩阵，欧拉图、哈密顿图，无向树，最小生成树，根数，最优二叉树邻接矩阵，欧拉图、哈密顿图，无向树，最小生成树，根数，最优二叉树1、作出、作出K4的生成子图（非

2、同构）的生成子图（非同构）2、作出三阶有向完全图的生成子图（非同构）、作出三阶有向完全图的生成子图（非同构）3、作出满足一定条件的欧拉图、哈密顿图、作出满足一定条件的欧拉图、哈密顿图4、作出满足一定条件的无向树、最小生成树、最优、作出满足一定条件的无向树、最小生成树、最优2叉树叉树5、利用邻接矩阵求一有向图中两顶点之间的通路、回路数、利用邻接矩阵求一有向图中两顶点之间的通路、回路数二、判断题二、判断题、命题都是陈述句、命题都是陈述句 、命题公式包括矛盾式和可满足式两类、命题公式包括矛盾式和可满足式两类、命题是元谓词，、命题是元谓词，元谓词是命题元谓词是命题、命题公式等值就是同真值、命题公式等值

3、就是同真值、任一命题公式都存在唯一的两种范式、任一命题公式都存在唯一的两种范式、任一谓词公式都存在唯一的前束范式、任一谓词公式都存在唯一的前束范式、含、含n个命题变元的所有命题公式的主析取范式最多有有限种，个命题变元的所有命题公式的主析取范式最多有有限种，并且为并且为 、命题之间的等值关系是等价关系、命题之间的等值关系是等价关系(偏序关系偏序关系)10、任意一个命题公式的赋值不是成真赋值就是成假赋值、任意一个命题公式的赋值不是成真赋值就是成假赋值 11、真值表是表示命题公式的一种方式、真值表是表示命题公式的一种方式 12、任意一个命题公式的层数都为正整数、任意一个命题公式的层数都为正整数 13

4、、同一个命题公式可能既是析取范式又是合取范式、同一个命题公式可能既是析取范式又是合取范式 14、同一个命题公式可能既是主析取范式又是主合取范式、同一个命题公式可能既是主析取范式又是主合取范式（A=p）15、一个命题公式有唯一的极小项并且有唯一的极大项、一个命题公式有唯一的极小项并且有唯一的极大项 16、一个正确的推理其结论未必是真命题、一个正确的推理其结论未必是真命题 17、推理定律对应的公式都是永真式、推理定律对应的公式都是永真式 18、封闭的公式在一确定解释下，其真值是唯一的、封闭的公式在一确定解释下，其真值是唯一的 19、同一个命题符号化后的形式可能不唯一、同一个命题符号化后的形式可能不

5、唯一、集合是二元关系，二元关系是集合、集合是二元关系，二元关系是集合 、集合可以表示函数、集合可以表示函数 、二元关系是函数，函数是二元关系、二元关系是函数，函数是二元关系、非空集上一个关系可能既是自反关系又是反自反关系、非空集上一个关系可能既是自反关系又是反自反关系、一个关系可能既是对称关系又是反对称关系、一个关系可能既是对称关系又是反对称关系、一个关系可能既是等价关系又是偏序关系、一个关系可能既是等价关系又是偏序关系 1、图分为简单图和多重图、图分为简单图和多重图 2、欧拉、欧拉(哈密顿哈密顿)图都是连通图图都是连通图3、欧拉、欧拉 图都是哈密顿图图都是哈密顿图 4、哈密顿图都是欧拉、哈密

6、顿图都是欧拉 图图 5、半欧拉、半欧拉 图都是半哈密顿图图都是半哈密顿图 6、半哈密顿图都是半欧拉、半哈密顿图都是半欧拉 图图 7、任一个有限图都可以用矩阵、图形和集合表示、任一个有限图都可以用矩阵、图形和集合表示 8、图分为欧拉、图分为欧拉 图和半欧拉图和半欧拉 图图 9、图分为哈密顿图和半哈密顿图、图分为哈密顿图和半哈密顿图 10、树都是连通图、树都是连通图 11、任一棵树都是自己生成树、任一棵树都是自己生成树 12、任一连通图都有生成树、任一连通图都有生成树 13、含、含n个顶点，个顶点，n-1条边的图一定是生成树条边的图一定是生成树 14、一棵树的余树不一定是树、一棵树的余树不一定是树

7、 15、可图化的非负整数列在同构的意义下，非负整数列、可图化的非负整数列在同构的意义下，非负整数列与图不一定是一一对应的与图不一定是一一对应的 16、边带权的无向（连通）图一定有最小生成树、边带权的无向（连通）图一定有最小生成树 17、根树的顶点分为分支点和树叶、根树的顶点分为分支点和树叶 18、最优、最优2叉树一定是叉树一定是2叉正则树叉正则树 19、含、含t片树叶的最优片树叶的最优2叉树一定含有叉树一定含有t-1个分支点个分支点 20、含、含t片树叶并且树叶带权的片树叶并且树叶带权的2叉树一定存在最优叉树一定存在最优2叉树叉树 21、一欧拉图不一定是一半欧拉图。、一欧拉图不一定是一半欧拉图。（）22、在集合表达式中，关系运算优先于集合运算。、在集合表达式中，关系运算优先于集合运算。（）23、在图论中，平凡图是一棵树。、在图论中，平凡图是一棵树。（）24、连通图中顶点之间的可达关系是等价关系。、连通图中顶点之间的可达关系是等价关系。（）25、非空集上的偏序关系与集合的划分是一一对应、非空集上的偏序关系与集合的划分是一一对应.（）