圖論及其算法

出版說(shuō)明
前言
第1章 圖的基本概念
1.1 圖論發(fā)展簡(jiǎn)史
1.2 圖的概念
1.2.1 圖
1.2.2 子圖
1.2.3 一些重要類(lèi)型的圖
1.3 頂點(diǎn)的度和圖的同構(gòu)
1.3.1 頂點(diǎn)的度
1.3.2 圖的同構(gòu)
1.4 圖的運(yùn)算
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 特殊類(lèi)型圖的鄰接矩陣
1.7.6 有向圖的矩陣表示
1.8 習(xí)題
第2章 樹(shù)
2.1 樹(shù)的基本性質(zhì)
2.1.1 樹(shù)的概念
2.1.2 樹(shù)的性質(zhì)
2.1.3 樹(shù)的度序列與同構(gòu)
2.1.4 樹(shù)的葉子數(shù)
2.1.5 有向樹(shù)
2.2 生成樹(shù)
2.2.1 生成樹(shù)的概念
2.2.2 生成樹(shù)的計(jì)數(shù)
2.3 最優(yōu)生成樹(shù)
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)二元樹(shù)與前綴碼
2.5.1 最優(yōu)二元樹(shù)
2.5.2 前綴碼
2.6 樹(shù)的Pmfer編碼
2.7 習(xí)題
第3章 距離與連通性
3.1 圖的距離
3.1.1 離徑、中心、半徑與直徑
3.1.2 樹(shù)的中心
3.1.3 自補(bǔ)圖與距離
3.2 圖的連通性
3.2.1 點(diǎn)連通度、邊連通度
3.2.2 點(diǎn)、邊連通度的性質(zhì)
3.2.3 塊
3.3 連通圖
3.3.1 k.連通圖
3.3.2 2.連通圖
3.3.3 Menger定理
3.4 最短路算法
3.4.1 從一個(gè)始點(diǎn)到一個(gè)終點(diǎn)的最短路
3.4.2 任意兩點(diǎn)問(wèn)的最短路
3.5 習(xí)題
第4章 圖的遍歷問(wèn)題
4.1 歡拉圖
4.1.1 歐拉圖的相關(guān)定義
4.1.2 一筆畫(huà)問(wèn)題
4.1.3 七筆畫(huà)問(wèn)題
4.2 中國(guó)郵遞員問(wèn)題
4.3 哈密爾頓圖
4.4 格雷碼
4.5 旅行售貨員問(wèn)題
4.6 E-圖與H-圖的關(guān)系
4.7 習(xí)題
第5章 圖的匹配與獨(dú)立集
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 獨(dú)立集和覆蓋
5.7 Ramsey數(shù)
5.7.1 Ramsey定理
5.7.2 一般化的Ramsey數(shù)
5.8 習(xí)題
第6章 圖的染色
6.1 頂點(diǎn)染色
6.1.1 色數(shù)
6.1.2 色數(shù)的一個(gè)算法
6.2 邊染色
6.2.1 邊色數(shù)的概念
6.2.2 Vizing定理
6.3 色多項(xiàng)式
6.4 圖染色的應(yīng)用
6.4.1 點(diǎn)染色的實(shí)際應(yīng)用
6.4.2 邊染色的實(shí)際應(yīng)用
6.5 習(xí)題
第7章 平面圖
7.1 平面圖的概念及Euler公式
7.1.1 平面圖的概念
7.1.2 Euler公式
7.2 一些特殊平面圖及平面圖的對(duì)偶圖
7.2.1 一些特殊平面圖
7.2.2 對(duì)偶圖
7.3 Kuratowsk定理
7.4 平面性算法
7.5 五色定理和四色猜想
7.6 習(xí)題
第8章 網(wǎng)絡(luò)流
8.1 流與割
8.2 最大流最小割定理
8.3 最大流問(wèn)題的算法
8.3.1 最大流問(wèn)題的標(biāo)號(hào)算法(2F算法)
8.3.2 最大流問(wèn)題的最短增廣路算法
8.4 Menger定理
8.5 最小費(fèi)用流問(wèn)題
8.6 最小費(fèi)用流問(wèn)題的算法
8.6.1 負(fù)回路算法
8.6.2 最小費(fèi)用路算法
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 樹(shù)的A(T)值
9.2.1 關(guān)于樹(shù)的A(T)值的結(jié)論
9.2.2 由樹(shù)構(gòu)造的A(H)=3圖
9.2.3 方法證明
9.3 頂點(diǎn)數(shù)不超過(guò)7的圖按參數(shù)A(H)的分類(lèi)
9.3.1 頂點(diǎn)數(shù)不超過(guò)7的3一圖
9.3.2 頂點(diǎn)數(shù)不超過(guò)7的4一圖
9.3.3 |V(H)|≤7的圖按A(H)值的分類(lèi)
9.4 習(xí)題
附錄
附錄A部分習(xí)題參考答案
第1章習(xí)題答案
第2章習(xí)題答案
第3章習(xí)題答案
第4章習(xí)題答案
第5章習(xí)題答案
第6章習(xí)題答案
第7章習(xí)題答案
第8章習(xí)題答案
第9章習(xí)題答案
附錄B本書(shū)符號(hào)列表
參考文獻(xiàn)