目录
第一部分基础理论篇
第一章图的基本概念3
§1引论3
§2图的概念14
§3道路与回路17
§4图的矩阵表示法23
§5中国邮路问题26
§6平面图29
§7Petri网33
第二章树41
§1树的概念41
§2基本性质45
§3关联矩阵与基本关联矩阵46
§4回路矩阵与基本回路矩阵48
§5关联矩阵与回路矩阵的关系51
§6割集矩阵与基本割集矩阵53
§7树的数目56
§8内向树与外向树61
§9二元树64
§10Huffman树66
§11搜索树69
§12流动商人问题与分支定界法70
§13最佳匹配问题77
第三章图的算法81
§1最佳路径问题及其算法81
§2最短树问题及其算法85
§3任意两点间最短距离及其算法90
§4图的连通性判断94
§5树的生成95
§6DFS算法102
§7图的块划分109
§8强连通块的划分112
第二部分应用篇
第四章电路网络问题119
§1克希荷夫定律119
§2电路问题119
§3状态变量法理论基础121
§4状态变量法122
§5状态变量法举例128
§6若干特殊情形140
第五章信号流图问题150
§1矩阵与Coates流图150
§2代数方程组与Mason信号流图151
§3信号流图的运算152
§4行列式的展开法158
§5代数方程组的Coates图解法160
§6Mason公式162
*§7Mason公式的证明166
第六章网络流图问题174
§1网络流图问题与最大流174
§2割切175
§3FordFulkerson最大流最小割切定理176
§4标号法178
§5EdmondsKarp修正算法,Dinic算法及其它181
§6开关网络简介185
第七章匹配理论、色数问题及其它189
§1最大匹配189
§2Hall定理191
§3匈牙利算法及例192
§4最佳匹配194
§5最佳匹配的算法及例198
§6色数问题202
§7独立集概念及其应用206
§8支配集210
§9色数的一种求法211
§10色多项式213
§11色数问题应用举例214
§12PERT图法216
§13强连通化问题219