综合建模：从证明到离散结构应用

前面的章节把离散数学拆成了许多部件：逻辑、量词、集合、关系、函数、证明方法、归纳、计数、图论。综合建模要做的是把这些部件重新装回一个完整问题里。

现实问题通常不会直接写着“请使用逆否证明”或“请建立冲突图”。它只会给出一段场景、一组约束和一个目标。我们要先判断对象是什么，关系是什么，目标能否写成命题，接着选择证明、计数或图论工具，最后检查模型是否真的回答了原问题。

---

综合建模的基本动作

一个离散建模过程可以分成六个动作。它们不一定严格线性进行；建模常常要反复修改，但第一次下手时，按这个顺序能减少混乱。

下面的工作台把同一套动作放进三个场景。切换案例时，注意右侧摘要怎样从对象、关系、目标命题一步步成形。

---

从问题翻译成对象、关系、命题

建模最容易出错的地方，是太早套方法。看到“排课”就立刻画图，看到“多少种”就立刻套组合公式，看到“算法”就立刻写程序，这些都可能跳过真正的问题。

更稳的做法是先写一张翻译表：

如果把课程集合记为 $C$，时段集合记为 $T$，一次排课可以看成函数

$$f:C\to T$$

若两门课程 $x,y$ 有冲突，就要求

$$xRy \Rightarrow f(x)\ne f(y)$$

这两行公式做了三件事：它说明对象是课程和时段，说明冲突是课程之间的关系，也说明“没有冲突”的目标可以写成一个全称条件。

---

案例：排课问题如何变成图着色

考虑一个小型排课问题：代数、程序、物理、写作、统计五门课要安排考试。若两门课有学生重叠，或同一位教师负责，就不能放在同一时段。这个场景的关键不是考试地点、试卷页数或课程名称本身，而是哪两门课彼此冲突。

把课程看成顶点，把冲突看成边，就得到一个图

$$G=(V,E)$$

其中 $V$ 是课程集合，$E$ 中的每条边表示“两端课程不能同一时段”。若用颜色表示时段，那么合法排课就是一种顶点着色：每条边的两个端点颜色不同。

这个模型给出一个清楚的命题：

若图 $G$ 存在 $k$ 种颜色的合法着色，则这些课程可以安排在 $k$ 个时段内且没有冲突。

这个证明也暴露了模型的边界。它只保证冲突课程不重叠，不保证教室容量足够，也不保证学生喜欢这个时间。若原问题还要求教室容量，就要加入新的对象和约束。

---

案例：网络连接与验证

网络问题适合用图建模，因为它天然关心“谁和谁相连”。站点可以是顶点，线路可以是边；一条从甲到己的路径表示信息、货物或人员可以沿着若干线路到达。

在这个模型里，问题可以有不同目标：

• 若问“甲能否到达己”，目标是证明存在一条路径。
• 若问“断掉某条线路后是否仍可到达”，目标是检查删边后的连通性。
• 若问“哪条线路最脆弱”，目标可能是寻找割边。
• 若问“最少经过几条线路”，目标变成最短路径问题。

例如，要证明甲到己有备用路径，不能只画一条漂亮路线。我们要明确写出路径上的顶点序列，并检查相邻顶点之间都有边。若备用路径为

$$\text{甲}\to \text{丙}\to \text{戊}\to \text{己}$$

就要分别检查 $\{\text{甲},\text{丙}\}$、$\{\text{丙},\text{戊}\}$、$\{\text{戊},\text{己}\}$ 都是图中的边。

---

案例：计数模型先问对象是什么

计数问题看起来像在套公式，其实第一步仍然是建模。我们要先说清楚“被数的对象”是什么，再判断对象是否能被拆成互斥情况、连续步骤、选择集合或排列序列。

看一个小例子：四场专题讲座甲、乙、丙、丁要放入上午、下午、晚上三个时段。允许多个讲座同一时段，但甲乙不能同一时段，丙丁也不能同一时段。问一共有多少种安排？

若暂时不考虑约束，每场讲座有 $3$ 个时段可选，所以共有

$$3^4=81$$

种函数式安排。现在减去违反约束的安排。设 $A$ 表示“甲乙同一时段”，$B$ 表示“丙丁同一时段”。若甲乙同一时段，先选这个共同时间有 $3$ 种，再给丙和丁各选一个时间，有 $3^2$ 种，所以 $|A|=27$。同理 $|B|=27$。若两个约束同时违反，甲乙共同选一个时段，丙丁共同选一个时段，共有 种。

用容斥原理得到合法安排数：

$$81-27-27+9=36$$

这个计算不只是代数。它背后有一个模型：一次安排是从讲座集合到时段集合的函数，两个约束定义了两个坏事件，容斥用来修正重复删除。

