第一章 图的基本概念 1
第一节 图的定义 1
一、什么是图 1
二、有向图和无向图 3
第二节 点与边的关联关系 5
一、线度 5
二、线度与边的关系 5
第三节 图的矩阵表示 7
一、邻接矩阵 7
二、关联矩阵 9
第四节 同构 11
一、定义 11
二、同构的判断 12
一、道路与回路 13
第五节 道路与回路 13
二、道路矩阵及其计算 16
三、道路矩阵的Warshall算法 19
第六节 欧拉回路与哈密顿回路 22
一、欧拉回路及其应用 22
二、哈密顿回路及其应用 26
习题 29
第二章 树 30
第一节 树的有关定义 30
一、树的定义 30
二、支撑树 31
第二节 基本关联矩阵 32
一、基本关联矩阵 32
二、基本关联矩阵的性质 33
第三节 树的计数 36
一、比内-柯西定理 36
二、树的计数 38
第四节 Huffman树 40
一、二元树与最优二元树 40
二、Huffman树 42
第五节 搜索树 43
一、α-β法 43
二、DFS和BFS搜索法 44
三、分支与界法 47
习题 50
第三章 最佳道路问题 52
第一节 最短树问题 52
一、定义 52
二、Kruskal算法及举例 52
第二节 最短路问题 54
一、两个引理 54
二、Dijkstra算法及其应用 55
第三节 关键路径问题 58
一、实际背景与相应的数学模型 58
二、无有向回路正权图的关键路径算法 59
三、作业的允许延迟时间的计算 64
第四节 中国邮路问题 65
习题 67
第四章 回路矩阵与割集矩阵 69
第一节 回路矩阵 69
一、完全回路矩阵与基本回路矩阵 69
二、回路矩阵及其性质 73
第二节 基本关联矩阵和回路矩阵的关系 74
第三节 割集与割集矩阵 76
一、割集的定义 76
二、完全割集矩阵与基本割集矩阵 77
三、割集矩阵及其性质 79
第四节 基本回路矩阵与基本割集矩阵的关系 80
习题 85
第五章 电路网络的基本方程 87
第一节 电路的基本定律 87
第二节 节点方程 91
一、节点方程的基本形式 91
二、节点方程计算举例 94
三、用视察法求节点导纳矩阵 107
第三节 回路方程 109
一、回路方程的基本形式 109
二、回路方程计算举例 111
三、用视察法求回路阻抗矩阵 121
第四节 割集方程 122
一、割集方程的基本形式 122
二、割集方程计算举例 125
三、用视察法求割集导纳矩阵 132
第五节 特勒根定理 133
习题 135
第六章 状态变量法 136
第一节 基本原理 136
一、状态变量法的基本方程 136
二、状态方程的构造 137
第二节 状态变量法举例 145
第三节 状态变量法的一般步骤 163
习题 168
第七章 信号流图 169
第一节 Mason信号流图与图的运算 169
一、信号流图 169
二、信号流图的运算规则 172
三、计算举例 177
一、Mason公式 181
第二节 Mason公式 181
二、利用Mason公式计算举例 182
第三节 网络的信号流图 187
一、利用信号流图求解电路网络参数 187
二、求解电路网络信号流图的方法 190
习题 196
第八章 网络流理论与可靠性分析 197
第一节 网络流图 197
一、实际背景 197
二、网络流图定义 197
第二节 利用网流法计算直流电路 199
第三节 潮流的近似计算 205
一、近似公式 205
二、利用网流法近似计算系统可靠性 206
一、最大流的概念 209
第四节 最大流与最小割切定理 209
二、割切与割切容量 210
三、最大流与最小割切定理 211
第五节 标号法 213
一、标号算法 213
二、计算举例 214
第六节 最小费用流 215
一、问题的实际背景 215
二、一种简单的计算方法 219
第七节 网流理论在输电系统静态可靠性分析中的应用 220
一、基础知识 220
二、状态分解的规则及其正确性证明 221
三、可靠性指标简述 224
四、最大流算法在可靠性分析中的应用 226
五、最小割切的应用 230
习题 232
习题答案 233