內容簡介
圖論及其算法《圖論及其算法》可作為高等院校計算機、數學、信息、電子、管理等專業的教材，還可作為相關專業人員的參考書。
圖書目錄
出版說明
前言
第1章 圖的基本概念
1.1 圖論發展簡史
1.2 圖的概念
1.2.1 圖
1.2.2 子圖
1.2.3 一些重要類型的圖
1.3 頂點的度和圖的同構
1.3.1 頂點的度
1.3.2 圖的同構
1.4 圖的運算
1.4.1 並與和
1.4.2 笛卡兒積
1.4.3 超立方體
1.4.4 格線
1.4.5 邊收縮
1.4.6 線圖
1.5 路和連通
1.5.1 路和迴路的定義
1.5.2 連通性
1.6 有向圖
1.6.1 有向圖的概念
1.6.2 有向圖的度
1.6.3 有向網路
1.6.4 有向圖的連通性
1.7 圖的矩陣表示
1.7.1 關聯矩陣
1.7.2 鄰接矩陣
1.7.3 距離矩陣
1.7.4 連通矩陣
1.7.5 特殊類型圖的鄰接矩陣
1.7.6 有向圖的矩陣表示
1.8 習題
第2章 樹
2.1 樹的基本性質
2.1.1 樹的概念
2.1.2 樹的性質
2.1.3 樹的度序列與同構
2.1.4 樹的葉子數
2.1.5 有向樹
2.2 生成樹
2.2.1 生成樹的概念
2.2.2 生成樹的計數
2.3 最優生成樹
2.3.1 Kmskal算法
2.3.2 Prim算法
2.3.3 破圈法
2.4 深度優先搜尋與廣度優先搜尋
2.4.1 深度優先搜尋
2.4.2 廣度優先搜尋
2.5 最優二元樹與前綴碼
2.5.1 最優二元樹
2.5.2 前綴碼
2.6 樹的Pmfer編碼
2.7 習題
第3章 距離與連通性
3.1 圖的距離
3.1.1 離徑、中心、半徑與直徑
3.1.2 樹的中心
3.1.3 自補圖與距離
3.2 圖的連通性
3.2.1 點連通度、邊連通度
3.2.2 點、邊連通度的性質
3.2.3 塊
3.3 連通圖
3.3.1 k.連通圖
3.3.2 2.連通圖
3.3.3 Menger定理
3.4 最短路算法
3.4.1 從一個始點到一個終點的最短路
3.4.2 任意兩點問的最短路
3.5 習題
第4章 圖的遍歷問題
4.1 歡拉圖
4.1.1 歐拉圖的相關定義
4.1.2 一筆畫問題
4.1.3 七筆畫問題
4.2 中國郵遞員問題
4.3 哈密爾頓圖
4.4 格雷碼
4.5 旅行售貨員問題
4.6 E-圖與H-圖的關係
4.7 習題
第5章 圖的匹配與獨立集
5.1 二分圖
5.2 圖的匹配
5.3 二分圖的匹配
5.3.1 二分圖的完全匹配
5.3.2 二分圖最大匹配的生成算法
5.4 最優匹配
5.4.1 求最優匹配的Kuhn-Munkres算法
5.4.2 求最小基數最優匹配的算法
5.5 穩定匹配
5.6 獨立集和覆蓋
5.7 Ramsey數
5.7.1 Ramsey定理
5.7.2 一般化的Ramsey數
5.8 習題
第6章 圖的染色
6.1 頂點染色
6.1.1 色數
6.1.2 色數的一個算法
6.2 邊染色
6.2.1 邊色數的概念
6.2.2 Vizing定理
6.3 色多項式
6.4 圖染色的套用
6.4.1 點染色的實際套用
6.4.2 邊染色的實際套用
6.5 習題
第7章 平面圖
7.1 平面圖的概念及Euler公式
7.1.1 平面圖的概念
7.1.2 Euler公式
7.2 一些特殊平面圖及平面圖的對偶圖
7.2.1 一些特殊平面圖
7.2.2 對偶圖
7.3 Kuratowsk定理
7.4 平面性算法
7.5 五色定理和四色猜想
7.6 習題
第8章 網路流
8.1 流與割
8.2 最大流最小割定理
8.3 最大流問題的算法
8.3.1 最大流問題的標號算法(2F算法)
8.3.2 最大流問題的最短增廣路算法
8.4 Menger定理
8.5 最小費用流問題
8.6 最小費用流問題的算法
8.6.1 負迴路算法
8.6.2 最小費用路算法
8.7 習題
第9章 圖參數A(H)值
9.1 圖參數A(H)
9.1.1 圖參數A(H)的概念
9.1.2 2-圖
9.1.32-圖母圖的結構
9.1.4 3-圖的存在性
9.1.5 3-圖的推廣
9.2 樹的A(T)值
9.2.1 關於樹的A(T)值的結論
9.2.2 由樹構造的A(H)=3圖
9.2.3 方法證明
9.3 頂點數不超過7的圖按參數A(H)的分類
9.3.1 頂點數不超過7的3一圖
9.3.2 頂點數不超過7的4一圖
9.3.3 |V(H)|≤7的圖按A(H)值的分類
9.4 習題
附錄
附錄A部分習題參考答案
第1章習題答案
第2章習題答案
第3章習題答案
第4章習題答案
第5章習題答案
第6章習題答案
第7章習題答案
第8章習題答案
第9章習題答案
附錄B本書符號列表
參考文獻
