應用圖論

第一章圖的基本概念
1.1引言.
1.2圖的概念
1.2.1圖的定義
1.2.2頂點的度
1.2.3圖的同構
1.3子圖
1.4路與連通
1.4.1路與圈
1.4.2連通性
1.4.3二分圖的一個特征
1.5有向圖
1.5.1基本概念
1.5.2存在有向路和有向圈的條件
1.5.3不存在有向圈的條件
習題一
第二章樹與割集
2.1樹及其性質
2.1.1樹的定義
2.2.2樹的特征
2.2生成樹
2.2.1生成樹
2.2.2生成樹的構造
2.2.3基本圈
2.2.4生成樹的數(shù)目
2.3割集
2.3.1割集
2.3.2割集的性質
2.3.3割集的環(huán)和
2.3.4基本割集
2.3.3割點
2.4圖的連通度
2.4.1(點)連通度
2.4.2邊連通度
2.5最優(yōu)生成樹
2.6單向樹
2.6.1單向樹
2.6.2有序樹
2.6.3Huffman樹
習題二
第三章圖的矩陣表示
3.1關聯(lián)矩陣
3.1.1無向圖的關聯(lián)矩陣
3.1.2有向圖的關聯(lián)矩陣
3.2鄰接矩陣
3.2.1無向圖的鄰接矩陣
3.2.2有向圖的鄰接矩陣
3.3圈矩陣
3.3.1無向圖的圈矩陣
3.3.2有向圖的回路矩陣
3.4割集矩陣
3.4.1無向圖的割集矩陣
3.4.2有向圖的割集矩陣
習題三
第四章搜索技術與分枝定界法
4.1搜索技術
4.1.1深探法DFS
4.1.2廣探法BFS
4.1.3α-β搜索法
4.2分枝定界法
第五章最短路問題
5.1解最短路問題的基本方法
5.1.1從一個始點v1到一個終點vn的最短路問題
5.1.2求任意兩頂點間的最短路問題
5.2具有負權有向圖中的最短路
5.2.1賦權有向圖中的最短路
5.2.2具有負權的有向圖中的最短路
5.3K最短路問題
5.3.1雙向掃視算法基礎
5.3.2雙向掃視算法過程
5.3.3算法原理..
習題五
第六章可行遍性
6.1Euler圖
6.2中國郵遞員問題
6.2.1Euler圖中的最優(yōu)環(huán)游
6.2.2非Euler圖中的最優(yōu)環(huán)游
6.3Hamilton圖
6.4旅行售貨員問題
6.4.1調整Hamilton圈以得到近似最優(yōu)解
6.4.2分枝定界法確定精確最優(yōu)解
習題六
第七章平面圖
7.1平面圖的概念
7.1.1平面圖
7.1.2Euler公式
7.1.3極大平面圖
7.2圖的平面性檢測
7.2.1Kuratowski圖
7.2.2平面性檢測
7.3對偶圖
7.4五色定理與四色猜想
習題七
第八章著色.匹配與覆蓋
8.1色數(shù)問題
8.1.1色數(shù)及其性質
8.1.2色數(shù)的一種求法
8.1.3色數(shù)多項式
8.2匹配.覆蓋及獨立集
8.2.1匹配
8.2.2覆蓋與獨立集
8.3二分圖的匹配和覆蓋
8.3.1Hall定理
8.3.2匹配與覆蓋的關系
8.3.3匈牙利算法
8.4人員分派問題
8.4.1人員分派問題
8.4.2最優(yōu)分派問題
習題八
第九章網(wǎng)絡流問題與選址問題
9.1基本概念和定理
9.1.1網(wǎng)絡的流
9.1.2割
9.1.3最大流最小割定理
9.2解最大流問題的標號法
9.3多端最大流問題
9.4選址問題
9.4.1單服務設施問題
9.4.2一般選址問題
習題九
第十章流圖與代數(shù)方程組
10.1Mason信號流圖
10.1.1信號流圖
10.1.2線性方程組的Mason信號流圖表示
10.1.3信號流圖的運算規(guī)則
10.2Mason公式
10.3矩陣與Coate流圖
習題十
參考書目...