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

学到这里，我们已经会写真值表、会处理集合和函数，也见过归纳、计数、树、着色与连通性。可一旦题目换成“怎么排考试”“怎么铺网络”“怎么证明程序不会出错”，很多人还是会愣一下：这些现实问题并没有在句尾提醒你“请使用图论”。

这正是综合建模真正难的地方。难点通常不在最后那几行计算，而在前面几步：哪些东西需要区分，哪些关系必须保留，目标究竟是存在性命题、全称命题，还是一个计数问题？如果这几步翻译错了，后面的证明越漂亮，离原问题反而越远。

这一章不再把知识点分开复述。我们会让三个案例从头走到尾：考试排程、园区网络和流式去重。每个案例都按同一条路线推进：

先把“问题”改写成能判断真假的句子

现实语言很喜欢使用“合理”“可靠”“尽量少”“不会出错”这些词。它们能表达愿望，却还不是数学命题。比如“这张课表很合理”到底是说没有学生撞考，还是说考试天数少，或者是说每个学生每天最多考一门？三种解释会得到三个不同模型。

第一次建模时，我建议先写一张五栏草稿。它不需要漂亮，但每一栏都必须能被检查。

这里有个很实用的判断：如果一句话还不能明确判真或判假，它通常还不是可证明的目标。“网络可靠”不是命题；“删除任意一条边后，任意两个站点之间仍存在路径”才是。

量词决定你要交出什么证据

四种常见问法，对应四种完全不同的任务。

“我找到了一个三时段排法”只能证明三时段足够，不能证明三时段最少。要证明最少，还得说明两时段为什么不可能。建模时把这两个方向拆开，证明会清楚很多。

下面的工作台可以切换排课、网络和算法场景。你可以故意选择一个较弱的对象或证明方案，看看右侧的模型为什么失去说服力。

考试排程：从冲突关系走到可数的着色

先看一个小型但完整的排程问题。现在有六门考试：逻辑、集合、归纳、计数、图论、算法。已知下列课程对有学生重叠，不能安排在同一时段：

我们想回答两个问题：两个时段够不够？如果有 $k$ 个带标签的可用时段，一共有多少张合法课表？

对象：课程集合、时段集合和冲突关系

把六门课程组成的集合记为 $V$，把 $k$ 个时段组成的集合记为

一次完整排程必须给每门课程恰好一个时段，所以它是一个全函数

冲突是课程之间的对称关系：若逻辑与集合冲突，那么集合与逻辑也冲突；一门课程不会和自己形成这里所说的课程对。于是这个关系可以用简单无向图 $G=(V,E)$ 表示。

这一步已经删掉了很多现实细节。课程名称只负责区分顶点，试卷页数和授课周数没有进入模型；学生重叠则必须保留，因为它正是“不能同场”的来源。

定义：合法课表就是正常着色

函数 $c$ 是合法课表，当且仅当每条冲突边的两个端点被分到不同时段：

这恰好是正常顶点着色的定义。颜色不需要真的是红黄蓝；颜色只是时段标签。

于是“用 $k$ 个时段排完考试”与“图 $G$ 可以用至多 $k$ 种颜色正常着色”不只是长得相似。它们是同一组函数满足同一组约束。

猜想：两个时段足够，而且合法排法可以精确计数

这张冲突图连通且没有环，所以它是一棵树。我们准备证明两个结论。

第一，任意至少有两个顶点的树都可以用两种颜色正常着色，因此这个实例只要两个时段。

第二，对任意 $n\ge 1$ 和 $k\ge 2$，一棵有 $n$ 个顶点的树使用 $k$ 个带标签颜色的正常着色数为

代入 $n=6$、$k=3$，三时段合法课表数是

这时先别急着庆祝。我们还欠两笔账：树为什么一定二着色，计数公式为什么没有重复也没有遗漏。

证明：先用唯一路径构造二着色

任选一个根顶点 $r$。树是连通图，所以每个顶点 $v$ 都能从 $r$ 到达；树又没有环，所以 $r$ 到 $v$ 的简单路径唯一。令 $d(r,v)$ 表示这条路径的长度，并按长度奇偶给顶点分色：

若相邻顶点 $u,v$ 得到了同一种颜色，那么 $d(r,u)$ 与 $d(r,v)$ 同奇偶。把从根到这两个顶点的唯一路径与边 $\{u,v\}$ 放在一起，就会形成一个环；这和树无环矛盾。于是每条边两端颜色不同，构造确实给出了合法的两时段课表。

这个证明也告诉我们方案是怎么想到的：树没有环，沿根向外走时，每经过一条边就切换一次颜色，不会出现“绕一圈回来却要求自己换色”的麻烦。

证明：删掉叶子，再把它接回来

接着证明着色数公式。这里最自然的归纳参数是顶点数，而不是颜色数。

