# 离散结构：只数能够同时成立的分配 — 学习任务单

[学习指南](https://unireadinglist.com/zh-cn/guides/discrete-structures/)

[课程专题: 离散数学](https://unireadinglist.com/zh-cn/subjects/mathematics/#course-discrete-mathematics)

来源确认日期: 2026-11-04

学习计划与例题由 University Reading List 编辑整理。

围绕集合、逻辑、计数与二部匹配的入门路线。Levin 指第四版，Epp 指第五版，Lovász 等指2003年第一版。虚构题中任务与位置有标签、各位置容量为1，并明确列出允许关系；不提供真实机构的排程保证。

## 选择你的起点

- [ ] 需要免费探究路线
  选 Levin，用调查题、例子和选择性反馈，从第四版的逻辑与证明开始。

- [ ] 需要明确的证明写作训练
  若量词、关系和论证结构需要细练，选 Epp。

- [ ] 希望用问题深化推理
  能跟随短证明、希望从计数和图论问题看结构，可选 Lovász 等。

## 三本书如何取舍

### Discrete Mathematics: An Open Introduction（离散数学：开放式导论）

Oscar Levin · 4 · 2025
免费的逻辑到图论入门

什么情况下适合读: 希望先调查小例子，再形式化。
什么情况下选别本: 需要全题完整解答，或默认旧版与新版顺序相同。
建议阅读范围: 第四版的逻辑与证明、图论、计数、数列；例题对应匹配内容。
局限与取舍: 提示和交互反馈支持探究，完整证明仍需自己写。

#### 选书前试做

列出 A,B:\{1,2\}、C:\{2,3\} 的分配，并排除重复占位。
检查标准: 恰有两种合法分配；解释局部选择的乘积8为何不是答案。

你的笔记:

________________________________

ISBN: 9781032966168

[官方免费阅读](https://discrete.openmathbooks.org/dmoi4.html)

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/mathematics/discrete-mathematics-an-open-introduction/)

### Discrete Mathematics with Applications（离散数学及其应用）

Susanna S. Epp · 5 · 2020
逻辑与关系的系统主线

什么情况下适合读: 需要在计数前写清资格与互异性。
什么情况下选别本: 只想解图论谜题而跳过持续的逻辑证明训练。
建议阅读范围: 第1–5章语言与证明、第8章关系、第9章计数、第10章图与树。
局限与取舍: 进入图应用前需投入较广的形式训练；WebAssign 是独立产品。

#### 选书前试做

把分配写成任务到位置的单射 f，且每个 (t,f(t)) 都获允许。
检查标准: 资格条件与单射性缺一不可；普通函数仍允许任务共享位置。

你的笔记:

________________________________

ISBN: 9781337694193

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/mathematics/discrete-mathematics-with-applications-epp/)

### Discrete Mathematics: Elementary and Beyond（离散数学：从初等到深入）

László Lovász; József Pelikán; Katalin Vesztergombi · 2003
问题驱动的计数与匹配

什么情况下适合读: 能把例子变为短论证，希望理解结构。
什么情况下选别本: 需要形式逻辑、关系和算法记号的完整教学大纲。
建议阅读范围: 所选第一版的计数、图与树、匹配主题，按章名定位。
局限与取舍: 简洁问题需要耐心；课程缺少的形式主题可另配系统教材。

#### 选书前试做

在后续题中找到邻接位置不足的任务子集。
检查标准: \{A,B,D\} 有3个任务、仅2个邻接位置；总空位数不能消除障碍。

你的笔记:

________________________________

ISBN: 9780387955858

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/mathematics/discrete-mathematics-elementary-and-beyond/)

## 开始前需要会什么

### 能否区分函数和单射？

你的笔记:

________________________________

### 能否避免重复与非法计数？

你的笔记:

________________________________

### Hall 条件说什么？

你的笔记:

________________________________

## 六步学习计划

- [ ] 画关系

建议阅读范围: 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；仅允许列出的配对。任务和位置均有标签，不假设概率模型。

你的笔记:

________________________________

## 改变假设，再做一题: 无法到达的空位不能救场

保留原资格，增加任务 D，允许位置为 \{1,2\}，同时新增位置4。判断可行性。再新增一条资格边 D→4，求修复后的完整分配数，并解释为何一条边已是最小修复规模。

你的笔记:

________________________________

## 进入下一阶段之前

- 把分配写成满足资格关系的单射。
- 给出总容量看不出的 Hall 障碍。
- 证明匹配个数与最小修复规模。

## 答案与解释

### 能否区分函数和单射？

函数为每个任务指定一处；单射还禁止两个不同任务占用同一位置。

### 能否避免重复与非法计数？

三个任务可以枚举六个位置排列后检查资格；不能把受容量耦合的选择直接当独立选择相乘。

### Hall 条件说什么？

每个任务子集 S 的邻接位置至少有 |S| 个；检查的是全部子集，不仅是单个任务。

### 八种局部选择，只有两种合法分配

1. A 与 B 必须以某种顺序占据1和2，故 C 只能用3。按任务顺序，分配为 (1,2,3)、(2,1,3)。
2. 单任务邻集大小均为2；\{A,B\} 为2，\{A,C\} 与 \{B,C\} 为3，三任务整体为3，因此各子集均满足 Hall 条件。
3. 2·2·2=8 把冲突也算入，并非单射数；检查六个位置排列，同样只有两种合法。

按 A,B,C 顺序，恰有 (1,2,3) 与 (2,1,3) 两种完整分配。

检验结果: 逐项检查资格与位置互异。由于 A、B 强制 C=3，剩余1、2只有两种排列，故没有遗漏。

### 改变假设，再做一题: 无法到达的空位不能救场

1. 修复前，S=\{A,B,D\} 的邻集只有 \{1,2\}。三个任务不能单射到两个位置，即使总共已有四个位置，也不存在完整分配。
2. 加入 D→4 后，A、B 仍必须占1、2，所以 D 必须占4，C 占3；A 与 B 可以互换。
3. 按 A,B,C,D 顺序有 (1,2,3,4)、(2,1,3,4)。不加边已证不可行，一条边可行，所以最小新增边数为1，但修复方案未必唯一。

新增资格边前为0种；加入 D→4 后恰为2种。最小修复规模为一条边。

检验结果: 位置4必须有任务能到达才有帮助。不要声称 D→4 是唯一的一边修复；题目要求分析指定修复，而非证明唯一性。

## 常见误区

### 把选择当独立

容量约束把选择关联起来，乘法法则需要合法的逐步计数。

### 只检查总数

总空位充足仍可能存在局部瓶颈。

### 混淆存在与计数

一个匹配或 Hall 定理回答可行性；精确个数需另给穷尽论证。

## 参考来源与版本

- [Author: fourth edition and reorganization](https://discrete.openmathbooks.org/dmoi4.html)
  作者确认第四版的新顺序、完整免费阅读及 CC BY-NC-SA 4.0 范围。

- [Cengage: exact fifth edition and contents](https://www.cengage.com/c/discrete-mathematics-with-applications-5e-epp/9781337694193/)
  Cengage 确认第五版的逻辑、关系、计数与图论主题，平台另有产品。

- [Springer: selected first-edition softcover](https://link.springer.com/book/10.1007/b97469)
  Springer 确认2003年所选平装及问题驱动的计数、图论和匹配范围。

这些是本站建议的学习活动，并非大学官方作业，也不代表对每本书逐页通读。

[编辑与选书方法](https://unireadinglist.com/zh-cn/editorial/)