06 第六章 网络分析.pptx

第1页：第六章网络分析与§1引言

第六章 网络分析（Network Analysis）　网络最大流问题　§1. 问题的提出

• 交通系统：车辆流量
• 企业：物资流、信息流
• 信息系统（网络）：信息流
• 供水网络：水流量
• 金融系统：现金流

第2页：最大运输能力例题

例　产品从产地运往销售地点，图中给出了每段的运输能力，问：最大的运输能力为多少？

图中各弧的容量与当前流量标注为 (5,1)、(3,3)、(3,3)、(2,2)、(4,3)、(2,1)、(1,1)、(1,1)。

分析：方案如图所示，流量 = 3 + 1 = 4，是否为最大？

第3页：§2基本概念

§2 基本概念　本页为标题页，网络与流的相关定义（容量、流量、可行流、增广链、截集与截量等）见后续页图示。

第4页：

第5页：

第6页：

第7页：

第8页：

第9页：标号法网络图

求解用的网络图：标出发点 v_s、收点 v_t 以及中间节点 v1、v2、v3、v4 的编号与各弧容量。

本页为网络图示页，源文件文字提取有限（仅节点编号），建议对照原课件图片核对弧容量。

第10页：一、标号过程

解：一. 标号过程　从发点 v_s 出发，沿着未满容量的前向弧与有流量的后向弧逐点标号，直至标到收点 v_t（找到增广链）或无法继续标号（已得最大流）。

第11页：二、调整过程

二. 调整　沿已找到的增广链，按调整量 θ 修改各弧的流量（前向弧加 θ、后向弧减 θ），得到流量更大的可行流；重复标号与调整，直至不存在增广链，此时的流即为最大流。

第12页：

第13页：