[数学]运筹学第10章.ppt

图论(Graph Theory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。 随着电子计算机的蓬勃发展，图论不仅得到了迅速发展，而且应用非常广泛。它直观清晰，使用方便，易于掌握。 应用领域：物理学、化学、控制论、信息论、管理科学、通信系统、交通运输系统、建筑、计算机科学、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。 网络规划是图论与线性规划的交叉学科,具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等. ● s t v1 v3 v2 v4 8(8) 9(5) 5(5) 10(9) 6(0) 2(0) 9(9) 5(2) 7(6) (∞) (1) (1) (1) (7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。 ε(2)=min{∞,1}=1 ε(1)=min{1,2}=1 ε(3)=min{1,4}=1 网络最大流 例6.9 求下图s→t的最大流，并找出最小割 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(4) 3(2) 1(1) 4(3) 3(2) 5(3) 4(2) 2(2) 7(6) 8(3) ● 网络最大流 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(4) 3(2) 1(1) 4(3) 3(2) 5(3) 4(2) 2(2) 7(6) 8(3) ● 解: (1) 在已知可行流的基础上，通过标号寻找增广链。 (∞) ε(2)=min{∞,6}=6 (6) ε(3)=min{6,2}=2 (2) ε(t)=min{2,5}=2 (2) 存在增广链s→v2→v3→ t 网络最大流 (2) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(4) 3(2) 1(1) 4(3) 3(2) 5(3) 4(2) 2(2) 7(6) 8(3) ● (∞) (6) (2) (2) 网络最大流 最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。 (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 v(f)=7. 网络最大流 割与割集 割是指容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。 网络最大流 (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 割集 网络最大流 网络的割集有多个，其中割集容量最小者称为网络的最小割集容量(简称最小割)。 (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 网络最大流 如下图中，AA′将网络上的点分割成 两个集合。并有 ，称弧的集合{(v1,v3),(v2,v4)}是一个割，且 的流量为18。 ● s t v1 v3 v2 v4 8(8) 9(5) 5(5) 10(9) 6(0) 2(0) 9(9) 5(3) 7(6) A A’ B B’ 网络最大流 定理1 设网络N中一个从 s 到 t 的流 f 的流量为v(f )， (V, V′)为任意一个割集，则 v(f ) = f (V, V′) ? f (V′, V) 推论1 对网络 N中任意流量v(f )和割集 (V, V′)，有 v(f ) ? c(V, V′) [证明] w= f(V, V′) ? f(V′, V) ? f(V, V′) ? c(V, V′) 推论2 最大流量v＊ (f )不大于最小割集的容量，即： v＊ (f ) ? min{c(V, V′)} 定理2 在网络中s→t的最大流量等于它的最小割集的容量， 即： v＊ (f ) = c ＊(V, V′) 网络最大流 增广链 在网络的发点和收点之间能找到一条链，在该链上所有指向为s→t的弧，称为前向弧，记作μ+,存在fc；所有指向为t→s的弧，称为后向弧，记做μ－，若f0，则称这样的链为增广链。 定理3 网络N中的流 f 是最大流当且仅当N中不包含任何增广链 网络最大流 一个可行流 f ={ fij }， 称 fij= cij 的弧为饱和弧，称 fij cij 的弧为