离散结构：只数能够同时成立的分配
把每个任务的选择数相乘，会把冲突也当作合法分配。先把资格表示成关系，判断是否存在完整匹配，再数满足全部约束的分配。
学习计划与例题由 University Reading List 编辑整理。 编辑与选书方法 · 来源确认日期:
本页目录
这份指南适合谁
围绕集合、逻辑、计数与二部匹配的入门路线。Levin 指第四版，Epp 指第五版，Lovász 等指2003年第一版。虚构题中任务与位置有标签、各位置容量为1，并明确列出允许关系；不提供真实机构的排程保证。
选择你的起点
希望用问题深化推理
能跟随短证明、希望从计数和图论问题看结构，可选 Lovász 等。
三本书如何取舍
Discrete Mathematics: An Open Introduction（离散数学：开放式导论）
Oscar Levin · 版次: 4 · 2025
免费的逻辑到图论入门
- 什么情况下适合读
- 希望先调查小例子，再形式化。
- 什么情况下选别本
- 需要全题完整解答，或默认旧版与新版顺序相同。
- 建议阅读范围
- 第四版的逻辑与证明、图论、计数、数列；例题对应匹配内容。
- 局限与取舍
- 提示和交互反馈支持探究，完整证明仍需自己写。
选书前试做
列出 A,B:{1,2}、C:{2,3} 的分配，并排除重复占位。
检查标准: 恰有两种合法分配；解释局部选择的乘积8为何不是答案。
Discrete Mathematics with Applications（离散数学及其应用）
Susanna S. Epp · 版次: 5 · 2020
逻辑与关系的系统主线
- 什么情况下适合读
- 需要在计数前写清资格与互异性。
- 什么情况下选别本
- 只想解图论谜题而跳过持续的逻辑证明训练。
- 建议阅读范围
- 第1–5章语言与证明、第8章关系、第9章计数、第10章图与树。
- 局限与取舍
- 进入图应用前需投入较广的形式训练；WebAssign 是独立产品。
选书前试做
把分配写成任务到位置的单射 f，且每个 (t,f(t)) 都获允许。
检查标准: 资格条件与单射性缺一不可；普通函数仍允许任务共享位置。
Discrete Mathematics: Elementary and Beyond（离散数学：从初等到深入）
László Lovász; József Pelikán; Katalin Vesztergombi · 2003
问题驱动的计数与匹配
- 什么情况下适合读
- 能把例子变为短论证，希望理解结构。
- 什么情况下选别本
- 需要形式逻辑、关系和算法记号的完整教学大纲。
- 建议阅读范围
- 所选第一版的计数、图与树、匹配主题，按章名定位。
- 局限与取舍
- 简洁问题需要耐心；课程缺少的形式主题可另配系统教材。
选书前试做
在后续题中找到邻接位置不足的任务子集。
检查标准: {A,B,D} 有3个任务、仅2个邻接位置；总空位数不能消除障碍。
开始前需要会什么
能否区分函数和单射？
函数为每个任务指定一处；单射还禁止两个不同任务占用同一位置。
能否避免重复与非法计数？
三个任务可以枚举六个位置排列后检查资格；不能把受容量耦合的选择直接当独立选择相乘。
Hall 条件说什么？
每个任务子集 S 的邻接位置至少有 |S| 个；检查的是全部子集，不仅是单个任务。
六步学习计划
已完成步骤: 0 / 6
勾选用于自我记录，不是成绩评定；标记不会发送给本站。
-
画关系
建议阅读范围: Levin 图论或 Epp 关系。
要做的练习: 画二部图及允许配对表。
检查标准: 不添加任务之间的边或隐藏容量。
-
形式化合法性
建议阅读范围: Epp 数学语言与函数。
要做的练习: 用量词写完整分配的条件。
检查标准: 每项任务获分配、配对合法、位置互异。
-
构造并计数
建议阅读范围: Levin 或 Lovász 计数。
要做的练习: 列出全部合法分配，并解释 C 的位置为何被迫确定。
检查标准: C 必须为3，A 与 B 交换1和2。
-
检查结构判据
建议阅读范围: 匹配主题。
要做的练习: 为 {A,B,C} 的7个非空子集列出邻集大小。
检查标准: 没有子集位置不足，存在性与计数一致。
-
破坏并修复
建议阅读范围: 匹配与后续题。
要做的练习: 加入 D 和位置4，指出障碍，再补 D→4 并重新计数。
检查标准: 仅增加位置无效，一条资格边可恢复可行性。
-
区分三种证据
建议阅读范围: 自己的两份解答。
要做的练习: 分别写存在证书、不可能证书和计数论证。
检查标准: 找到一个匹配只证存在；Hall 障碍证不可能；精确个数还需穷尽理由。
原创例题与解析
八种局部选择，只有两种合法分配
任务 A,B,C 必须占用互异位置1,2,3。允许位置为 A:{1,2}、B:{1,2}、C:{2,3}。求全部完整分配，并用 Hall 条件验证可行性。
前提假设
每项任务恰占一个位置，每处容量为1；仅允许列出的配对。任务和位置均有标签，不假设概率模型。
- A 与 B 必须以某种顺序占据1和2，故 C 只能用3。按任务顺序，分配为 (1,2,3)、(2,1,3)。
- 单任务邻集大小均为2；{A,B} 为2，{A,C} 与 {B,C} 为3，三任务整体为3，因此各子集均满足 Hall 条件。
- 2·2·2=8 把冲突也算入，并非单射数；检查六个位置排列，同样只有两种合法。
答案与解释
按 A,B,C 顺序，恰有 (1,2,3) 与 (2,1,3) 两种完整分配。
检验结果
逐项检查资格与位置互异。由于 A、B 强制 C=3，剩余1、2只有两种排列，故没有遗漏。
改变假设，再做一题
无法到达的空位不能救场
保留原资格，增加任务 D，允许位置为 {1,2}，同时新增位置4。判断可行性。再新增一条资格边 D→4，求修复后的完整分配数，并解释为何一条边已是最小修复规模。
- 修复前，S={A,B,D} 的邻集只有 {1,2}。三个任务不能单射到两个位置，即使总共已有四个位置，也不存在完整分配。
- 加入 D→4 后，A、B 仍必须占1、2，所以 D 必须占4，C 占3；A 与 B 可以互换。
- 按 A,B,C,D 顺序有 (1,2,3,4)、(2,1,3,4)。不加边已证不可行，一条边可行，所以最小新增边数为1，但修复方案未必唯一。
答案与解释
新增资格边前为0种；加入 D→4 后恰为2种。最小修复规模为一条边。
检验结果
位置4必须有任务能到达才有帮助。不要声称 D→4 是唯一的一边修复；题目要求分析指定修复，而非证明唯一性。
常见误区
把选择当独立
容量约束把选择关联起来，乘法法则需要合法的逐步计数。
只检查总数
总空位充足仍可能存在局部瓶颈。
混淆存在与计数
一个匹配或 Hall 定理回答可行性；精确个数需另给穷尽论证。
进入下一阶段之前
- 把分配写成满足资格关系的单射。
- 给出总容量看不出的 Hall 障碍。
- 证明匹配个数与最小修复规模。
参考来源与版本
来源确认日期:
- Author: fourth edition and reorganization
作者确认第四版的新顺序、完整免费阅读及 CC BY-NC-SA 4.0 范围。
- Cengage: exact fifth edition and contents
Cengage 确认第五版的逻辑、关系、计数与图论主题，平台另有产品。
- Springer: selected first-edition softcover
Springer 确认2003年所选平装及问题驱动的计数、图论和匹配范围。
这些是本站建议的学习活动，并非大学官方作业，也不代表对每本书逐页通读。