请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1322|回复: 0

常用模型&算法总结—图&网络模型应用—树:连通性、最小生成树

[复制链接]
字体大小: 正常 放大
浅夏110 实名认证       

542

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2020-11-14 17:15
  • 签到天数: 74 天

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    发表于 2020-5-21 09:56 |显示全部楼层
    |招呼Ta 关注Ta |邮箱已经成功绑定
    1 最大流问题的数学描述! O8 y! ^! Q  O- V0 ^+ y/ P
    1.1 网络中的流 定义
    2 d" o- j: Q& K+ J3 b0 w在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:
    # I' N) B2 l9 c! U6 h4 A/ }% S
    $ F2 v- ]+ _1 P. w% x4 m(i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);$ c+ ^- G+ l. `5 g

    ; I# r8 y& V( H+ V(ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);  ]" C' r  f7 \  ^* J
    * K4 `- x, p- H( ~4 t) N6 e
    (iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为  ,称为顶 点i 的供需量(supply/demand);1 J( q  I, _4 [- O  m2 J
    / }- p) ~+ L! G0 W' t
    此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。" ~- e* t! q3 U5 V- I) G7 ]

    ( x8 s$ s! A; x1 x+ }0 O; g在流网络中,弧(i, j) 的容量下界  和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。6 T, e7 W+ W2 W( R7 X0 Z% {3 c
    + Z! Q4 e( p1 ?- m* f
    可行流(feasible flow)3 g1 H7 D8 d  m3 [  U5 G7 K* X) M5 X$ N
    / b- z9 I, D' h, p
    9 F+ h& v6 j# X3 s
    0 D1 A! K1 X1 h
    - N( j+ P$ }, X; N2 j; P
    可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有
    5 ?; M4 N% N5 j+ a) \" v( J( N" q8 W; p6 h3 h6 @

    ' [# Q) d/ M. [7 `8 f
    * M! S2 _: U# w7 F( \也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件8 W! Y& [% s8 q2 V2 D- N1 ?( W2 L

    , |1 g9 v6 Z2 q; g6 C; F7 I; ?# I
    - y2 y; M% X$ d( u, J" G
    9 x  z+ H. T% L! Y+ h/ o$ c+ B4 D6 _
    1.2 最大流问题
    6 Z! y& p' I4 P6 q! e3 P8 b0 Y考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 −  ),通常记为v 或v( f ) ,即$ j5 S: x2 p7 d

    1 @6 F# `% S. v
    , ~) A, d6 k6 G* D- `2 ?: ~对这种单源单汇的网络,如果我们并不给定  和  (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。
    % u1 c% X1 }9 k. K* }+ o+ B) i% o& v
    用线性规划描述最大流问题4 l3 c0 I$ Z) a. Q% Y, h
    因此,用线性规划的方法,最大流问题可以形式地描述如下:2 Z2 e/ r( Z8 I' ?
    , p  o9 p0 h0 o

    1 c- o* n2 n0 F: P3 W5 u. G2 D' n2 d: I; x
    定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。& c$ v0 q* K# `7 \9 V, C

    1 v+ x. J, j8 o- f7 ~整流定理) K) u! C5 c7 r+ a5 O! {! g4 A  y
    【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。
    / x* t9 [5 I, I9 ?5 j* h. E( z+ O8 v9 x  I9 G
    1.3 单源和单汇运输网络
    " ^; ?8 e7 H9 n: Y* i多源多汇网络 转化成单源单汇网络
    : M2 l, ~! }6 ~% Q. w8 T实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:
    9 j1 U/ N8 r, o! r2 z3 b- w$ `/ T1 @9 M+ ^
    (i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。3 U' G( t/ V6 d' b" o9 {' k# i. a, q) E

    & m7 {/ d5 ~  P7 j(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。
      a2 P7 U. o: {! v% E2 Y& o3 V, r) ~4 t2 f; V0 e, ]
    (iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由4 b+ p5 _$ D  k+ I/ V: z
    2 Q$ U# b7 s; W: L& ^

    " h! Q* H, o6 w4 S) }( J) N6 g( F6 M; ~0 x
    2 最大流和最小割关系割的容量
    5 L0 W0 k( _1 C2 X; T" w% `5 _: f  l# B# ~

    ) h$ e9 {$ A7 S4 k5 r2 u# x
    % [" ^" _# z1 P1 B) |% ~则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。( A% z" x- K1 S" w
    . z. G$ ~' G+ m# L4 b% o
    3 最大流的一种算法—标号法- r8 m, Y8 E3 Q1 k2 |
    标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。* D* `3 [* _9 q7 L
      p* `  z. d: `% m* [- R0 w" c6 Q
    这种方法分为以下两个过程:: i; w% q- \2 S4 O
    ; O4 W) W; Q! u. L) Z" U
    A.标号过程:通过标号过程寻找一条可增广轨。
    9 O  j3 `4 X% k% B
    8 S! {/ L- f" G0 Q7 u: XB.增流过程:沿着可增广轨增加网络的流量。# c0 j* o" `3 S) z
    6 `% j$ C2 m, y2 F! t7 _
    这两个过程的步骤分述如下。( z0 i3 p6 h) L9 P. P$ `& n

    4 v" q  @( v7 W: X. ?) W* @' A(A)标号过程:
    $ N9 d$ e. g3 G$ u" S' f
    2 Q9 g7 u1 g: |6 c3 D9 J
    8 K, R- N9 Y- }% m% a# t. }& r9 q6 |7 \) e- z+ a8 R9 j7 _. E
    (B)增流过程
    6 h4 ~( O% W. B" V2 a/ \
    0 y1 ?- g; A* i* G( F网络最大流 x 的求解步骤
    . x1 b+ G. @2 `5 b1 I" L求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:
    5 _+ q9 H: S8 x4 M6 G& X7 q6 v) o3 [8 r% j7 s& r
    对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j))& ^; R) B+ y. D+ R9 w/ g$ i- c) ?
    + g! e9 `; s& E; M
    该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。
    4 q  d7 S) }# t% S3 c2 \) C: e$ M  O* I" O
    ' I# p( Y: f) S% ?( c4 s

    6 a4 G# T* F$ J9 v- J9 L9 E

    并将 j 加入 LIST 中。

    例 17 用 Ford-Fulkerson 算法计算如图 6 网络中的最大流,每条弧上的两个数字分 别表示容量和当前流量。


      U0 I; E* b  Z; E% m6 {0 s. P2 v/ H  X: o
    ! ]6 a6 `* x) F3 u3 ^5 t8 }5 \6 x% @' i4 r
    解 编写程序如下:/ D- [3 ?* `1 c6 M( a% C
    / ^/ d7 T$ t/ Z/ l8 n; ?
    clc,clear' R5 G9 S( L+ p3 I  c
    u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;  |" M; J! k6 W
    u(3,5)=1;u(4,3)=3;u(4,5)=3;' S2 P* ~4 a  [6 t* \' t! S$ {
    f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;  n+ G" _7 q& l- W
    f(3,5)=1;f(4,3)=1;f(4,5)=0;, c: P: r& G! p4 b
    n=length(u);list=[];maxf(n)=1;3 @0 m. u7 W+ F9 {1 @- ?
    while maxf(n)>08 u7 C9 @9 N. o: Q- ~+ F
    maxf=zeros(1,n);pred=zeros(1,n);4 t! N0 b0 _6 t0 `) Q2 a+ _
    list=1;record=list;maxf(1)=inf;: o! e# |; v9 U9 q# q; m! \
    % list是未检查邻接点的标号点,record是已标号点
    - U# ?2 g% G, e" t* g0 L. Nwhile (~isempty(list))&(maxf(n)==0), z! V) N7 G# ?7 l- {) n
        flag=list(1);list(1)=[];! ]% e  ^( f6 \9 k4 p2 A
        label1= find(u(flag,-f(flag,);
    , i+ g5 [7 Z7 D, y. ]    label1=setdiff(label1,record);7 W( b) D8 _+ e. R
        list=union(list,label1);
    ' [/ h: n' k3 w& o4 I0 A; X9 j2 ?1 T    pred(label1)=flag;
    , L# G  T8 T, s6 C    maxf(label1)=min(maxf(flag),u(flag,label1)...
    2 D$ [  _8 b3 q; D: ~    -f(flag,label1));
    0 W  F  H; P4 h, u+ r2 E    record=union(record,label1);& I7 \3 b, h* p6 r! ^6 K
        label2=find(f(:,flag));
    ( p) x  A( l) P! W% S    label2=label2';8 Y! W5 ~8 M& `/ V8 l: M- Q, T
        label2=setdiff(label2,record);2 O2 O5 n0 g$ @8 J( ?/ M; y, h
        list=union(list,label2);
    ' v& g  g: V7 Y5 {8 e" t; Q    pred(label2)=-flag;' S  `! B8 n: V% R" a
        maxf(label2)=min(maxf(flag),f(label2,flag));" C' {) ]9 _8 M) d7 G& G/ ?& |
        record=union(record,label2);
    3 T. y5 o% z" c9 n8 ]+ W end
    9 X  }. T2 C1 ~, J1 w, I6 S/ Q. R     if maxf(n)>0% w" p  Y9 ^; ?/ F# f) c; O
            v2=n; v1=pred(v2);0 T1 E8 E+ _) s, e* p. o: Y1 l2 x
            while v2~=12 O$ @% \8 |: ?
                if v1>0" k. z. H3 d4 O; E! m
                    f(v1,v2)=f(v1,v2)+maxf(n);
    8 F# B; T2 r3 G7 e6 Y: }2 j% p            else" ]* q: K7 a7 `* L' M2 K% T4 D
                    v1=abs(v1);$ ]# d- w/ s$ u8 j7 ]' {. J8 }
                    f(v2,v1)=f(v2,v1)-maxf(n);6 e( h- I/ X9 N( q' l( S
                end) ?) |. X6 Q& Q* x2 {, u
                v2=v1; v1=pred(v2);
    ) C- r1 |9 T7 [; q" y        end
    . u8 B( w2 j" \% ~    end8 y: ~0 [+ ~0 k9 ?& P: z
    end
    " E# t* V& `4 k& u5 Z' J. A. Ef . P* y$ a* L* w4 `
    例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站  v1 ,v2 ,v3 和  v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。
    7 y' V5 Y2 ^' v5 k. Y; G4 P5 o
      a) H* U9 v2 Y+ g8 B
    1 z3 d& G' q5 \# K& ]; c' D/ B5 x, n9 M2 b8 i1 W9 k, x% g$ J( I

    # U0 U  G: s1 q0 h; b2 Y* L5 [8 W8 K, f解 使用最大流的数学规划表达式,编写LINGO程序如下:
    ! b3 J0 }& F- _4 ]( U$ L" z/ ?& C0 e% r# f9 A1 `) E
    model:3 r9 C2 ~, f1 u/ K
    sets:- k$ ~, i' V! c7 c
    nodes/s,1,2,3,4,t/;, i  d4 M3 m+ \- `7 D* v
    arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;
    2 P" a3 z! Y8 R' T+ F  ]endsets  i& x9 E$ L. S0 r7 W
    data:8 @$ _  N) z; `* q
    c=8 7 9 5 2 5 9 6 10;
    / D# g5 S2 X/ g/ W9 Aenddata
    : R4 {) Q% M4 i3 W, cn=@size(nodes); !顶点的个数;
    + c% K, M# [& `' x2 hmax=flow;
    5 _4 P1 l, j2 t5 `% N@for(nodes(i)|i #ne#1 #and# i #ne# n:
    4 }5 D8 ?+ [! w  \) Q" Z' N4 D; y    @sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)
    1 J% D6 L6 ~; w' @, V$ S. v7 y@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
    6 W6 M) k. o7 B* _9 b6 B@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;
    5 ^$ }# `' g1 C3 T" g. E@for(arcsbnd(0,f,c));
    . D6 d& Z. r1 P; H$ ?& ]0 Kend 4 O# |0 q7 z/ C/ j

    ) t6 T8 Y4 K9 o% f在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
    , Z, j2 ?' l% J4 A+ [6 g7 P# t  K5 Z  _+ }, D0 H9 R4 {5 r
    model:
    2 h5 X  V4 h5 c" _3 f! J5 L; bsets:& p9 l* {  ^$ v$ w2 s
    nodes/s,1,2,3,4,t/;7 u% k& |# e8 v7 V' Q6 S$ H7 @
    arcs(nodes,nodes):c,f;
    2 D  _- l5 j; \2 }/ uendsets" h, f9 ]) G# @! j; N0 Q  \
    data:. v0 U) i- z  H% [" l$ X& b
    c=0;6 C1 w. U. r( ?; R
    @text('fdata.txt')=f;
    ( r; F  w4 @0 W, e1 zenddata( z' ?5 f% U' w3 V5 \9 J) {% U
    calc:; ^9 p1 j! D' |9 E% `1 g
    c(1,2)=8;c(1,4)=7;
    - B& h8 K0 k0 U8 Ac(2,3)=9;c(2,4)=5;& j' a9 w9 E. \/ h. ~1 z" S6 |
    c(3,4)=2;c(3,6)=5;5 v9 `+ O4 I% E+ e: B3 ~
    c(4,5)=9;c(5,3)=6;c(5,6)=10;  U4 l2 A' \1 f8 f4 R/ P; E9 D3 o
    endcalc
    7 _1 T7 G3 }+ `/ W9 Zn=@size(nodes); !顶点的个数;7 ?: V! p- ?7 E: {+ l
    max=flow;
    1 j5 v3 r5 Y/ r/ q# y  |@for(nodes(i)|i #ne#1 #and# i #ne# n:) y3 M; C8 U& {4 R) H
        @sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));
    . e+ I# b6 t) a3 H/ u@sum(nodes(i):f(1,i))=flow;4 B6 h( e& u7 v1 P
    @sum(nodes(i):f(i,n))=flow;
    " T+ y/ c- t6 M3 l! N9 `; f3 N@for(arcsbnd(0,f,c));
    - \! W$ [: }4 ]end2 |- u. M/ _& [: h  p; [9 v

    # g4 A0 L4 Y& r% d$ z————————————————
    0 e$ s) l- K/ J" P! i' w4 }版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    ( i( ?1 ~* {. B, D* `# [  `* a: X原文链接:https://blog.csdn.net/qq_29831163/article/details/89786313
    " f8 _( \' V8 p7 N, E: O6 d
    $ u% w0 ?7 z, J" w6 }! ~& x3 u' |# D* o
    zan
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-28 23:15 , Processed in 0.408160 second(s), 51 queries .

    回顶部