離散結構：只數能夠同時成立的分配
把每個任務的選擇數相乘，會把衝突也當作合法分配。先把資格表示成關係，判斷是否存在完整匹配，再數滿足全部約束的分配。
學習計畫與例題由 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年所選平裝及問題驅動的計數、圖論和匹配範圍。
這些是本站建議的學習活動，並非大學官方作業，也不代表對每本書逐頁通讀。