應用組合數學

第一部分 圖論
　第1章 圖論入門
　　1.1 圖模型
　　1.2 同構
　　1.3 邊計數
　　1.4 可平面圖
　　1.5 小結及參考文獻
　第2章 覆蓋回路和圖著色
　　2.1 歐拉圈
　　2.2 哈密頓回路
　　2.3 圖著色
　　2.4 著色定理
　　2.5 小結及參考文獻
　第3章 樹和搜索
　　3.1 樹的性質
　　3.2 搜索樹和生成樹
　　3.3 旅行商問題
　　3.4 排序算法的樹分析
　　3.5 小結及參考文獻
　第4章 網絡算法
　　4.1 最短路徑
　　4.2 最小生成樹
　　4.3 網絡流
　　4.4 算法上的匹配
　　4.5 運輸問題
　　4.6 小結及參考文獻
第二部分 枚舉
　第5章 排列和選擇的一般計數方法
　　5.1 兩個基本計數法則
　　5.2 簡單排列和選取
　　5.3 重復排列和選取
　　5.4 分配
　　5.5 二項恆等式
　　5.6 小結及參考文獻
　第6章 生成函數
　　6.1 生成函數模型
　　6.2 計算生成函數的系數
　　6.3 分拆
　　6.4 指數生成函數
　　6.5 一個求和方法
　　6.6 小結及參考文獻
　第7章 遞推關系
　　7.1 遞推關系模型
　　7.2 分治關系
　　7.3 線性遞推關系的解
　　7.4 非齊次遞推關系的解
　　7.5 使用生成函數對遞推關系求解
　　7.6 小結及參考文獻
　第8章 容斥原理
　　8.1 利用Venn圖計數
　　8.2 容斥公式
　　8.3 限定位置和車多項式
　　8.4 小結及參考文獻
第三部分 其他主題
　第9章 Polya枚舉公式
　　9.1 等價和對稱群
　　9.2 Burnside定理
　　9.3 循環指標
　　9.4 Polya公式
　　9.5 小結及參考文獻
　第10章 計算機科學在枚舉中的應用
　　10.1 生成排列和組合，程序設計項目
　　10.2 形式語言和文法
　　10.3 有限狀態機
　　10.4 小結及參考文獻
　第11章 圖游戲
　　11.1 逐步受限游戲
　　11.2 尼姆類游戲
　　11.3 小結及參考文獻
附錄A
　A.1 集合論
　A.2 數學歸納法
　A.3 概率簡介
　A.4 鴿巢原理
　A.5 計算復雜度和NP完備性
關于計數和圖論的術語表
關于樹的術語表
參考文獻
索引
部分練習解答（圖靈網站下載）

組合數學是系統分析的基礎，在計算機科學、數學、運籌學、生物學等諸多學科中有著廣泛的應用．組合數學內容繁多、所要處理的問題又多是非常深奧難解的NP問題，掌握組合數學的相當知識已很不易，而熟練運用組合數學解決實際問題則更是困難，通過一兩本書就想要學會組合數學是不太可能的．讀者可以根據自己的需求，選擇合適的書籍，循序漸進地學習組合數學的知識

本書講授離散數學問題求解中組合推理和組合建模的方法、思維和運用，它強調組合推理的3個主要方面——可能性的系統分析，問題邏輯結構的探究，以及精巧、靈活的設計，從而有助于培養基礎離散數學問題求解的能力。

本書有如下三大特色．首先，較多地使用了貼近日常生活、比較容易理解的游戲作為示例。第二，本書詳略得當，強調推理技巧︰只有在需要運用證明中的推理去解決應用問題時，才給出證明，否則不給出證明，而只給出結果，然後把這些結果運用于問題求解．第三，本書以組合數學在計算機科學、運籌學以及有限概率中的重要應用作為研究動力，同時使用紙牌游戲中的概率或推理游戲等作為更有趣的學習背景．這樣可以使學習趣味性更強，而且可以使讀者免于陷入特殊應用的復雜場景中，因此，這是一本面向應用的組合數學教學參考書，讀者可以相對輕松、快速地學習組合數學的相關概念、技巧及其應用。對理論學習感興趣的讀者也可以通過本書領略到組合數學的應用能力，理解各概念和技術的用途，為深入進行理論學習打下良好的基礎，

譯者對本書的翻譯目標是易懂、通暢．我們為此付出了巨大的努力，感謝我愛人在本書翻譯過程中所給予的支持和幫助。但是，由于譯者能力有限，難免有對原書理解不夠的地方，不周之處，敬請讀者指正。