離散數學引論

本書以組合計數問題為重點，介紹了組合數學的基本原理和思想方法，全書共分8章：鴿巢原理，排列與組合，容斥原理，遞推關係，生成函數，Polya計數理論，相異代表系，組合設計．取材的側重點在於體現組合數學在計算機科學特別是在演演算法分析領域中的應用．每章後面都附有一定數量的習題，供讀者練習和進一步思考． .

本書可作為計算機專業、應用數學專業研究生和高年級本科生的教材或教學參考書，也可供從事這方面工作的教學、科研和技術人員參考． ...

序 言

第一篇 圖及其演演算法

1. 1 什麼是圖論

1. 2 圖的定義

1. 3 Brouwer不動點定理

1. 4 Dijkstra演演算法

習題一

1. 5 樹

1. 6 生成樹

1. 6. 1 生成樹的個數

1. 6. 2 最優生成樹的Kruskal演演算法

1. 7 常用樹

1. 7. 1 有序二元樹

1. 7. 2 Huffman樹

習題二

1. 8 平面圖

1. 8. 1 平面圖及其Euler公式

1. 8. 2 對偶圖和極大平面圖

1. 8. 3 Kuratowsky定理

1. 8. 4 圖的厚度

習題三

1. 9 縱深搜索和平面嵌入演演算法

1. 9. 1 廣度優先與深度優先搜索演演算法

1. 9. 2 求割頂和塊的演演算法

1. 9. 3 有向圖的DFS和極大強連通子圖的演演算法

1. 9. 4 平面嵌入演演算法

習題四

1. 10 匹配

1. 10. 1 匹配理論

1. 10. 2 二分圖中最大匹配與最佳匹配的演演算法

習題五

1. 11 圖上遍歷

1. 11. 1 Euler圖

1. 11. 2 求Euler迴路的演演算法

1. 11. 3 中國郵路問題

1. 11. 4 Harmihon圖

習題六

1. 12 色

1. 12. 1 邊色數

1. 12. 2 頂色數與面色數

1. 12. 3 色多項式

習題七

1. 13 支配集. 獨立集和Ramsey數

1. 13. 1 支配集和獨立集

1. 13. 2 a G ,

G , G 的計算

1. 13. 3 Ramsey數

1. 13. 4 多元Ramsey數和Schur定理

習題八

1. 14 有向圖

1. 14. 1 有向圖的連通性

1. 14. 2 有向軌與競賽圖

1. 14. 3 有向圈與競賽圖

1. 14. 4 有向Euler圖

習題九

1. 15 網路流

1. 15. 1 Ford-Fulkerson最大流演演算法

1. 15. 2 Dinic最大流演演算法

1. 15. 3 有上下界的網路中的流

1. 15. 4 有供需約束的流

1. 15. 5 PERT問題

1. 15. 6 流與二分圖

習題十

1. 16 連通度

1. 16. 1 無向圖的頂連通度

1. 16. 2 有向圖的頂連通度

1. 16. 3 無向圖的邊連通度

1. 16. 4 有向圖的邊連通度和弱獨立外向生成樹

1. 16. 5 可靠通訊網路

習題十一

第二篇 組合基礎

2. 1 什麼是組合論

2. 2 鴿籠原理

2. 3

×原理與排列組合

2. 3. 1 無重複的排列組合

2. 3. 2 Catalan數

2. 3. 3 可重複的排列組合

習題一

2. 4 容斥原理

習題二

2. 5 生成函數

2. 5. 1 生成函數概念

2. 5. 2 組合數的生成函數

2. 5. 3 拆分自然數

2. 5. 4 排列數的生成函數

習題三

2. 6 遞歸方程

2. 6. 1 遞歸方程的初值問題

2. 6. 2 線性常係數遞歸方程的生成函數解法

2. 6. 3 常係數線性齊次遞歸方程的特徵值解法

2. 6. 4 常係數線性非齊次遞歸方程的解

2. 6. 5 遞歸方程的其它解法

2. 6. 6 Stirling數

習題四

第三篇 代數與計數

3. 1 代數系統及其性質

3. 1. 1 代數系統的定義

3. 1. 2 代數系統的同構與同態

3. 2 群. 環. 域

3. 2. 1 群

3. 2. 2 環

3. 2. 3 域

習題一

3. 3 置換群和循環群

3. 3. 1 置換

3. 3. 2 置換群與循環群

3. 4 Lagrange定理和Burnside定理

3. 5 Polya定理

習題二

3. 6 圖的群

3. 6. 1 圖的自同構群

3. 6. 2 有限群的Cayley圖

習題三

第四篇 離散數學中的空間. 矩陣和擬陣

4. 1 圈空間和斷集空間

4. 1. 1 圈空間

4. 1. 2 斷集空間

4. 2 關聯矩陣和鄰接矩陣

4. 2. 1 關聯矩陣

4. 2. 2 鄰接矩陣

4. 3 圈矩陣和割集矩陣

4. 4 開關網路分析

習題一

4. 5 擬陣

4. 5. 1 擬陣的概念

4. 5. 2 擬陣理論

習題二

4. 6 倒稱矩陣與層次分析

4. 7 正交拉丁方

4. 8 區組設計與區組矩陣

4. 8. 1 BIBD問題

4. 8. 2 區組關聯矩陣

4. 8. 3 Hadamard矩陣

4. 8. 4 區組設計的構作

4. 9 魔矩陣密碼

習題三

第五篇 不確定Turing機和計算的時間複雜度

5. 1 好演演算法和壞演演算法

5. 2 不確定Turing機和NP類問題

5. 3 NPC問題和Cook定理

5. 4 NPC中的組合問題

5. 5 NPC中的圖論問題

習題

第六篇 數理邏輯

6. 1 命題邏輯

6. 1. 1命題及其真假

6. 1. 2 聯結詞與命題公式

6. 1. 3 真值表

6. 1. 4 等價公式. 代換定理與對偶定理

6. 1. 5 範式

6. 2 命題邏輯中的推理

6. 2. 1 蘊含關係

6. 2. 2 真值表推理法

6. 2. 3 直接推理法

6. 2. 4 間接推理法

習題一

6. 3 謂詞邏輯

6. 3. 1 命題的謂詞表達形式

6. 3. 2 量詞

6. 3. 3 謂詞公式及其變元

6. 3. 4 謂詞邏輯中的等價定律. 代入規則

6. 4 謂詞邏輯中的推理

習題二

參考文獻