# 離散結構：只數能夠同時成立的分配 — 學習任務單

[學習指南](https://unireadinglist.com/zh-tw/guides/discrete-structures/)

[課程主題: 離散數學](https://unireadinglist.com/zh-tw/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-tw/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-tw/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-tw/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-tw/editorial/)