QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1944|回复: 0
打印 上一主题 下一主题

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

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

542

主题

15

听众

1万

积分

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

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    跳转到指定楼层
    1#
    发表于 2020-5-21 09:56 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    1 最大流问题的数学描述8 [/ c$ _* ]" N* l! M- R# k
    1.1 网络中的流 定义
    & }. t1 M8 u3 n' r在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:
    , e- g0 D! {$ E' p; g! D8 K3 D1 U4 F2 e) t6 t5 f) q
    (i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);
    ! k  ], t; u6 M8 \- W& F& D  p; d% U; x
    (ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);) v9 W: t  a6 o3 d
    , ^8 e$ m9 x9 O/ {+ z" Z
    (iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为  ,称为顶 点i 的供需量(supply/demand);$ o. A- v% S" o! R- @8 l

    : _) \. {9 P8 O此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。/ H5 x  i! c1 _% Q/ f4 L7 h/ S
    9 m* D: Q4 d# f2 {
    在流网络中,弧(i, j) 的容量下界  和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。  Z2 `. {8 M9 C
    + P" B, ~6 |3 d4 o% x, X
    可行流(feasible flow)" m$ g& L; C' x4 @- H5 Q- c
    ' T- u- L/ B) M5 o( q9 ]  S3 a

    - F9 d9 t& B# Y1 u6 H# @/ k4 f* a) g/ T3 R- W
    2 J7 ^& m7 G6 g2 w0 z6 \+ a
    可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有
    ; w# w  r5 {6 G. q! c/ j" Q; f$ [, d
    2 c$ X5 K2 t  z4 g: Q/ ~: V
    . s! z- L/ [& c+ x) _* X& p
    也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件
    8 I7 M+ ~& O4 k: E
    6 a- N$ k/ `: Q& B
    6 ~2 H% C" u2 x1 U) I& a4 q; L, M& ~: d4 g. \4 C4 x
    3 A4 b1 v2 }7 w8 B' Y; z5 j
    1.2 最大流问题
    8 L" l9 L* p: N+ J考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 −  ),通常记为v 或v( f ) ,即+ G3 J" c9 t: ^9 N
    7 ~6 f6 e1 Z0 M+ X4 I

    8 X. }4 N  y2 H1 |+ R; `对这种单源单汇的网络,如果我们并不给定  和  (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。/ B, y8 a" ^/ ]0 U. P2 T

    8 B/ R2 R, R  i% [: d用线性规划描述最大流问题/ M, e& K% H+ [2 z% J
    因此,用线性规划的方法,最大流问题可以形式地描述如下:
    9 R& {1 c8 Q! u8 w4 x4 W  _, F' G: B% x3 [# R: Q

    5 a, C' J* w4 [- [3 A
    4 G; z/ F' Z9 M1 H- s定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。3 o2 y7 N' n2 O. k& n1 e( b
    9 {- }+ E- x( ?5 d, r# V, @
    整流定理0 @" `. _" `8 A; C$ \$ y
    【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。: p' `, G+ \/ l8 L0 G

    * d# g3 @- b$ P' r1.3 单源和单汇运输网络% @3 ~. D0 F8 J" u8 A
    多源多汇网络 转化成单源单汇网络3 e4 ^6 M# \: Y2 z: {" @2 k4 @
    实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:
    / N" w- d# v' @5 i6 O9 b/ m, T# R$ I2 O1 P1 Y- F
    (i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。
    # m% J' S. u, q  ?# D8 [6 ?" ~% m4 ~& z; k
    (ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。' d7 o$ E: v% E6 I

    ( }0 ?+ X# ~' d(iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由
    # i' `' n: M0 k& l2 s5 J) o% }3 B3 O' P: `- u' |! f. ?! U

    + P* T* Z$ Z" Q9 |5 S2 v! k
    5 f; x2 A" i, t2 最大流和最小割关系割的容量' h% z. C, \9 z# t
    - V* @) x- g2 \* N% P

    ' g" x% F! L" v- @% C
    ' i$ w4 F9 T; K7 [7 O/ ?+ h则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。
    ' B9 e) J# q  P- |5 V( p: j$ w- N! Z: A
    3 最大流的一种算法—标号法/ C1 s0 U- ]5 l# [% ~
    标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。. c4 ?$ O! T1 g7 Z

    + o0 ]" U% W$ T3 e这种方法分为以下两个过程:& S, F# Q, J' K0 A2 w7 u' [; x& X: w# {
    $ }/ x' K+ Y+ \: _  d
    A.标号过程:通过标号过程寻找一条可增广轨。; o5 e( P. c! A7 U
    1 j- o* o( Q, j" \
    B.增流过程:沿着可增广轨增加网络的流量。2 I: d6 X3 b" W+ S: Z1 z

    / ?( E0 O3 P: K, C$ R9 s这两个过程的步骤分述如下。* Q, @5 U" U# H% Q( p- y

    ; n' V) H: P+ D3 W$ D# q(A)标号过程:1 L' q0 K1 F+ l) \6 M
    9 {; x7 D: V& J

    4 y& p% @( {# N2 ~7 y1 W- t; n/ P0 P' d( B1 x- s9 q1 p( Z7 C6 F( ]# j
    (B)增流过程( w" Y9 ], u& \# q4 L
    * R* e  ?/ p! R4 Q' ?# ?6 t
    网络最大流 x 的求解步骤
    9 H% H, M* S, F: g' D. N求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:- x/ x! z* V" B* `

    ( f' i' P6 V# y, V  i% M  S对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j)); G! F0 b8 a8 {% \
    # c% O0 C6 C% p$ T. v+ [$ e
    该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。
    ( r- i! n/ w. k% J+ H2 P: O$ ^2 O8 A* k2 n5 F. ?& ?' _6 @; ?

    * ], b5 X7 d! D; s
    8 l% ^7 T3 r. {, @+ K

    并将 j 加入 LIST 中。

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

    $ i# K6 N, q) j5 O, t5 i

    9 Y7 K! T/ L; {; N3 V4 S1 ~! o' e+ ]. t
    解 编写程序如下:
    9 w8 [) J6 Y# O" o  y
    : |' v2 E& r( \5 O6 Z$ D# _: @4 tclc,clear& i# H3 [! s0 S+ V) _3 @$ g
    u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;
    + ~. G' j- _7 Z' vu(3,5)=1;u(4,3)=3;u(4,5)=3;* a. Z7 }/ l8 j! I  Y) y! N, U
    f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;5 }) C5 q7 j" P; n
    f(3,5)=1;f(4,3)=1;f(4,5)=0;
    / T2 f: ?$ I+ V( T: {) M- q# B1 A# hn=length(u);list=[];maxf(n)=1;/ n" S8 @3 a3 K2 [# i  @: V
    while maxf(n)>0
    - y, Q& y$ N3 j, l: \5 gmaxf=zeros(1,n);pred=zeros(1,n);
    0 G, k. R- o7 N7 s: M+ {list=1;record=list;maxf(1)=inf;% }: j8 m( `, Z% ]; j
    % list是未检查邻接点的标号点,record是已标号点
    . X9 r6 J( }. K& ~while (~isempty(list))&(maxf(n)==0), R+ |$ n) w# V  k; D7 j
        flag=list(1);list(1)=[];
    2 t- O) q8 Y: A* v/ Z4 q    label1= find(u(flag,-f(flag,);
    + Y+ a' o. @) A- c# }    label1=setdiff(label1,record);
    5 Y" c& l& D" X4 d    list=union(list,label1);9 Y6 h5 P: B. @1 E! v: D9 W/ l) e
        pred(label1)=flag;
      y3 c0 l% K+ Z. O    maxf(label1)=min(maxf(flag),u(flag,label1)...- a4 Y$ \- Z* [7 V% [
        -f(flag,label1));# M+ N6 J8 j! O. `5 F# K  f6 D* J
        record=union(record,label1);  i* ]  Y, u+ @2 u& x4 t- v
        label2=find(f(:,flag));
    3 l( ^7 _3 R( ^# \# O  J; }    label2=label2';+ X0 }5 F' B$ g! U0 t0 m
        label2=setdiff(label2,record);3 }! U3 Z; [2 e( D
        list=union(list,label2);! Z3 {2 w: o7 h1 l
        pred(label2)=-flag;
    ( z6 a( D, ]$ c. N, i( u    maxf(label2)=min(maxf(flag),f(label2,flag));& p% N0 h- Z$ M5 x; D! \4 r# p" A
        record=union(record,label2);
    ' N! h# n: C2 w, ] end
    8 ~; A# P; h7 h8 ~     if maxf(n)>0" N8 @! b% f& p/ p' |0 X3 y
            v2=n; v1=pred(v2);
      A( N; y# ^" m% d4 |  i0 [5 C        while v2~=1
    % N+ r* J, G' |* f2 E+ C            if v1>0+ K: s( h: m7 t
                    f(v1,v2)=f(v1,v2)+maxf(n);) r. o- [' f4 k9 I, S2 N2 s
                else' A* V# l6 j4 \7 ^+ M
                    v1=abs(v1);
    * L( {8 y/ Q3 D) g: U7 a                f(v2,v1)=f(v2,v1)-maxf(n);% Z+ C& }" d4 P, q+ {; }1 b
                end
    . J: l0 f' j" E3 \( H            v2=v1; v1=pred(v2);" ?! l3 \2 K; L9 U1 H) n& X
            end
    9 F8 c( q) S% S6 \  ^5 F" B0 F    end: [' U% k: U8 t2 F: T
    end% c/ i' ]/ ^" c5 M
    f , c0 s- @  k2 v5 r+ E
    例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站  v1 ,v2 ,v3 和  v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。
    + |6 C( K9 A6 C2 u! Z/ z, g) ~7 y! [2 z) n4 n' B, l" _

    8 k) f- D) R' i' r" `2 T
    % o6 m. B! L" u) Z1 q+ g% U! H& `7 z% o1 e" X8 d6 R( K+ h
    解 使用最大流的数学规划表达式,编写LINGO程序如下:
    1 z0 J$ g! Q0 e) G) I/ a% v
    0 a' u7 X7 a  g7 ]* kmodel:% I/ a* P2 F( N) ?9 S
    sets:
    - l9 R% d- p8 `/ ?/ q# l- |nodes/s,1,2,3,4,t/;  A0 @+ E  c5 z# V8 u5 h3 y
    arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;" j$ G+ ?4 v4 ]% c5 m) w
    endsets" T7 z" l" V7 M; |/ W; b
    data:
    ' m; ?- J7 i) H, u" Fc=8 7 9 5 2 5 9 6 10;* j  w& K" q" `) z3 K7 _
    enddata
    . t, c+ B( w! R3 R4 C+ A+ j8 Fn=@size(nodes); !顶点的个数;. ~6 F5 T8 J/ r  |0 ?6 C( |
    max=flow;
    8 i9 z+ D% `" N' h' `1 G# o@for(nodes(i)|i #ne#1 #and# i #ne# n:' \3 z  N, y, R  r0 W+ X0 K9 G
        @sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)
    - P& B/ c6 K) f@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
    ! F2 N4 P0 R  v4 l+ h5 \. s@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;/ o4 R/ T8 z" j
    @for(arcsbnd(0,f,c));5 v) `# l5 o' u% q! X
    end
    8 U: L$ G9 U4 @9 a. k0 f# K& c
    : ~' J& W$ j) r" P在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
    ! g6 }0 Y& e: \5 T/ Y% ^0 \2 j$ n) z: T9 k5 y+ Y+ }# S: I& d, U
    model:
    & D5 }4 Q; d& v  d! nsets:! }& ?: N6 @0 q9 b- {7 Q. e
    nodes/s,1,2,3,4,t/;
    $ ?: n  M* G3 z) @5 x0 r, V: zarcs(nodes,nodes):c,f;* \, z- K2 h; c7 R, l
    endsets
    0 _+ d6 }1 L/ E4 Mdata:
    ) n% I+ ?: G- O7 l0 cc=0;1 J" E$ @% k$ E5 G" R; R
    @text('fdata.txt')=f;% `# D. }% E* f" [2 i% Z
    enddata
    # e& }+ v6 N' a1 b8 j& wcalc:+ f: T: T! r  Q
    c(1,2)=8;c(1,4)=7;
      W% x  U- ]. I8 r2 j$ h$ @c(2,3)=9;c(2,4)=5;' B8 d4 u: |, a
    c(3,4)=2;c(3,6)=5;* l' C( G3 d9 H; c
    c(4,5)=9;c(5,3)=6;c(5,6)=10;3 C& F3 g- _$ m# V! {( S8 t
    endcalc! S& b* X) K, e4 ^0 P, S
    n=@size(nodes); !顶点的个数;5 W% c9 V1 ?! g/ h' R  M" L
    max=flow;
    , P) ]; W/ v5 b1 o, C% |( m@for(nodes(i)|i #ne#1 #and# i #ne# n:
    - X, C8 P) M7 D    @sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));, T0 \8 @' H% b' C7 |) x; b
    @sum(nodes(i):f(1,i))=flow;
    ! s4 J8 U( P/ d1 Q3 A9 z@sum(nodes(i):f(i,n))=flow;! y& `( ?  b- h2 f
    @for(arcsbnd(0,f,c));& m) E8 Q! B4 z$ y2 }
    end7 k0 i& q; R2 P1 K
    2 q& x7 _  ~& @+ O' L
    ————————————————
    / {) I3 j# R) X7 _5 u( S版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。5 d) d4 X- e- N  ~4 X
    原文链接:https://blog.csdn.net/qq_29831163/article/details/89786313. N# D( [5 F- @7 K  E; y

    . m& T7 R1 [: l" ?9 h5 e6 B2 k( d6 ?4 E0 A
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2026-4-20 19:38 , Processed in 0.444183 second(s), 51 queries .

    回顶部