圖論與代數結構

離散數學以離散量為研究對象，主要包括數理邏輯、集合論、圖論和代數結構四部分內容。書中給出了大量的例題，它們不但有助於對概念的理解，同時也幫助讀者掌握不同的證明方法。

基本介紹

• 書名：圖論與代數結構 
• 作者：戴一奇等
• ISBN：9787302018148
• 頁數：220
• 出版社：清華大學出版社
• 出版時間：1995-8-1

書籍簡介

版　次：1

字　數：331000

印刷時間：2003-5-1

紙　張：膠版紙

包　裝：平裝

定　價：￥12.90

編輯推薦

各章後面附有較多的習題，有難有易，同時還有一定數量的上機題，可以幫助讀者熟悉掌握圖的編程技巧。

內容簡介

離散數學是計算機專業的基礎數學課程，本書與“數理邏輯與集合論”一起構成了清華大學計算機的離散數學課程的教材。學時為50學時。本書是作者在使用多年“圖論與代數結構” 講義的基礎上完成的。本書共十章，分為兩部分。前六章是圖論，第一章介紹圖的基本概念及其代數表示方法，第二章至第六章分別詳細討論了道路與迴路、樹、平面圖與圖的著色、匹配與網路流、圖的連貫性等圖的主要內容，並且將它們與計算機的套用緊密結合，分別介紹了眾多良好的圖算法，給出其正確性證明與複雜度分析，以便讀者在圖的套用及算法的設計與分析方面能得到較好的訓練與培養。第七章至第十章是代數結構部分，主要討論了群、環和域、格與布爾代數等內容，它們都是抽象代數的基本內容，是計算機科學的重要數學基礎。全書結構緊湊、內容精煉、證明嚴謹、語言流暢。為了便於讀者理解和掌握基本理論，書中提供豐富的例題，每章後面附有較多的習題，難度恰當，還有一定數量的上機題，可以幫助讀者熟悉、掌握圖的編程技巧。本書可作為計算機專業學生的教科書或參考書，也可供計算機工程技術人員作參考。

作者簡介

戴一奇，男，1946年10月出生於浙江省瑞安市，1964年考入清華大學自動控制系，1970年畢業後留校任教至今，其中1982年獲計算機軟體工學碩士學位。目前任清華大學計算機科學與技術系教授，博士生導師。

書籍目錄

第一章 基本概念

1.1 圖的概念

1.2 圖的代數表示

習題一

第二章 道路與迴路

2.1 道路與迴路

2.2 道路與迴路的判定

2.3 歐拉道路與迴路

2.4 哈密頓道路與迴路

2.5 旅行商問題

2.6 最短路徑

2.7 關鍵路徑

2.8 中國郵路

習題二

第三章 樹

3.1 樹的有關定義

3.2 基本關聯矩陣及其性質

3.3 支撐樹的計數

3.4 迴路矩陣與割集矩陣

3.5 支撐樹的生成

3.6 Huffman樹

3.7 最短樹

3.8 最大分枝

習題三

第四章 平面圖與圖的著色

4.1 平面圖

4.2 極大平面圖

4.3 非平面圖

4.4 圖的平面性檢測

4.5 對偶圖

4.6 色數與色數多項式

習題四

第五章 匹配與網路流

5.1 二分圖的最大匹配

5.2 完全匹配

5.3 最佳匹配及其算法

5.4 最大基數匹配

5.5 網路流圖

5.6 Ford-Fulkerson最大流標號算法

5.7 最大流的Edmonds-Karp算法

5.8 最小費用流

習題五

第六章 圖的連通性

6.1 割點、割邊和塊

6.2 結點與邊的連通度

6.3 明格爾定理

6.4 連通度的判定

6.5 無向圖的DFS算法與圖的塊劃分

6.6 有向圖的DFS算法與強連通塊劃分

習題六

第七章 代數結構預備知識

7.1 集合與映射

7.2 等價關係

7.3 代數系統的概念

7.4 同構與同態

習題七

第八章 群

8.1 半群

8.2 群、群的基本性質

8.3 循環群 群的同構

8.4 變換群和置換群 Cayley定理

8.5 陪集和群的陪集分解 Lagrange定理

8.6 正規子群與商群

8.7 群的同態、同態基本定理

8.8 群的真積

習題八

第九章 環和域

9.1 環及其性質

9.2 理想、商環

9.3 環的同態

9.4 域的概念

習題九

第十章 格與布爾代數

10.1 格及其基本性質

10.2 子格、同態與同構

10.3 分配格與有補格

10.4 布爾代數

10.5 布爾表達式

習題十