我可能活不过三章 第六章6.最 大 流 问题

6-4 最 大 流 问 题;一、基本概念;求v1到v10的最大流及最大流量；求最小割集和最小割量。 ; 流：①弧上的流——网络中加在弧上的负载 量。记为fij或xij。 ②图上的流——加在网络中各条弧上的一组负载量。记为 f={f}={fij}或X={xij} ;; 3．? 割： ; 4、弧的分类在可行流X={xij}中，按流量的特征分有： ①饱和弧——xij=bij ②非饱和弧——xij bij ③零流弧——xij=0 ④非零流弧——xij 大家应该也有点累了，稍作休息;在容量网络中从起点vs到收点vt的一条链中，按弧的方向分 ①前向弧——与链的方向一致的弧。前向弧全体记为μ+； ②后向弧——与链的方向相反的弧。后向弧全体记为μ_； 其中,链的方向规定为: 从起点vs指向终点vt。;按点来分 任一顶点vi处，流入的弧称为对节点vi的后向弧，流出的弧称为对节点vi的前向弧。;5.增广链： 设χ是一可行流，μ是从起点vs到终点vt的一条链，若μ满足下面两个条件，则称μ为关于可行流χ的一条增广链： ①在弧∈μ+上， 0≤xij bij ②在弧∈μ-上， 0 xij≤bij ;二、什么是最大流问题？;;四、标记化方法 步骤与举例：;给出初始流如下 ;;?重复步骤二，但要注意把vs换成已得到标号的点；可能出现两种结局：;3．调整过程： ;用上述同样的方法对修正流量后的网络图再次进行标记化工作，得各顶点的标号如下： 起点vs，顶点v2 顶点v3、v4、v5、v6等都不能标记。因此，终点也就得不到标记，即已不存在流量修正路线。故流量修正工作到此为止。图2就是最大流量网络图，由图中可知最大流流量为20。 ;第一轮标号：得到一条增广链，调整量等于5，如下图所示;第二轮标号：得到一条增广链，调整量等于2，如下图所示;第三轮标号：得到一条增广链，调整量等于3，如下图所示

“原创力文档”前称为“文档投稿赚钱网”，本站为“文档C2C交易模式”，即用户上传的文档直接卖给用户，本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有【成交的100%】。原创力文档是网络服务平台方，若您的权利被侵害，侵权客服QQ：3005833200 电话：19940600175 欢迎举报，上传者QQ群:784321556