📚 IB HL Option 10 Discrete Mathematics Review | IB 高阶数学选项10 离散数学复习
Discrete mathematics forms the backbone of theoretical computer science and modern cryptography, and it provides powerful tools for solving counting problems, network optimisation, and logical reasoning. In the IB Higher Level Mathematics Option 10, students explore a rich blend of combinatorics, graph theory, algorithms, recurrence relations, number theory and fundamental relations. This article revisits the essential concepts from the Cambridge 2012 textbook by Fannon, Kadelburg, Woolley and Ward, offering clear explanations, helpful comparisons and worked-style insights to reinforce your understanding ahead of the examination.
离散数学是理论计算机科学和现代密码学的重要支柱，它为解决计数问题、网络优化和逻辑推理提供了强有力的工具。在 IB 高阶数学选项 10 中，学生将深入学习组合学、图论、算法、递推关系、数论以及基本关系。本文回顾 Fannon、Kadelburg、Woolley 和 Ward 编写的 Cambridge 2012 版教材中的核心知识点，通过清晰的解释、对比表格和解题风格的剖析，帮助你在考前巩固理解、查漏补缺。
1. Counting Principles and the Binomial Theorem | 计数原理与二项式定理
Counting problems are solved using three fundamental ideas: the multiplication principle, permutations and combinations. When selections are ordered, the number of ways to arrange r objects from n distinct objects is P(n, r) = n!/(n−r)!. If order does not matter, the number of combinations is C(n, r) = n!/(r!(n−r)!). The binomial theorem then compacts these ideas: (a+b)n = Σk=0n C(n,k) an−k bk. Notice that the coefficient of an−kbk is exactly the number of ways to choose the k positions for b.
计数问题依靠三个基本原理解决：乘法原理、排列和组合。如果选取的对象有顺序，从 n 个不同元素中取出 r 个进行排列的方法数为 P(n, r) = n!/(n−r)!；若顺序无关，组合数为 C(n, r) = n!/(r!(n−r)!)。二项式定理则将这些思想浓缩为：(a+b)n = Σk=0n C(n,k) an−k bk。请注意，an−kbk 的系数恰好是选出 k 个位置放置 b 的组合数。
2. Inclusion–Exclusion and Pigeonhole Principle | 容斥原理与鸽巢原理
When sets overlap, the inclusion–exclusion principle gives the number of elements in the union. For two sets, |A ∪ B| = |A| + |B| − |A ∩ B|; for three sets, the formula extends to |A ∪ B ∪ C| = Σ|sets| − Σ|pairs| + |A ∩ B ∩ C|. The pigeonhole principle, though simple, is surprisingly powerful: if n items are placed into m boxes and n > m, at least one box must contain more than one item. This idea can prove the existence of certain configurations without constructing them explicitly.
当集合之间有重叠时，容斥原理给出了并集中元素的个数。两个集合时，|A ∪ B| = |A| + |B| − |A ∩ B|；三个集合的公式扩展为 |A ∪ B ∪ C| = Σ|各集合| − Σ|两两交集| + |A ∩ B ∩ C|。鸽巢原理虽简单，却出奇强大：如果把 n 件物品放入 m 个盒子，且 n > m，则至少有一个盒子装有多于一件物品。这个原理常用于证明某些结构的存在性，而不必显式构造出来。
3. Introduction to Graph Theory | 图论基础
A graph consists of vertices (nodes) and edges connecting them. The degree of a vertex is the number of edges incident with it; a loop counts twice. Two graphs are isomorphic if there is a one-to-one correspondence between their vertices that preserves adjacency. Important families include complete graphs Kn, cycle graphs Cn r graphs states v − e + f = 2, where v, e, f are the numbers of vertices, edges and faces.
图由顶点（节点）和连接它们的边组成。顶点的度是指与该顶点相连的边数；自环按两条边计算。如果两个图的顶点之间存在一一对应，并且保持了邻接关系，则它们同构。重要的图族包括完全图 Kn、环图 Cn 和二分图。平面图是指能在平面上画出且边不相交的图。对于连通的平面图，欧拉关系式为 v − e + f = 2，其中 v、e、f 分别是顶点数、边数和面的数目。
4. Trees and Their Properties | 树及其性质
A tree is a connected graph with no cycles. Equivalently, a tree on n vertices has exactly n − 1 edges, and adding any new edge creates a cycle. Rooted trees allow parent–child relationships and are used to model hierarchical data. Spanning trees of a connected graph include all vertices but only some of the edges; counting them can be achieved via Kirchhoff’s matrix-tree theorem. The minimum connector problem then asks for a spanning tree of least total weight in a weighted graph.
树是无环的连通图。等价地说，有 n 个顶点的树恰好有 n − 1 条边，并且任意添加一条边都会形成环。有根树引入了父子关系，用于模拟层次化数据。连通图的生成树包含了所有顶点，但只选用部分边；其数目可以通过基尔霍夫矩阵‑树定理计算。最小连接问题则要求在加权图中寻找总权值最小的生成树。
5. Minimum Spanning Trees: Kruskal and Prim | 最小生成树：Kruskal 与 Prim 算法
Kruskal’s algorithm builds a minimum spanning tree by sorting all edges by weight and adding the cheapest edge that does not create a cycle, repeating until the tree has (v − 1) edges. Prim’s algorithm starts from an arbitrary vertex and repeatedly adds the cheapest edge connecting a visited vertex to an unvisited one. Both guarantee an optimal solution, but their implementation differs: Kruskal needs a union-find structure to test for cycles, while Prim maintains a priority queue of frontier edges.
Kruskal 算法先将所有边按权重排序，然后依次添加不会形成环的最小权边，直到树中含有 (v − 1) 条边。Prim 算法从任意一个顶点出发，反复贪心地选取连接已访问顶点和未访问顶点的最轻边。两者都能保证最优解，但实现方式不同：Kruskal 依赖于并查集来检测环，而 Prim 则维护一个前沿边的优先队列。
6. Shortest Path: Dijkstra's Algorithm | 最短路径：Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a source vertex to all others in a graph with non‑negative edge weights. It maintains a set of permanently labelled vertices and a set of temporary distances. At each step, the vertex with the smallest temporary distance is made permanent, and its neighbours are updated. This process resembles a wavefront propagating through the network. The algorithm can be recorded in a table showing the order of labelling and the final shortest‑path tree.
Dijkstra 算法在边权非负的图中，找出从源顶点到所有其他顶点的最短路径。它维护一个永久标号顶点的集合以及临时距离的集合。每一步，选取临时距离最小的顶点并将其标为永久，然后更新其邻居的距离。这一过程类似于波前在网络中传播。算法执行过程可通过表格记录永久标号的顺序和最终的最短路径树。
7. Chinese Postman Problem | 中国邮递员问题
The Chinese postman problem asks for the shortest closed walk that traverses every edge of a graph at least once and returns to the start. In a Eulerian graph (all vertices have even degree), an Eulerian circuit is the optimal route and can be found using Fleury’s algorithm. When odd‑degree vertices exist, they must be paired by extra journeys to make the graph Eulerian. The task reduces to finding a minimum‑weight perfect matching on the odd vertices after computing shortest distances between them.
中国邮递员问题要求找出经过图中每条边至少一次并回到起点的最短闭合路径。在欧拉图（所有顶点的度均为偶数）中，欧拉回路就是最优路线，可通过 Fleury 算法求得。当存在奇度顶点时，必须通过添加重复边将其配对，使图变成欧拉图。问题转化为：先计算奇度顶点间的最短距离，再寻找这些顶点上的最小权重完美匹配。
8. Recurrence Relations | 递推关系
A linear homogeneous recurrence of order k has the form un = a1un−1 + a2un−2 + … + akun−k. Its characteristic equation is rk − a1rk−1 − … − ak = 0. If the roots r1, r2 are distinct, the general solution is un = A·r1n + B·r2n. Repeated roots introduce polynomial factors: for a double root r, the term becomes (A + Bn)rn. Non‑homogeneous recurrences are solved by adding a particular solution, often guessed from the form of the non‑homogeneous term.
k 阶线性齐次递推关系形如 un = a1un−1 + a2un−2 + … + akun−k。其特征方程为 rk − a1rk−1 − … − ak = 0。若特征根 r1、r2 互异，通解为 un = A·r1n + B·r2n。当有重根时，解中需引入多项式因子：对于二重根 r，对应的项为 (A + Bn)rn。非齐次递推关系可通过添加一个特解来解决，特解的形式通常由非齐次项的结构猜测得出。
9. Number Theory and Modular Arithmetic | 数论与模运算
Working modulo m means that two integers are congruent if their difference is a multiple of m: a ≡ b (mod m). Linear congruences a·x ≡ b (mod m) have solutions precisely when gcd(a,m) divides b. The extended Euclidean algorithm finds inverses a−1 modulo m when they exist. Fermat’s little theorem states that if p is prime and p ∤ a, then ap−1 ≡ 1 (mod p), a result that underpins the security of RSA. Euler’s totient function φ(n) generalises this to composite moduli: aφ(n) ≡ 1 (mod n) when gcd(a,n)=1.
模 m 运算意味着两个整数之差如果是 m 的倍数，则它们同余：a ≡ b (mod m)。线性同余式 a·x ≡ b (mod m) 有解当且仅当 gcd(a,m) 整除 b。扩展欧几里得算法可在 a 存在模 m 的逆元时找出 a−1。费马小定理指出：若 p 为素数且 p ∤ a，则 ap−1 ≡ 1 (mod p)，该结果是 RSA 安全性的基石。欧拉函数 φ(n) 将此结论推广到合数模：当 gcd(a,n)=1 时，有 aφ(n) ≡ 1 (mod n)。
10. RSA Encryption | RSA 加密
) = (p−1)(q−1). Choose an encryption exponent e coprime to φ(n), and find d satisfying e·d ≡ d φ(n)). The public key is (n, e); the private key is d. A message M is encrypted as C = Me mod n, and decryption uses M = Cd mod n. The security relies on the difficulty of factoring n to recover p and q, thus protecting the private key.
RSA 是一种公钥密码体制，使用两个大素数 p 和 q。计算 n = p·q 以及 φ(n) = (p−1)(q−1)。选取与 φ(n) 互质的加密指数 e，再求出满足 e·d ≡ 1 (mod φ(n)) 的解密指数 d。公开密钥为 (n, e)，私钥为 d。消息 M 加密为 C = Me mod n，解密则通过 M = Cd mod n 恢复。其安全性依赖于分解 n 以恢复 p、q 的困难性，从而保护私钥。
11. Equivalence Relations and Partial Orders | 等价关系与偏序
A relation R on a set is an equivalence relation if it is reflexive, symmetric and transitive. Equivalence relations partition the set into disjoint equivalence classes. A partial order is a relation that is reflexive, antisymmetric and transitive, represented concisely by a Hasse diagram. In a Hasse diagram, loops and implied transitive edges are omitted, and smaller elements are placed lower. Special elements such as maximal, minimal, greatest and least can be identified from the diagram; lattices arise when every pair of elements has both a least upper bound and a greatest lower bound.
集合上的关系 R 若满足自反性、对称性和传递性，则称为等价关系。等价关系将集合划分为互不相交的等价类。偏序是自反、反对称且传递的关系，通常用哈斯图简洁地表示。哈斯图中省略了自环和由传递性隐含的边，并将较小的元素放在下方。从图中可以识别极大元、极小元、最大元和最小元；当每一对元素既有最小上界又有最大下界时，该偏序构成一个格。
12. Proof by Induction | 归纳法证明
. Strong induction assumes the statement holds for all values up to k, which is particularly useful when the formula depends on earlier terms, as in many recurrence proofs. Writing a clear, step‑by‑step inductive proof is a core skill examined throughout the discrete mathematics option.
数学归纳法是证明关于自然数命题的基本工具。奠基步骤验证 n = 1（或其他起始值）时命题成立；归纳步骤则假设 n = k 时命题成立，并利用该假设证明 n = k+1 时命题也成立。强归纳法假设命题对所有不大于 k 的值都成立，这在公式依赖于前面多个项时格外有用，例如许多递推关系的证明。写出清晰、逻辑严密的归纳证明，是在整个离散数学选项考试中反复考查的核心能力。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图