注意最后那句“删掉 $x$ 后只会回到一个小树着色”。它说明我们计数的对应关系是可逆的。如果只写“先给小树着色，再给叶子选颜色”，却不解释每张大课表是否恰好被数一次，乘法就还缺逻辑支撑。

边界检查：公式在哪些地方会失效

这个模型有几条很清楚的边界。

• 若后来发现计数、图论和算法三门课两两冲突，图中会出现三角形。三角形不能二着色，原来的“两时段足够”立即失效。
• 公式 $k(k-1)^{n-1}$ 只对树成立。给树多加一条边，新增约束可能排除一部分着色，不能继续照抄公式。
• 颜色是带标签时段。“周一上午”和“周一下午”交换后算另一张课表；如果时段本身不区分，计数对象已经改变。
• 图着色只处理两两不能同场的冲突。教室容量、每天最多一场、教师休息间隔都不在当前定义中，需要额外变量与约束。
• 若冲突数据漏掉一条边，着色证明依然可能完全正确，但它证明的是一张错误冲突图上的结论。这正是数学正确与建模正确的区别。

这个案例把本课程的几块知识真正接上了：集合给出 $V$ 和 $T$，关系给出 $E$，函数给出排程，逻辑量词定义合法性，图论识别树结构，归纳证明一般公式，计数法则给出方案总数。

园区网络：连接、抗单边故障与平面布线

第二个问题来自网络设计。五栋建筑需要用地下光缆连通：图书馆、实验楼、教学楼、食堂和宿舍。设计方提出三个层次的要求：平时任意两栋楼能通信；任意一条光缆损坏后仍能通信；如果所有光缆必须铺在同一层管沟里，线路之间不能交叉。

这三个要求看起来都在说“网络好不好”，数学上却是三种不同性质：连通性、删边后的连通性和平面性。

对象：建筑是顶点，光缆是无向边

令 $V$ 是建筑集合，$E$ 是实际铺设的光缆集合。若每对建筑之间最多有一条光缆，光缆没有方向，也不会从一栋楼连回自己，那么网络可以建模为简单无向图

一条从 $u$ 到 $v$ 的路径是顶点序列

其中每一对相邻顶点都由边连接。图连通，指的是每一对顶点之间都存在路径。

“删除任意一条边仍连通”可以直接写成

对至少有两个顶点的连通图，这也等价于图中没有割边。割边是删除后会让某些原本相连的顶点失去连接的边。

猜想：抗一次边故障至少需要 $v$ 条边

设网络有 $v\ge 3$ 个顶点和 $e$ 条边。我们猜想：只要要求删除任意一条边后仍连通，就一定有

而且这个下界能达到：长度为 $v$ 的环 $C_v$ 恰好使用 $v$ 条边，并能承受任意一条边故障。

这次要证明的是最优性，所以证明必须分成两半。下界说明任何方案都不能少于 $v$ 条边；构造一个 $v$ 条边的环说明 $v$ 条边确实够用。

证明下界：先看每个顶点的度数

假设网络满足单边故障后仍连通。任意顶点 $x$ 的度数不可能是 $0$，否则原图就不连通；度数也不可能是 $1$，因为删除 $x$ 唯一关联的那条边会把 $x$ 孤立。

因此每个顶点都满足

把所有顶点度数相加，每条无向边会在两个端点各贡献一次，所以握手引理给出

另一方面，$v$ 个顶点的度数都至少为 $2$，于是

两边除以 $2$，得到 $e\ge v$。

这段证明没有猜线路应该怎么画。它从故障要求推出局部条件 $\deg(x)\ge 2$，再用握手引理把所有局部条件合成全局边数下界。很多网络下界证明都用这个套路：先问“每个点至少要承担什么”，再把局部总量对账。

证明可达：环恰好达到下界

把 $v$ 个顶点首尾相接成环 $C_v$，边数正好是 $v$。删除环上的任意一条边后，剩下的图是一条包含全部 $v$ 个顶点的路径。路径中任意两点仍能沿线到达，所以删边后的图连通。

于是环既满足抗单边故障要求，又达到了所有可行方案的边数下界。若每条光缆成本相同，它在“光缆条数最少”这个目标下最优。

再加一条现实约束：线路必须平面铺设

如果线路交叉必须建设额外接点，而设计又禁止这种交叉，我们需要图是平面图。这里说“平面”，不是说当前草图恰好没有交叉，而是说这张图存在一种无边交叉的平面画法。

对一个连通简单平面图，设顶点数、边数和面数分别为 $v,e,f$。欧拉公式的前提和结论是

当 $v\ge 3$ 时，每个面的边界长度至少为 $3$；每条边在所有面边界中一共被计算两次，因此

