第一章 何谓图论 1
1.1 在我们周围图的表示 1
1. 何谓图 1
2. 图的点和线及图的方向性 3
1.2 图论的起源--哥尼斯堡桥与四色问题 4
1.3 图论在现实中的广泛应用 4
习题 6
参考文献 7
第二章 图的基础 9
2.1 图的结构 9
1. 图的基本结构 9
2. 子图 11
3. 边交叉时的表示 11
4. 有向图和无向图 12
1. 图的短接和连通图 13
2.2 图的秩和零度 13
2. 图的连通片 15
3. 图的秩 15
4. 图的零度 17
5. 图的秩与零度的拓扑意义 17
2.3 同构 20
2.4 平面图和对偶图 22
1. 图的同胚 24
2. 图的平面性和对偶 25
2.5 次数(度数) 28
习题 31
参考文献 32
第三章 路径和割集 33
3.1 路径 33
3.2 割集 35
1. 路径与割集的关系 35
2. 用关联集合的环和表示割集 39
3. 分割特定的两个顶点的割集的算法 40
3.3 关联矩阵 43
1. 关联矩阵定义 43
2. 计算关联矩阵的秩的预备知识 45
3. 关联矩阵的秩 46
4. 基底关联矩阵的最大阶数子矩阵与树的关系 49
3.4 割集矩阵 51
1. 割集矩阵定义 51
2. 割集矩阵的秩 52
3.5 有向图的矩阵表示 55
1. 有向图的关联矩阵 55
2. 树(或林)的数目 57
3. 有向图的割集矩阵 58
4. 线性组合系数的确定 61
5. 有向图的割集矩阵的秩和基底割集矩阵 62
3.6 通讯网(网络流) 66
1. 网络流问题 66
2. 最大流-最小切割定理 68
3. 通讯网的矩阵表示与实现 69
习题 71
参考文献 73
第四章 回路 75
4.1 回路的性质 75
1. 零度与补树的关系 76
2. 平面图的关联集合及其对偶图的回路 77
3. 平面图和对偶图中割集与回路的对应关系 78
4.2 基本回路 80
4.3 欧拉图 82
1. 闭边列(欧拉回路) 82
2. 一笔画定理(欧拉定理) 84
3. 欧拉图 84
4. 欧拉图的环和 85
4.4 回路矩阵与割集矩阵的关系 87
1. 回路矩阵 88
2. 基本回路矩阵 89
3. 回路矩阵与关联矩阵的正交性 90
4. 由回路矩阵与关联矩阵的正交性所得出的结果 93
5. 回路矩阵的秩 94
6. 从基底回路矩阵计算全部补树的方法 95
7. 回路矩阵与割集矩阵的关系 96
8. 基本回路矩阵与基本割集矩阵的互换性 98
9. 基本割集的拓扑算法 100
4.5 有向图的回路矩阵 104
1. 回路矩阵 104
2. 基本回路矩阵 106
3. 回路矩阵与关联矩阵的正交性 107
习题 109
参考文献 111
第五章 在电路和电子线路方面的应用 112
5.1 基尔霍夫电流定律和电压定律 112
1. KCL(基尔霍夫电流定律) 114
2. KVL(基尔霍夫电压定律) 118
5.2 基本回路电流和节点电压 120
5.3 戴勒亨定理 126
1. 戴勒亨定理 126
2. 戴勒亨扩展定理 129
5.4 电路分析中树和补树的作用 132
5.5 节点电压法和回路电流法 133
1. 电阻网络分析 134
2. KCL和KVL的系统化的公式表示 135
3. 欧姆定律的矩阵表示 138
4. 节点电压法 138
5. 回路电流法 139
6. RLC电路的稳态分析 141
5.6 电路分析中的拓扑公式 142
习题 145
参考文献 147
6.1 连接矩阵 149
第六章 连接矩阵 149
1. 连接矩阵的K次乘方 151
2. 连接矩阵C与单位矩阵U之和的(n-1)次乘方：(C+U)n-1 152
6.2 连接矩阵的行列式 153
1. 置换与回路的关系 156
2. 连接矩阵的行列式及其拓扑公式 157
6.3 连接矩阵的子行列式 158
6.4 开关电路分析 163
习题 167
参考文献 168
第七章 信号流图 169
7.1 信号流图 169
7.2 用图的化简法求解方程 171
7.3 梅森公式 176
1. 梅森公式 176
2. 梅森公式的证明 179
7.4 在控制系统方面的应用 187
习题 192
参考文献 193
第八章 在逻辑电路方面的应用 195
8.1 逻辑元件 195
8.2 1-网和0-网 197
1. 1-网 198
2. 输出函数F的拓扑公式 199
3. 0-网 202
8.3 逻辑电路的分析 204
习题 207
参考文献 208
附录 209
附·1 线性代数基础 209
附·2 排列与组合 221
附·3 布尔代数 222
习题详解 225
索引 263