衡水网站建设费用,网站中文域名怎么做,专门做墓志铭的网站,灵璧县建设局网站系列文章目录
【管理运筹学】第 7 章 | 图与网络分析#xff08;1#xff0c;图论背景以及基本概念、术语、矩阵表示#xff09; 【管理运筹学】第 7 章 | 图与网络分析#xff08;2#xff0c;最小支撑树问题#xff09; 【管理运筹学】第 7 章 | 图与网络分析#xf…系列文章目录
【管理运筹学】第 7 章 | 图与网络分析1图论背景以及基本概念、术语、矩阵表示 【管理运筹学】第 7 章 | 图与网络分析2最小支撑树问题 【管理运筹学】第 7 章 | 图与网络分析3最短路问题 【管理运筹学】第 7 章 | 图与网络分析5最小费用流问题及最小费用最大流问题 文章目录 系列文章目录引言四、最大流问题4.1 有关概念与定理4.1.1 基本概念4.1.2 有关定理 4.2 寻找最大流的标号法 写在最后 引言
承接系列文章这一节主要来学习最大流问题。
生活中有许多流量问题例如公路系统的车辆流、控制系统的信息流和金融系统的现金流等等。对于这类包含了流量问题的系统我们往往要在现有系统容量的约束下求出系统的最大流。 四、最大流问题
4.1 有关概念与定理
4.1.1 基本概念
定义 1 —— 对于网络 G ( V , A , C ) G(V,A,C) G(V,A,C) 在弧集合 A A A 上的一个函数 f { f ( v i , v j } f\{f(v_i,v_j\} f{f(vi,vj} 称为网络流 f ( v i , v j ) f(v_i,v_j) f(vi,vj) 为弧 a i j a_{ij} aij 上的流。 c i j c_{ij} cij 为弧 a i j a_{ij} aij 所能通过的最大流量。
定义 2 —— 满足下列条件的网络流 f f f 称为可行流。
1容量限制条件。即每条弧上的流量满足 0 ≤ f ( v i , v j ) ≤ c i j . 0 \leq f(v_i,v_j) \leq c_{ij}. 0≤f(vi,vj)≤cij.
2平衡条件。对于中间点流出量和流入量相等。对于起点记所有从起点流出的流量减去流进起点的流量为 V ( f ) V(f) V(f) 对于终点所有从终点流出的流量减去流进终点的流量为 − V ( f ) . -V(f). −V(f). V ( f ) V(f) V(f) 即为可行流 f f f 的流量即起点的净输出量或终点的净输入量。
可行流总是存在的如所有弧的流量 f i j f_{ij} fij 均取 0 就是一个可行流 V ( f ) 0. V(f)0. V(f)0.
定义 3 —— 网络中可能会有多条可行流其中流量最大的可行流我们称为最大流。
设 μ ( x , ⋯ , u , v , ⋯ , t ) \mu(x,\cdots,u,v,\cdots,t) μ(x,⋯,u,v,⋯,t) 是网络 G G G 中的一条初等链各个顶点均不相同定义链的方向为 x → t x\to t x→t 。若链上有弧 ( u , v ) (u,v) (u,v) 的方向与 μ \mu μ 的方向一致称其为前向弧所有前向弧记为 μ \mu^ μ 。若链上有弧 ( v , u ) (v,u) (v,u) 的方向与 μ \mu μ 的方向相反称其为后向弧所有后向弧记为 μ − \mu^- μ− 。
对于一个可行流 f { f i j } f\{f_{ij}\} f{fij} 我们把网络中使 f i j c i j f_{ij}c_{ij} fijcij 的弧称为饱和弧使 f i j c i j f_{ij}c_{ij} fijcij 的弧称为非饱和弧把 f i j 0 f_{ij}0 fij0 的弧称为零流弧 f i j 0 f_{ij}0 fij0 的弧称为非零流弧。
定义 4 —— 设 f f f 为一个可行流 v s v_s vs 是网络起点 v t v_t vt 是网络终点 μ \mu μ 是从起点到终点的一条链若 μ \mu μ 满足下列条件
1所有前向弧均为非饱和弧。2所有后向弧均为非零流。
则称 μ \mu μ 为关于可行流 f f f 的一条增广链。
定义 5 —— 对于有向网络 G ( V , A , C ) G(V,A,C) G(V,A,C) 若 S S S 为 V V V 的子集 S ‾ V − S \overline{S}V-S SV−S 则称弧集合 ( S , S ‾ ) { a ∣ a ( u , v ) , u ∈ S , v ∈ S ‾ } (S,\overline{S})\{a|a(u,v),u\in S,v\in\overline{S}\} (S,S){a∣a(u,v),u∈S,v∈S} 为网络 G G G 的一个截集并将截集中所有弧容量之和称为截容量简称截量。所有截集中截量最小的称为最小截其容量为最小截量。
感觉这不就是割集的意思嘛不过是在有向图中。比如下图如果 S { v 2 , v 3 , v 4 , v 5 , v 6 } S\{v_2,v_3,v_4,v_5,v_6\} S{v2,v3,v4,v5,v6} 截集为 { ( v 2 , v 1 ) , ( v 3 , v 1 } \{(v_2,v_1),(v_3,v_1\} {(v2,v1),(v3,v1} 。不能加上 ( v 1 , v 4 ) (v_1,v_4) (v1,v4) 它不是这个截集中的因为它的起点不在集合 S S S 中。 4.1.2 有关定理
定理 1 —— 若 f ∗ f^* f∗ 是网络 G ( V , A , C ) G(V,A,C) G(V,A,C) 上的可行流则可行流 f ∗ f^* f∗ 为最大流的充要条件为 G G G 中不存在关于 f ∗ f^* f∗ 的增广链 μ \mu μ 。
定理 2最大流量、最小截量定理 —— 任一网络 G ( V , A , C ) G(V,A,C) G(V,A,C) 中从起点 v s v_s vs 到终点 v t v_t vt 的最大流的流量等于分离 v s v_s vs 与 v t v_t vt 的最小截集的容量。
4.2 寻找最大流的标号法
寻找最大流的标号法是由 Ford福特和 Fulkerson福克尔逊首先提出来的所以又称 2F 算法。
2F 算法可以分为两大过程。首先是标号过程检查是否存在增广链如果不存在现行流就是最大流否则进入调整过程也叫增值过程。标号与调整过程如下。
1标号过程
先给起点 v s v_s vs 标上 ( 0 , ∞ ) (0,\infty) (0,∞)不断其它点 v i , v j v_i,v_j vi,vj 包括后向弧此时有下列两种情况
在前向弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上若 f i j c i j f_{ij}c_{ij} fijcij 则给 v j v_j vj 标号 ( v i , l ( v j ) ) (v_i,l(v_j)) (vi,l(vj)) 。其中 l ( v j ) m i n { l ( v i ) , c i j − f i j } l(v_j)min\{l(v_i),c_{ij}-f_{ij}\} l(vj)min{l(vi),cij−fij} 。在后向弧 ( v j , v i ) (v_j,v_i) (vj,vi) 上若 f j i 0 f_{ji}0 fji0 则给 v j v_j vj 标号 ( − v i , l ( v j ) ) (-v_i,l(v_j)) (−vi,l(vj)) 。其中 l ( v j ) m i n { l ( v i ) , f j i } l(v_j)min\{l(v_i),f_{ji}\} l(vj)min{l(vi),fji} 。
重复上述步骤一旦终点 v t v_t vt 得到标号表明得到一条增广链进入调整过程。
若标号过程进行不下去则算法结束此时可行流即为最大流。
2调整过程
首先根据各点标号进行回溯找出增广链。增广链的调整量 θ \theta θ 为终点 l ( v t ) l(v_t) l(vt) 。 令 f i j ′ { f i j l ( v t ) , ( v i , v j ) ∈ μ f i j − l ( v t ) , ( v i , v j ) ∈ μ − f i j , e l s e f_{ij}\begin{cases} f_{ij}l(v_t), (v_i,v_j)\in \mu^ \\ f_{ij}-l(v_t), (v_i,v_j)\in \mu^- \\ f_{ij}, else\\ \end{cases} fij′⎩ ⎨ ⎧fijl(vt),fij−l(vt),fij,(vi,vj)∈μ(vi,vj)∈μ−else 即现行流中的前向弧加上调整量后向弧减去调整量现行流外的流量不变。
对新流 f i j ′ f_{ij} fij′ 重新进行标号过程。 写在最后
最大流问题相较于之前的最短路还是较为简单些的不过这只是一个载体后面结合了最小费用流可就不简单了。