将 $f=2-v+e$ 代入，得到简单连通平面图的边数上界

现在假设五栋楼之间都要求直接相连，模型就变成完全图 $K_5$。它有

但平面边数上界只允许

因为 $10>9$，五栋楼两两直接连接的简单网络不可能无交叉地铺在同一平面。注意我们证明的是“不存在任何无交叉画法”，而不只是“我画的这张图有交叉”。

边界检查：简单图假设不是小字备注

• 两个顶点的简单图最多只有一条边，删除它必然断开，所以 $v=2$ 时不存在抗单边故障的简单图。若允许两条并行光缆，模型应改成多重图，前面的简单图定义不能原样使用。
• 环能抵抗一条边损坏，不代表能抵抗任意两条边同时损坏。故障数量改变后，要改用更高的边连通性要求。
• 边数最少不等于总长度最短。实际距离不同，就需要给边加权，并重新定义优化目标。
• 欧拉公式这里用于连通平面嵌入；边数上界还用到了简单图和 $v\ge 3$。漏掉自环、重边或顶点数前提，推导可能失效。
• 线路在一张草图中交叉，不能推出图非平面；只有排除所有可能的重画方式，或使用必要条件推出矛盾，才能证明非平面。

这个案例把路径、连通、割边、度数、握手引理和平面图放进了同一条推理链。定义负责把“可靠”拆细，下界证明负责说明最少成本，构造负责给出可执行方案，平面边数界负责识别额外物理约束是否可满足。

流式去重：把程序运行变成可归纳的状态

最后看一个算法问题。系统按顺序收到标识符序列

要求输出每个不同标识符第一次出现时的顺序。比如输入“甲、乙、甲、丙”，输出应该是“甲、乙、丙”。

代码看起来很简单：维护一个“见过的标识符集合” $S$ 和一个输出序列 $L$。读到新标识符时，如果它不在 $S$ 中，就加入 $S$ 并追加到 $L$；若已经见过，就什么也不做。

真正要证明的不是“这段代码看起来合理”，而是：对每个有限输入序列，它都恰好输出所有不同标识符，既不重复，也不改变首次出现的先后次序。

对象：输入前缀、集合状态和输出序列

处理完前 $i$ 个输入后，把集合状态和输出序列分别记为 $S_i$ 与 $L_i$。初始状态是

从状态 $(S_i,L_i)$ 读入 $a_{i+1}$ 时，转移规则是

其中 $\mathbin{\|}$ 表示把一个元素追加到序列末尾。

为什么同时维护集合与序列？集合适合回答“是否见过”，查询语义清楚；但集合不记录首次出现顺序。若只证明最终集合正确，还没有证明输出序列的顺序正确。

猜想：每个前缀都满足四个条件

单写“$S$ 存着已经见过的元素”还不够强，因为最终要求还包含输出不重复和顺序正确。我们把循环不变式写完整。处理完前 $i$ 项后：

$L_i$ 中的元素两两不同；$L_i$ 的元素集合恰好是 $S_i$；并且这些元素按照它们在输入中第一次出现的位置递增排列。

这四条合在一起，才足以在循环结束时推出完整后置条件。这里有一个很常见的经验：归纳步骤卡住时，问题未必是归纳法不合适，也可能是归纳命题写得太弱。把真正需要保留的信息一起写进不变式，后一步反而更容易证明。

证明：初始化、保持、终止

证明按已经处理的元素个数 $i$ 归纳。

这就是归纳在程序证明里的样子。基础情形对应初始化，归纳步骤对应一次状态转移保持性质，归纳结论说明所有可达轮次都满足不变式，终止时再把不变式翻译成输出结论。

计数检查：有多少种输入一定会出现重复

假设标识符只能来自一个大小为 $m$ 的有限集合 $D$。长度为 $n$ 的输入序列是从位置集合到 $D$ 的函数，也可以看成 $n$ 次有序选择。

每个位置都有 $m$ 种选择，根据乘法法则，原始输入一共有

种。

当 $n\le m$ 时，不含重复的序列第一个位置有 $m$ 种选择，第二个位置只能从剩下的 $m-1$ 个标识符中选，依次类推，所以数量是

因此至少含一次重复的输入数为

当 $n>m$ 时，不需要继续展开乘积。把 $n$ 个输入位置当成对象，把 $m$ 个标识符当成类别，映射 $j\mapsto a_j$ 是一个从 $n$ 元集合到 元集合的全函数。对象比类别多，鸽巢原理保证至少两个不同位置映到同一个标识符，所以每个长度为 的输入都含重复。

这里计数和证明各自回答不同问题：不变式保证去重算法对每个输入都正确；计数说明不同输入结构有多少种，并判断重复何时不可避免。

边界检查：程序正确不代表规格完整

