离散数学考点总结

离散数学考点总结

1.选择题

1）欧拉图：每个顶点边数为偶数
2）补元：非最高最低，非相邻
3）真子集：除元素本身的子集
4）补图：完全图删除已有的边
5）幺元（单位元）：任何一个元素与之运算都是元素本身
6）零元：定义在集合S上的二元运算中的一个特殊元素θ，它既是左零元（对任意x∈S满足θx=θ），又是右零元（对任意x∈S满足x*θ=θ）
7）哈密顿图：指一个无向图中存在一条经过每个顶点恰好一次的路径的图
8）函数：满足x都有定义，且一个x对应一个y
9）集合的二元关系对称、反对称和反自反性质都能在差集操作保存，传递不行
10）集合的二元关系：

• 相容关系：自反+对称
• 等价关系：自反+对称+传递
• 偏序关系：自反+反对称+传递
• 拟序关系：反自反+传递
• 交集：自反、反自反、对称、反对称、传递都满足
• 并集：反对称、传递不满足
• 差集：自反、传递不满足
• $\cdot$：除了自反都不满足

2.填空题

1）连通图：所有面的边数之和=连通图边数的2倍，面数r+顶点数n=边数m+2
2）$R \cdot S$表示复合关系，即通过$$
3）完全图边数计算公式为$\frac {n(n-1)}{2}, 其中n为阶数$
4）并集的幺元是空集，零元是全集；交集的幺元是全集，零元是空集
5）树的度数=2倍的边，边=点-1
6）逆函数就是将$(x, y)$调换顺序为$(y, x)$
7）幂集就是所有子集
8）A到B集合的满射个数为$2^{A集合的元素个数} - B集合的元素个数$

3.计算题

1）真值表
2）等值演算
3）关系图和关系矩阵
重点
-自反闭包的主对角线为1

4）最小生成树和计算权
重点
-权值从小到大，不能成环，直至所有点有线连接

5）图的邻接矩阵、通路、回路
6）二叉树的先序、中序、后序遍历
7）集合关系的哈斯图、极大元、极小元、最大元、最小元

4.证明题

1）证明构成交换群
解题思路

• 满足封闭性
• 满足结合律
• 存在幺元
• 每个元素存在逆元
• 满足交换律

2）CP规则证明有效推理
3）图的证明