圖論及其算法

出版說明
前言
第1章 圖的基本概念
1.1 圖論發(fā)展簡史
1.2 圖的概念
1.2.1 圖
1.2.2 子圖
1.2.3 一些重要類型的圖
1.3 頂點的度和圖的同構(gòu)
1.3.1 頂點的度
1.3.2 圖的同構(gòu)
1.4 圖的運算
1.4.1 并與和
1.4.2 笛卡兒積
1.4.3 超立方體
1.4.4 網(wǎng)格
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 有向網(wǎng)絡(luò)
1.6.4 有向圖的連通性
1.7 圖的矩陣表示
1.7.1 關(guān)聯(lián)矩陣
1.7.2 鄰接矩陣
1.7.3 距離矩陣
1.7.4 連通矩陣
1.7.5 特殊類型圖的鄰接矩陣
1.7.6 有向圖的矩陣表示
1.8 習(xí)題
第2章 樹
2.1 樹的基本性質(zhì)
2.1.1 樹的概念
2.1.2 樹的性質(zhì)
2.1.3 樹的度序列與同構(gòu)
2.1.4 樹的葉子數(shù)
2.1.5 有向樹
2.2 生成樹
2.2.1 生成樹的概念
2.2.2 生成樹的計數(shù)
2.3 最優(yōu)生成樹
2.3.1 Kmskal算法
2.3.2 Prim算法
2.3.3 破圈法
2.4 深度優(yōu)先搜索與廣度優(yōu)先搜索
2.4.1 深度優(yōu)先搜索
2.4.2 廣度優(yōu)先搜索
2.5 最優(yōu)二元樹與前綴碼
2.5.1 最優(yōu)二元樹
2.5.2 前綴碼
2.6 樹的Pmfer編碼
2.7 習(xí)題
第3章 距離與連通性
3.1 圖的距離
3.1.1 離徑、中心、半徑與直徑
3.1.2 樹的中心
3.1.3 自補圖與距離
3.2 圖的連通性
3.2.1 點連通度、邊連通度
3.2.2 點、邊連通度的性質(zhì)
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 習(xí)題
第4章 圖的遍歷問題
4.1 歡拉圖
4.1.1 歐拉圖的相關(guān)定義
4.1.2 一筆畫問題
4.1.3 七筆畫問題
4.2 中國郵遞員問題
4.3 哈密爾頓圖
4.4 格雷碼
4.5 旅行售貨員問題
4.6 E-圖與H-圖的關(guān)系
4.7 習(xí)題
第5章 圖的匹配與獨立集
5.1 二分圖
5.2 圖的匹配
5.3 二分圖的匹配
5.3.1 二分圖的完全匹配
5.3.2 二分圖最大匹配的生成算法
5.4 最優(yōu)匹配
5.4.1 求最優(yōu)匹配的Kuhn-Munkres算法
5.4.2 求最小基數(shù)最優(yōu)匹配的算法
5.5 穩(wěn)定匹配
5.6 獨立集和覆蓋
5.7 Ramsey數(shù)
5.7.1 Ramsey定理
5.7.2 一般化的Ramsey數(shù)
5.8 習(xí)題
第6章 圖的染色
6.1 頂點染色
6.1.1 色數(shù)
6.1.2 色數(shù)的一個算法
6.2 邊染色
6.2.1 邊色數(shù)的概念
6.2.2 Vizing定理
6.3 色多項式
6.4 圖染色的應(yīng)用
6.4.1 點染色的實際應(yīng)用
6.4.2 邊染色的實際應(yīng)用
6.5 習(xí)題
第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 習(xí)題
第8章 網(wǎng)絡(luò)流
8.1 流與割
8.2 最大流最小割定理
8.3 最大流問題的算法
8.3.1 最大流問題的標(biāo)號算法(2F算法)
8.3.2 最大流問題的最短增廣路算法
8.4 Menger定理
8.5 最小費用流問題
8.6 最小費用流問題的算法
8.6.1 負(fù)回路算法
8.6.2 最小費用路算法
8.7 習(xí)題
第9章 圖參數(shù)A(H)值
9.1 圖參數(shù)A(H)
9.1.1 圖參數(shù)A(H)的概念
9.1.2 2-圖
9.1.32-圖母圖的結(jié)構(gòu)
9.1.4 3-圖的存在性
9.1.5 3-圖的推廣
9.2 樹的A(T)值
9.2.1 關(guān)于樹的A(T)值的結(jié)論
9.2.2 由樹構(gòu)造的A(H)=3圖
9.2.3 方法證明
9.3 頂點數(shù)不超過7的圖按參數(shù)A(H)的分類
9.3.1 頂點數(shù)不超過7的3一圖
9.3.2 頂點數(shù)不超過7的4一圖
9.3.3 |V(H)|≤7的圖按A(H)值的分類
9.4 習(xí)題
附錄
附錄A部分習(xí)題參考答案
第1章習(xí)題答案
第2章習(xí)題答案
第3章習(xí)題答案
第4章習(xí)題答案
第5章習(xí)題答案
第6章習(xí)題答案
第7章習(xí)題答案
第8章習(xí)題答案
第9章習(xí)題答案
附錄B本書符號列表
參考文獻(xiàn)