• 空输入 $n=0$ 必须返回空序列。它不是可忽略的特例，而是不变式的基础情形。
• 上面的终止结论针对有限输入。无限数据流没有“扫描完整个输入”的时刻，但不变式仍对每个有限前缀成立。
• “重复”依赖相等关系。如果标识符大小写不敏感，或需要先标准化空格，那么对象定义必须先加入标准化函数。
• 若只保存集合 $S$ 而不保存序列 $L$，可以判断成员，却不能承诺输出保持首次出现顺序。
• 证明只说明逻辑正确，没有给出时间和空间上界。若 $D$ 极大，集合查询的实现方式会影响性能，但不会改变这份正确性证明的结构。

把三个案例压回同一条建模主线

三个案例表面上差别很大，其实每一步都能对齐。

你可以把这张表当成以后做题时的检查顺序。先找对象，再写定义；猜想要有清楚量词；证明时检查所用定理的前提；最后故意拿最小规模和极端结构去撞模型。

定理前提要在使用前对账

综合题最容易出现一种“局部都对，整体却错”的证明：每行推导没毛病，但定理被用在不满足前提的对象上。下面几组前提值得反复核对。

• 使用树的 $n-1$ 条边、唯一路径或叶子性质前，先证明图连通且无环。
• 使用握手引理时，要确认度数和边来自同一张有限无向图；每条边为什么贡献两次要说清楚。
• 使用平面图边数界 $e\le 3v-6$ 时，要检查简单、连通、平面以及 $v\ge 3$。若对象是二分平面图，还能用面长至少为 $4$ 得到更强界，但也必须先证明二分性。
• 使用乘法法则时，每一步的可选数量要对所有此前选择保持一致；若数量会随前缀改变，就使用广义乘法法则并逐步写出。
• 使用鸽巢原理时，要明确对象集合、类别集合和分配函数。只说“东西多，所以必有重复”不算完整论证。
• 使用归纳法时，要写出谓词、基础情形和对所有合法 成立的归纳步骤。基础情形与归纳步骤之间不能断一环。

构造、验证与最优性不要混成一句话

面对“找一个最好方案”，可以固定按三层证据组织答案。

章末建模练习

下面的题目不只问最后的数值。先自己写出对象、定义、猜想、证明和边界，再展开答案核对。

练习：森林排课的方案数

某冲突图是一片森林，共有 $n$ 个课程顶点和 $c$ 个连通分量。现有 $k\ge 2$ 个带标签时段。证明合法排程数为

练习：七个站点的最低冗余成本

一个由七个站点组成的简单无向网络，要求删除任意一条边后仍连通。每条边成本相同。至少需要多少条边？请同时给出下界证明和达到下界的构造。

练习：重复输入的精确计数

标识符集合有 $5$ 个元素，输入序列长度为 $3$。有多少个序列至少出现一次重复？

练习：找出错误的平面图论证

有人说：“一张有 $6$ 个顶点、$11$ 条边的图满足 $11\le 3\cdot 6-6$，所以它一定是平面图。”这段话错在哪里？

接下来怎么继续学

这门课给出的不是一张“公式清单”，而是一套可以继续扩展的工作方式。后续方向不同，你要带走的主线也不同。

• 想继续学组合数学，可以从双射、双计数和递推开始，再进入生成函数。先练习把一个难数的集合映到一个容易数的序列集合，而不是先搜公式。
• 想继续学图论，可以沿匹配、网络流、着色、平面图和极值图论推进。每学一个新定理，都把“对象类别、必要前提、能回答的实际问题”记在一起。
• 想学习算法设计与分析，可以把本章的不变式写法带到排序、图搜索、贪心和动态规划。先写循环或递归在每一步承诺什么，再讨论运行时间。
• 想进入概率论，可以把计数得到的有限方案集变成样本空间。此时第一步仍是定义对象，第二步才是给事件计数并除以样本空间大小。
• 想接触形式化验证、自动机或可满足性问题，可以继续加强命题逻辑、谓词逻辑和状态机。程序状态是对象，转移是关系，安全性质是不变式，整个证明框架并没有换。

以后遇到一个新问题，可以先在纸上写五句话：对象是什么；合法对象怎样定义；我猜什么成立；证据覆盖了哪些量词；最小与极端输入会发生什么。只要这五句话能对上，离散数学里的证明、计数与图结构就不再是分散的工具，而会自然接到同一个模型里。

边界上，空森林需要另行约定；这里默认每个连通分量至少有一个顶点，因此 $1\le c\le n$。

所以 $e\ge 7$。把七个站点首尾连接成七边形环，恰好使用 $7$ 条边；任意删一条边后得到包含所有顶点的路径，仍然连通。因此最少需要 $7$ 条边。

这里数的是有序输入序列；若只数三元素多重集合，计数对象不同，答案也会改变。