下面的交互把校园研讨会安排放在同一个场景里。切换目标时，模型会在冲突图、计数决策和算法验证之间改变，这能帮助你看见“同一现实场景不一定只有一个数学模型”。

---

算法正确性：把程序语句变成命题

算法正确性也是离散建模。输入、变量、循环轮次、递归调用都可以看成离散对象；程序每一步改变的是状态；正确性证明要说明这些状态变化不会破坏目标。

以“在有限列表中找最大值”为例。算法从第一个元素开始，把它记作当前最大值；随后逐个检查剩余元素，若发现更大的，就更新当前最大值。要证明它正确，核心不是说“看起来会更新”，而是写出循环不变式：

每轮循环结束后，当前最大值是已经检查过的元素中的最大值。

证明分三段。

这就是归纳思想在算法里的样子：初始化对应归纳基础，保持对应归纳步骤，终止把不变式翻译成最终结论。

---

选择证明路线

综合建模中，证明路线由命题形状决定。命题若直接展开定义就能推进，优先直接证明；结论是否定式时，逆否证明可能更自然；若假设相反会和已知条件冲突，可以考虑反证法；若命题含“对所有自然数 $n$”，归纳法通常要进入视野。

证明路线不是身份标签。同一个命题可能有多种证明。选择路线的目的，是降低推理难度，让定义、已知条件和结论之间的连接更短。

路线选择的几个信号

若命题形如“若 $P$，则 $Q$”，先试直接证明：从 $P$ 出发展开定义，看看能否到达 $Q$。若 $Q$ 难以直接得到，但 $\neg Q$ 很具体，可以改证逆否命题 $\neg Q\Rightarrow \neg P$。

若题目要求证明“不存在某对象”，常见路线是反证法：假设对象存在，再推出和定义、已知定理或最小性相冲突的结论。

若命题涉及所有自然数、递归结构、树的层数、算法轮次，可以考虑归纳法。归纳证明的关键不是写出“假设成立”，而是明确当前情形如何依赖前一个或更小情形。

若怀疑命题为假，不要硬写证明。先寻找反例。一个反例要同时满足命题的条件，并违反命题的结论。

---

把模型放回现实验证

数学证明说明“在模型假设下，结论成立”。但综合建模还要问：模型假设是否保留了原问题真正需要的东西？

排课模型若只包含课程冲突，就不能回答教室容量问题。网络模型若只记录线路是否存在，就不能回答带宽和延迟问题。计数模型若把讲座当成可区分对象，就不能直接用于“同主题讲座可互换”的场景。算法证明若只覆盖非空列表，就不能声称算法处理了空列表。

验证可以从四个方向进行：

• 对象检查：是否漏掉对象，是否把同一对象重复表示。
• 关系检查：关系是否记录了真正约束，方向性是否正确。
• 边界检查：空集、单元素、极端冲突、最大或最小输入是否处理。
• 结论检查：数学命题是否回答了原问题，而不是回答了一个更容易的问题。

---

章末综合练习

练习一：某学院要给四个项目组安排展示时段。项目组甲和乙有成员重叠，乙和丙有评委重叠，丙和丁使用同一设备。请把问题建模为图，并说明“两个时段是否足够”对应什么图论问题。

练习二：有 5 个不同任务要分配给 3 台服务器。每个任务必须分配给一台服务器，允许一台服务器接多个任务。若任务甲和乙不能在同一台服务器上，先建立计数模型，再求合法分配数。

练习三：命题“任意有 $n$ 个顶点的树都有 $n-1$ 条边”适合用什么证明路线？请说明理由。

---

全课复盘与继续学习

这门课从逻辑开始，是因为证明需要准确的句子。命题逻辑和谓词逻辑帮我们分清条件、结论、量词和否定。集合、关系和函数让我们有语言描述对象之间的结构。证明方法训练的是怎样从定义和假设走到结论。归纳和递归处理一步一步生成的对象。计数回答“有多少种可能”。图论处理连接、冲突、路径和分配。

综合建模把这些内容合在一起：先抽象对象和关系，再把目标写成命题，然后选择证明、计数或图论工具，最后回到原问题检查模型。

后续学习可以沿几条路继续走。若你喜欢“有多少种”的问题，可以进入组合数学，继续学习生成函数、递推和更复杂的双计数。若你喜欢网络、匹配、颜色和路径，可以进入图论。若你想证明程序为什么正确，可以继续学习算法设计与分析。若你关注随机选择和样本空间，离散概率会把计数结果转化为概率模型。若你准备学习抽象代数或实分析，本课程中的量词、集合、函数和证明习惯会继续发挥作用。