离散数学公式大全总结
离散数学是数学中的一个分支，涵盖了许多概念和公式。以下是一些离散数学中常见的公式和概念的总结：
1. 集合理论：
集合并：$A \cup B = {x | x \in A \text{或} x \in B}$
集合交：$A \cap B = {x | x \in A \text{且} x \in B}$
集合补：$A' = {x | x \notin A}$
集合差：$A - B = {x | x \in A \text{且} x \notin B}$
幂集：如果$A$有$n$个元素，$P(A)$有$2^n$个子集。
容斥原理：$|A \cup B| = |A| + |B| - |A \cap B|$
2. 排列和组合：
排列数：$P(n, k) = \frac{n!}{(n - k)!}$
组合数：$C(n, k) = \frac{n!}{k!(n - k)!}$
二项定理：$(a + b)^n = \sum_{k=0}^{n}C(n, k)a^{n-k}b^k$
3. 图论：
手握定理：$2 \cdot \text{边数} = \sum \text{度数}$
欧拉图：一个连通图是欧拉图，当且仅当每个顶点的度数都是偶数。
哈密顿图：包含图中每个顶点的圈。
图着：给定图中的顶点，用尽量少的颜对它们进行着，使得相邻的顶点颜不相同。
图的最短路径：Dijkstra算法和Floyd-Warshall算法用于到图中的最短路径。
4. 布尔代数：
布尔变量：$0$表示假，$1$表示真。
逻辑与：$A \land B$
二叉树公式
逻辑或：$A \lor B$
逻辑非：$\lnot A$
逻辑与门：$AND$
逻辑或门：$OR$
逻辑非门：$NOT$
布尔恒等定律：$A \land 1 = A$，$A \lor 0 = A$
德·摩根定律：$\lnot (A \land B) = \lnot A \lor \lnot B$，$\lnot (A \lor B) = \lnot A \land \lnot B$
5. 树和图：
树的顶点数与边数关系：$V = E + 1$
二叉树的性质：最多有$2^k$个叶子节点，高度为$h$的二叉树最多有$2^{h+1} - 1$个节点。
图的连通性：如果一个无向图有$n$个顶点，且每个顶点的度数至少为$k$，则这个图至少有$\frac{kn}{2}$条边。
这些是离散数学中的一些常见公式和概念，涵盖了集合论、排列和组合、图论、布尔代数、树和图等方面。离散数学在计算机科学、数学建模、逻辑推理等领域有广泛的应用。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。