08-图与网络 运筹学 教学课件.ppt

狄克斯屈标号法 1 4 2 3 5 6 7 7 6 3 4 2 2 4 3 5 7 1 4 2 P(0) P(5) P(3) P(4) P(8) P(7) P(10) 狄克斯屈标号法 1 4 2 3 5 6 7 7 6 3 4 2 2 4 3 5 7 1 4 2 P(0) P(5) P(3) P(4) P(8) P(7) P(10) s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 最大流问题 在一定条件下，使给定网络系统的某种流的流量达到最大的问题。 公路系统车流，水利系统水流，电力系统电流，生产系统产品流，金融系统货币流，服务系统顾客流，信息系统信息流。 网络流 给定条件： 1、网络有一个始点Vs和一个终点Vt; 2、流过网络的流具有一定的方向，一般用有向网络N=(V，A)加以描述，各弧的方向是流量通过的方向； 3、对每一对弧(vi，vj)∈A，都有一个容量r(vi,vj)=rij≥0，表示容许通过该弧的最大流量。 满足上述条件的网络称为容量网络，简称网络。 在给定条件下，流过一个网络的某种流在各边上的流量的集合称为网络流。 s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 流 s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 在一个网络N=(V，A)中，设xij=x(vi,vj)表示通过弧(vi,vj)∈A的流量，则集合 X={xij| (vi,vj)∈A} 就称为该网络的一个流 可行流 s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 静贮流量 网络中结点的总流入量与总流出量之差。 s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 最大流 前向弧后向弧 记μ是网络N中的一条从vs到vt的链，则链上与链的方向一致的弧称为前向弧，其集合记为μ+；链μ上与链的方向相反的弧称为后向弧，其集合 记为μ-。 链μ=vsv2v1v4v3vt的前向弧集合和后向弧集合是： 前向弧集合：μ+={(vs,v2), (v1,v4), (v3,vt)} 后向弧集合：μ-={(v1,v2), (v3,v4)} s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 增广链 s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 截集 在一个网络中N=(V,A)中，将点集V分成两个不相交的非空子集S1、S2，使vs∈S1，vt∈S2,且S1中的点不经过S2中的点而连通，S2中的点不经过S1中的点而连通，则把始点在S1，终点在S2中的所有弧构成的集合，成为分离vs和vt的截集，记为(S1,S2)。 s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) 截量 把一个截集(S1,S2)中所有弧的容量之和称为该截集的容量，简称截量，记为r(S1,S2)。 s 1 2 3 4 t (9,7) (5,3) (3,2) (4,4) (3,1) (5,5) (2,1) (6,3) (7,7) v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 总造价=1+4+9+3+17+23=57 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 避圈法 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17