應(yīng)用圖論

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