第一类是按照流量与容量的大小关系来划分:若,则称之为饱和弧;若,则称之为非饱和弧。

第二类是按照是否存在流量来划分:

若,则称之为零流弧;若,则称之为非零流弧。

介绍增广链之前,我们要引入链的概念:

设是一个给定的图,若图的一些点和边可以按照如下交错序列排列,使得,则称为中连接和的一条链,简称为链,点和称为链的端点,其他点称为的内点。我们把这条链简记为。若链中的所有点都不相同 ,则称之为初等链。若边都是不相同的,则称之为简单链。文献综述

本文所指的链都是简单链。若链连接着网络中的发点和收点,则规定链的方向是由到。这里我们按照方向又可以将链上的弧被分为两类:若弧的方向与链的方向相同,则称之为前向弧。前向弧的全体记为;若弧的方向与链的方向相反,则称之为后向弧。后向弧的全体记为。

定义 1。4。3。2  设是一个可行流,是从到的一条链,若满足下列两个条件,则称之为关于可行流的增广链。

若对任意的弧,有,即中每一条弧都是非饱和弧。

若对任意的弧,有,即中每一条弧都是非零流弧。

  (4)截集与截量

    设,我们把始点在集合中,终点在集合中的所有弧构成的集合称为弧集,记为。

定义 1。4。3。3  给定一个网络图,若顶点集合被分割为两个非空的集合和,使得,则我们把弧集称为是(分离和的)截集。

显而易见,若把一个网络图中的截集删去,那么便不存在从到的路。所以,直观上说,截集是从到的必经之道。

定义 1。4。3。4  给定一个截集,我们把截集中所有弧的容量之和称为这个截集的容量(简称为截量),记为,即

容易证明,任意一个可行流的流量都小于等于任一截量,即

显然,如果对于任意一个可行流,网络中存在一个截集,使得,那么必定是最大流,同时截集的容量也一定是的所有截集中最小的一个,即最小截集。

定理 1。4。3。1  可行流是最大流,当且仅当不存在关于的增广链。

于是有如下重要定理:

定理 1。4。3。2  最大流量最小截定理:任意一个网络图中,从发点到收点的最大流的流量等于分割和两点的最小截集的容量。

第二章 交通运输网络的图论模型建立与最大流问题

2。1 交通运输网络的图论模型的建立

2。1。1交通运输模型问题的引入 来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

  交通运输最优化要求在满足各个地区物资需求的前提下,以最少的运输费用将尽量多的物资从一个地区输送到另一个地区,要满足该要求,我们必须从三个方面考虑问题: 

   (1)满足各地区的最低物资需求; 

   (2)将尽量多的物资从一个地区输送到另一个地区; 

   (3)总运输费用最小。 

为了更好地从这三个方面处理该问题,我们先用数学语言描述它。

已知有个物资仓库。可供应某种物资,其供应量(库存量)分别为,有个销售地区,其需求量分别为。从到运输单位物资的运价(单价)为,从到道路运输能力为,从到的运量为。 

由此,我们以总运输费用最少为目标函数,以各地区物资需求量、各仓库物资库存量和道路运输能力为约束条件构建模型如下

上一篇:交通运输网路的最短路算法的优劣讨论
下一篇:C#+sqlserver安卓系统性能测试工具的设计与实现

基于Apriori算法的电影推荐

PHP+IOS的会议管理系统的设计+ER图

数据挖掘在电子商务中的应用

数据挖掘的主题标绘数据获取技术与实现

基于PageRank算法的网络数据分析

基于神经网络的验证码识别算法

基于网络的通用试题库系...

安康汉江网讯

老年2型糖尿病患者运动疗...

ASP.net+sqlserver企业设备管理系统设计与开发

我国风险投资的发展现状问题及对策分析

网络语言“XX体”研究

新課改下小學语文洧效阅...

互联网教育”变革路径研究进展【7972字】

麦秸秆还田和沼液灌溉对...

LiMn1-xFexPO4正极材料合成及充放电性能研究

张洁小说《无字》中的女性意识