堵塞流理论及其应用

绪论 1

上篇 堵塞流理论基础 7

第一章 必备的图论与网络分析知识 7

§1.1 图论中常用的名词 7

§1.2 最短路问题 10

§1.3 最大流问题 15

§1.4 最小费用流问题 24

第二章 堵塞流的基本理论 36

§2.1 堵塞流的基本概念与定义 36

§2.2 网络的理论最小流通能力与其最小完全截集的关系 45

§2.3 网络理论最小流通能力的确定方法 46

§2.4 堵塞流与堵塞截面 48

第三章 网络最大堵塞流问题 57

§3.1 最大流问题的重新定义 57

§3.2 最大流问题的图单纯形算法 58

§3.3 图单纯形算法的计算复杂性分析 59

第四章 网络的最小堵塞流问题 62

§4.1 求解网络最小流的分支定界法 62

§4.2 求解网络最小流的双向增流算法 66

§4.3 求解网络最小流问题的图单纯形算法 71

§4.4 关于最小流性质的讨论 75

§4.5 求解网络无环最小流的近似算法 77

§4.6 最小流算法的计算机实现 80

§5.1 随机流动仿真模型的建立 85

第五章 交通网络随机流仿真研究 85

§5.2 交通网络随机堵塞流仿真软件设计 89

§5.3 仿真结果的分析 91

上篇参考文献 100

下篇 堵塞流理论应用研究 101

第六章 堵塞流理论在哈密顿轨判定上的应用研究 101

§6.1 有向网络中哈密顿轨判定问题的网络流模型 101

§6.2 在有向网络中构造无环最小支撑流的方法 103

§6.3 在有向网络中判断是否存在无环最小支撑流的实证研究 118

第七章 一般象棋盘中的马步哈密顿圈问题及其实证研究 142

§7.1 前言 142

§7.2 象棋盘中的马步哈密顿圈问题研究的基本理论 143

§7.3 广义象棋盘中的马步哈密顿圈问题及其实证研究 148

§7.4 有洞棋盘的马步哈密顿圈问题及其实证研究 152

§7.5 大型象棋盘中的马步哈密顿圈实证解及算法的多项式性质研究 159

第八章 堵塞流理论在交通网络设计与运行控制中的应用 162

§8.1 交通网络防堵塞设计的基本准则 162

§8.2 交通网络防堵塞改造方案的优化方法——最小成本改造法 162

§8.3 最小流控制方法 166

§8.4 最大流控制方法 171

下篇参考文献 177

附录 178

附录1 网络最大流和最小流计算机程序 178

附录2 四个网络的最小流计算值及仿真结果 202

附录3 塔形图生成器的设计及15个塔形图中的哈密顿圈解 215

附录4 一般象棋盘的马步图生成器的设计与20×n（n=5～100）棋盘中的马步哈密顿圈解 222