本書是在吉林大學《離散數(shù)學》（高等教育出版社，1983年）以及《離散數(shù)學》（高等教育出版社，2002年）的基礎上，結合多年的教學實踐編寫而成。本書分為8章，主要內容包括集合論基礎知識、計數(shù)理論、古典數(shù)理邏輯、圖與網(wǎng)絡、數(shù)論基礎知識、抽象代數(shù)的群、環(huán)和域、格和布爾代數(shù)，以及計算模型中的三種類型的結構。
第一章 集合論基礎
1.1 集合的基本概念
習題1.1
1.2 關系
1.2.1 關系的基本概念及其性質
1.2.2 等價關系
1.2.3 偏序關系
習題1.2
1.3 映射
1.3.1 集合的基數(shù)
1.3.2 可數(shù)集合
1.3.3 不可數(shù)集合
習題1.3
1.4 集合在計算機科學中的應用
1.4.1 關系在關系數(shù)據(jù)庫中的應用
1.4.2 關系代數(shù)與數(shù)據(jù)子語言
1.4.3 等價關系在計算機中的應用
1.4.4 序關系在項目管理中的應用
第二章 計數(shù)
2.1 兩個基本計數(shù)原理
2.1.1 加法原理
2.1.2 乘法原理
習題2.1
2.2 排列與組合
2.2.1 集合的排列數(shù)和組合數(shù)
2.2.2 多重集的排列數(shù)和組合數(shù)
習題2.2
2.3 二項式定理
2.3.1 二項式定理
2.3.2 二項式定理的推廣
習題2.3
2.4 容斥原理
2.4.1 容斥原理
2.4.2 容斥原理的應用
習題2.4
2.5 鴿巢原理
2.5.1 簡單的鴿巢原理
2.5.2 加強的鴿巢原理
習題2.5
第三章 古典數(shù)理邏輯
3.1 命題邏輯
3.1.1 命題與公式
3.1.2 命題公式的等價關系和蘊涵關系
3.1.3 范式
3.1.4 命題邏輯在二值邏輯器件和語句邏輯中的應用
習題3.1
3.2 謂詞邏輯
3.2.1 謂詞邏輯的基本概念
3.2.2 謂詞公式
3.2.3 謂詞公式的等價關系和蘊涵關系
3.2.4 范式
3.2.5 謂詞邏輯的應用
習題3.2
第四章 圖與網(wǎng)絡
4.1 圖
4.1.1 圖的基本概念
4.1.2 權圖Dijkstra算法
習題4.1
4.2 樹
4.2.1 樹及其等價命題
4.2.2 最優(yōu)樹Kruskal算法
4.2.3 求最優(yōu)樹的其他算法
習題4.2
4.3 有向圖 歐拉路
4.3.1 有向圖與有向樹
4.3.2 歐拉路 歐拉圖
4.3.3 無向圖 無向圖中的歐拉路
習題4.3
4.4 哈密頓圖
4.4.1 哈密頓路 哈密頓圖的必要條件
4.4.2 哈密頓圖的若干充分條件
習題4.4
4.5 平面圖
4.5.1 平面圖判定 庫拉托夫斯基判定準則
4.5.2 平面圖的歐拉公式
4.5.3 平面圖的著色
習題4.5
4.6 匹配 二部圖
習題4.6
4.7 Konig無限性引理
習題4.7
4.8 網(wǎng)絡優(yōu)化算法
4.8.1 單源最短路徑問題具體算法及實現(xiàn)和比較
4.8.2 最大流問題具體算法及實現(xiàn)和比較
習題4.8
第五章 數(shù)論基礎
5.1 整除性 輾轉相除
5.1.1 整除及其性質
5.1.2 輾轉相除
習題5.1
5.2 互質 質因數(shù)分解
5.2.1 整數(shù)互質
5.2.2 質數(shù)與合數(shù) 算術基本定理
習題5.2
5.3 合同 一次同余式
5.3.1 合同及其性質
5.3.2 剩余類 一次同余式
習題5.3
5.4 九韶定理 歐拉函數(shù)
5.4.1 一次同余式組秦九韶定理
5.4.2 一元高次同余式的化簡
5.4.3 剩余系遍歷歐拉函數(shù)
習題5.4
5.5 一元高次同余式 二次剩余
5.5.1 一元高次同余式的解
5.5.2 二次同余式 二次剩余
習題5.5
5.6 數(shù)論在計算機通信安全中的應用
5.6.1 密碼系統(tǒng)
5.6.2 愷撒密碼
5.6.3 Vigenere密碼
5.6.4 希爾密碼
5.6.5 RSA公鑰系統(tǒng)
習題5.6
第六章 群、環(huán)、域
6.1 代數(shù)系統(tǒng)
習題6.1
6.2 群的定義
6.2.1 半群
6.2.2 群
6.2.3 群的性質
6.2.4 置換群
習題6.2
6.3 子群及其陪集
6.3.1 子群的定義
6.3.2 子群的判別條件
6.3.3 循環(huán)群
6.3.4 陪集
習題6.3
6.4 群的同態(tài)及同構
6.4.1 同態(tài)映射
6.4.2 同構映射
6.4.3 同態(tài)核
習題6.4
6.5 環(huán)
6.5.1 環(huán)的定義及性質
6.5.2 環(huán)同態(tài)
習題6.5
6.6 域的特征 素域
6.6.1 域的特征
6.6.2 素域
習題6.6
6.7 多項式
6.7.1 多項式的整除性
6.7.2 多項式的根
6.7.3 有理域上的多項式
6.7.4 分圓多項式
習題6.7
6.8 有限域
習題6.8
6.9 群環(huán)域在計算機科學中的應用
6.9.1 計數(shù)問題
6.9.2 糾錯碼
6.9.3 多項式編碼方法及其實現(xiàn)
習題6.9
第七章 格與布爾代數(shù)
7.1 引言
7.2 格的定義
習題7.2
7.3 格的性質
7.3.1 對偶原理
7.3.2 格的其他性質
7.3.3 格的同態(tài)與同構
習題7.3
7.4 幾種特殊的格
7.4.1 有界格
7.4.2 有余格
7.4.3 分配格
7.4.4 模格
習題7.4
7.5 布爾代數(shù)
7.5.1 布爾代數(shù)的定義及其性質
7.5.2 有限布爾代數(shù)的表示理論
7.5.3 布爾代數(shù)的同態(tài)與同構
習題7.5
7.6 布爾表達式的化簡問題
習題7.6
7.7 格與布爾代數(shù)在計算機科學中的應用
7.7.1 開關電路函數(shù)
7.7.2 邏輯門
7.7.3 全加器的邏輯設計
第八章 語言和有限狀態(tài)機
8.1 語言和語法
8.1.1 語法結構
8.1.2 語法結構的類型
8.1.3 演繹樹
8.1.4 巴克斯-諾爾形式
習題8.1
8.2 帶有輸出的有限狀態(tài)機
習題8.2
8.3 沒有輸出的有限狀態(tài)機
習題8.3
8.4 語言識別
8.4.1 正則集合
8.4.2 克林定理
8.4.3 其他幾種類型的有限狀態(tài)機
習題8.4
8.5圖靈機
習題8.5
參考文獻
結論：這樣的圖有兩類，或者都是偶數(shù)度點或者有兩個奇數(shù)度點。
現(xiàn)在再回頭來看對應七橋問題的圖，所有的點都是奇數(shù)度點，共有4個，故這個圖肯定不能一筆畫成。因此歐拉指出上述所要求的散步路線是不存在的。
從數(shù)學的觀點看，圖的理論在開始時似乎價值不大，因為它所討論的內容多為娛樂性的一些難題。但是近代的數(shù)學發(fā)展，特別是計算機學科誕生后的現(xiàn)代，圖與網(wǎng)絡作為一種工具在計算機科學與技術、信息、經濟、工程和管理等諸多領域的應用中發(fā)揮著重要的作用。
我們知道計算機中數(shù)據(jù)結構，離不開數(shù)組、串、各種鏈接表、樹和圖，因此圖是計算機中數(shù)據(jù)表示、存儲和運算的基礎。下面再看現(xiàn)實生活中關于圖與網(wǎng)絡的幾個小例子。
平面圖問題 在一塊地上蓋有3座房子，并且挖了3口井供房主人使用。由于土質和氣候等關系，這些井中的這一個或那一個常常干枯。因此各座房子的主人有時要到這個井去打水，有時要到那個井去打水，3個井都可能需要去。不久，這3個房子的主人相互間變成了冤家，于是決定修建各家通往3個井的小道，使得他們在去3個井的途中不會相遇。你能否幫他們設計整個的小道路線，滿足他們的要求？
最優(yōu)支撐樹問題 某一地區(qū)有若干個主要城市，擬修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經高速公路直接或間接到達另一個城市。假設已經知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最��？
最大流問題 假設從城市P到城市Q的一個公路網(wǎng)，公路網(wǎng)中每段公路上每天可以通過的汽車的數(shù)量有上限，那么經過該公路網(wǎng)，每天最多可以有多少輛汽車從城市P到城市Q？
上述例子都易于用圖形的形式直觀地描述和表達，在其中的最優(yōu)支撐樹問題和最大流問題中，每條路還標有成本費用值和汽車流量這種權值，把這種加了權的圖形稱為網(wǎng)絡。為了討論方便，本章對圖和網(wǎng)絡不做嚴格區(qū)分。與圖和網(wǎng)絡相關的最優(yōu)化問題稱為網(wǎng)絡優(yōu)化問題，這在追求最低成本、獲取最高利潤、強化效率的市場經濟時代，正獲得廣泛的應用。
……
書單推薦
