📕 离散数学 · 定理库
15 个定理 · 来自 Rosen《离散数学及其应用》第8版
📊 15 个定理
📐 5 个主题领域
📖 数论 · 图论 · 集合论 · 可计算性
🔢 数论
算术基本定理
每个大于1的整数可唯一分解为素数之积（不计顺序）
费马小定理
若 p 为素数且 gcd(a,p)=1，则 a^(p-1) ≡ 1 (mod p)
素数定理
不超过 x 的素数个数 π(x) ~ x / ln x，素数分布渐近规律
Lamé 定理
欧几里得算法的除法次数不超过较小数的十进制位数的5倍
📊 集合论与基数
Cantor 定理
任意集合的幂集基数严格大于原集合基数 |P(A)| > |A|
Schröder-Bernstein 定理
若 |A| ≤ |B| 且 |B| ≤ |A|，则 |A| = |B|，证明基数等价
🕸️ 图论
握手定理
无向图中所有顶点度数之和等于边数的两倍 Σ deg(v) = 2|E|
欧拉公式
连通平面图满足 V - E + F = 2（顶点-边+面=2）
Kuratowski 定理
图是平面图当且仅当不含 K₅ 或 K₃,₃ 的细分
Dirac 定理
n≥3 的简单图中若每个顶点度数 ≥ n/2，则存在哈密顿回路
Ore 定理
n≥3 的简单图中若任意不相邻顶点 u,v 满足 deg(u)+deg(v)≥n，则有哈密顿回路
Erdős-Szekeres 定理
任意 (r-1)(s-1)+1 个不同实数序列必含长度为 r 的递增或长度为 s 的递减子序列
Vizing 定理
简单图的边着色数 Δ 或 Δ+1（Δ 为最大度数）