QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1972|回复: 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 最大流问题的数学描述
    6 T' Z- {" G# B7 _) j" K% _1.1 网络中的流 定义' T! ]: t0 E8 I7 V
    在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:9 }4 g6 H, M8 N* Q  h* N; \
    - Y" K1 a5 N6 u1 h0 G( K0 @. J
    (i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);) E/ P9 U9 G! M
      p- D3 h/ V& a, I3 W" w. `
    (ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);
    ! H8 O0 m  r% m9 g. l9 z! f
    ' N3 `% i% |) a2 I2 U5 h(iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为  ,称为顶 点i 的供需量(supply/demand);+ k1 w, i& \' d

    7 t% Q6 f+ a# A此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。" ?# R$ f, v; Y- K! E

    ; W% M  A* G4 d% E% Y在流网络中,弧(i, j) 的容量下界  和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。
    , t0 s6 g+ i- b2 I+ W6 V/ A
    & |* g" U* S8 g- X  J1 N( g可行流(feasible flow)& E* a- J& l! f  |

    : \8 @! U) p* u, n3 ?2 G+ o- {  ^8 g7 U

    ! J1 G& T" G+ F. v' j( S$ S* C+ x( @
    可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有; p0 D# x7 {* B: k, _& A4 V

    , S1 G1 J# h+ _  r8 k& S# K
    " _" q2 ], F; N: ^! ]$ d$ F) R; d! m. n  n
    也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件
    + ~) V# I9 j  R+ ]* S4 a  X6 z8 v* t! N

    . W' R& D& O# k) E0 A! ?0 G( R( C4 Y2 i" S0 z2 [
    - C4 a- G0 a0 ~: X( E- E
    1.2 最大流问题: J) S* y( ~  I  \% X' ?  S
    考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 −  ),通常记为v 或v( f ) ,即
    1 s: S: s0 c" i4 O( o
    6 C7 b3 h7 z( s: s6 L- i- b) P3 k8 c' Z$ u% \
    对这种单源单汇的网络,如果我们并不给定  和  (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。
    8 k. o% F3 D3 B; z8 x6 J
    & K2 ]5 k$ l+ |  z用线性规划描述最大流问题6 B1 y8 S  F. M% Z5 ]7 V4 W
    因此,用线性规划的方法,最大流问题可以形式地描述如下:
    / h: ]/ @0 A6 O; o; r* g2 c; x
    ! l/ d2 j* o2 E% z+ u: F
    , R$ ]$ \' X, L: M3 A7 n: b5 B9 p# P0 Z
    定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。
    * D* X7 D# O3 ^
    & H8 n$ N1 V+ u, ~2 C8 d整流定理
    ( K/ z' d9 V9 v- @+ P7 R& b7 P【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。0 A% L% i* p, l' n  {
    6 N; W0 \  F5 ]  g$ Z$ |# a0 `; q" ~
    1.3 单源和单汇运输网络
    ' t' ?0 ]4 _8 M  L多源多汇网络 转化成单源单汇网络- Z1 g' J; K/ r/ q" T3 ]
    实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:+ G6 z: V4 j# ?7 N1 @8 O1 I

    - {7 e3 Q/ M" B" |0 f(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。
    2 s- t) c$ }; Q4 I% ?: V
    : K3 M; U% q$ x# }- z0 o(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。' T4 Z' _3 @4 {9 l( e6 ?% `" d0 n; B8 ]
    2 V+ I# t2 o" l
    (iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由/ ~. Y7 c/ X* N/ v& f+ V( A' w

    # J8 W6 n/ U% @: P3 Z% W& g/ [0 ], u' i- [

    * ^( c* W+ X( s8 S2 最大流和最小割关系割的容量
    ' G% j* ~: T* M0 {$ v9 h. B: h. z9 u( p% z2 X0 I2 F
    1 ?/ v  ~  m  {# ^3 k2 Z
    " P7 i7 U, L7 d0 v
    则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。
    " B2 f. Q2 f( N4 u
    " c4 u3 R3 u# Z0 Y3 L0 i3 c3 最大流的一种算法—标号法' @) [9 A% c! o
    标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。' t* \, d/ Q; U$ @4 K
    ' H) e9 x# T% |5 b
    这种方法分为以下两个过程:  @3 c! G: m; G: g) J

    & y% Z3 |7 e* j0 a! A% uA.标号过程:通过标号过程寻找一条可增广轨。6 a) P  U( U+ [% Y( \
    " d- R- x+ V7 Q- v6 a0 {3 w& w
    B.增流过程:沿着可增广轨增加网络的流量。
    + @4 y  S4 p! E& Z
    6 i2 T3 i2 u( V9 g: W0 j( |% ^  N7 `这两个过程的步骤分述如下。& M* U# r- k, U" k# o- u# i; H

    ' t7 X. o! ]" {+ m8 G- l(A)标号过程:
    / q+ t: L' l( Y, l. l3 Y) a" [5 J3 d" x0 ~# X
    / F- }$ D0 W% b# @* L! s& g3 @5 f
    3 h* K1 N! z% C- ~0 i  m8 s% T
    (B)增流过程
    7 ^* ]. X9 P) \5 z$ x0 X0 Y4 ~* I- ]( `: e3 Y
    网络最大流 x 的求解步骤
    # D7 @: ?  K7 a1 B/ n  d求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:
    + ?0 Y% p4 Q5 C* P- F: Y6 z7 Q) i' U) w* ]4 d# @( X
    对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j))- R, d4 C8 Z. o* E, `

    5 u$ r, ~+ N+ w1 Y  j该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。
    ) T& y; `. v& n) s
    , @" n1 B- D5 x' O  J# ]9 d# \2 {' F1 V( c; s0 ?5 V

    # G: w- V7 D# `6 E/ u1 o& |

    并将 j 加入 LIST 中。

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

    : J7 w7 L+ b. d/ L: j" j
    $ N1 K) G) j7 e6 e

    . p$ b  E7 K: j解 编写程序如下:& ?- m) ?4 i1 r* d: {+ _8 Y

    ! {; ?$ |: o% K9 r" V. [# h1 N0 Q; uclc,clear
    4 ^) @7 i8 Y; p& du(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;6 y! e; F, \, u. W* C
    u(3,5)=1;u(4,3)=3;u(4,5)=3;7 |! X+ H$ \& J8 }) M7 _
    f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;
    5 e7 A0 b( |) Nf(3,5)=1;f(4,3)=1;f(4,5)=0;
    # \0 B/ f+ x! a; n* ]" Rn=length(u);list=[];maxf(n)=1;
    8 n' H  S  ^: {while maxf(n)>0) S! x, i7 x5 d3 e
    maxf=zeros(1,n);pred=zeros(1,n);* J5 Z. p- Y' A( O$ p: ^
    list=1;record=list;maxf(1)=inf;( H7 N7 v3 j, q: m9 O$ F8 y
    % list是未检查邻接点的标号点,record是已标号点7 e$ W4 Z2 n$ j! K' r
    while (~isempty(list))&(maxf(n)==0)
    5 \! I0 d& c5 U: m3 {2 ]    flag=list(1);list(1)=[];
    * l4 a9 G* c( O% z    label1= find(u(flag,-f(flag,);
    7 i% e% P! C2 _    label1=setdiff(label1,record);  v5 X+ Q: I: |8 L  ~: U  k
        list=union(list,label1);7 u8 a: d1 S' A# ~7 \+ p' F* \
        pred(label1)=flag;( k( V: q  U9 f) ^; j
        maxf(label1)=min(maxf(flag),u(flag,label1)...
    ' y0 t) S* ^, O) A    -f(flag,label1));% q7 b$ F$ G  [
        record=union(record,label1);
    # t* ^% C  S& r3 }    label2=find(f(:,flag));
    - d8 \* r$ z" q! a! w% O* h6 c    label2=label2';
    ! s7 p' l" o# e1 J, W- f    label2=setdiff(label2,record);" X' l2 V! v$ e
        list=union(list,label2);
    1 w6 Q- _: ^0 X9 l6 ?! E    pred(label2)=-flag;
      `% w1 V0 k: J3 h' O    maxf(label2)=min(maxf(flag),f(label2,flag));* {5 E  {6 K8 R1 I' R
        record=union(record,label2);
    7 z2 @( Z% c* Q! S8 y6 |$ b end+ N- k3 e8 v& _' o, `- D7 t% I
         if maxf(n)>0+ I$ C& X! l6 E; [: v, Q7 ^
            v2=n; v1=pred(v2);; h, p$ z- l1 |- g$ ^5 k- c
            while v2~=1- d% y8 V6 |1 e1 T  g, D6 e' c
                if v1>09 \# r" ]+ H3 l1 t3 Y
                    f(v1,v2)=f(v1,v2)+maxf(n);
    5 Z2 `1 I! [5 y# l, Y, @  O" \& ?            else. k. |( F; ~. E6 n6 c9 F( E
                    v1=abs(v1);
    : y8 N! ?. ^8 K- Q# A                f(v2,v1)=f(v2,v1)-maxf(n);+ ~- w$ K/ k+ J: i0 J- X
                end) e! T! }0 F% ]2 _- @3 |( d
                v2=v1; v1=pred(v2);1 Y9 R1 s  N. p
            end  \4 Y( D/ ^. L* ^5 B& F8 y
        end
    ' |3 ~! {8 t& S# vend
    & Z# I0 M" c0 sf
    ; u; e* w9 W- w  W5 ~" m例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站  v1 ,v2 ,v3 和  v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。5 x% q6 c1 J9 I& M3 c
    2 m; q$ j& u) E+ ~
    ( J6 Q' t$ @0 \4 I
    . c! b; _# g, |# N9 ?

    * ^3 o, A1 U5 R8 G) n0 p% S解 使用最大流的数学规划表达式,编写LINGO程序如下:$ q8 r0 J: i3 Q$ `! I3 o! o& i: `$ a

    ; e% Y# m8 i2 _& c! ?9 dmodel:- V; q6 Y2 H1 s3 K0 |
    sets:
    3 S! o! B  ~% U. ^7 qnodes/s,1,2,3,4,t/;. u5 o/ P! f& F! z8 \0 Y* x) V
    arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;
    / _& p2 `: T: {+ vendsets
    8 B: L  M% A! n1 i6 W' kdata:
    " N% T8 [' A/ V+ K/ ?c=8 7 9 5 2 5 9 6 10;
    ; t& J( a  Z3 _5 Z5 henddata" [$ w, M7 R7 l) C# I7 J, L; s5 v
    n=@size(nodes); !顶点的个数;5 y+ l9 Z+ \& L- ~1 z: {
    max=flow;$ {5 ]3 F# s8 H7 ?
    @for(nodes(i)|i #ne#1 #and# i #ne# n:
    , X( N' A) [$ L5 i    @sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)9 Z/ O; u2 I. |0 v: ^
    @sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
    / w: g7 g" S5 E@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;
    , r4 x: e' x3 y* l: z! `@for(arcsbnd(0,f,c));
    # q0 b- H+ U* I% }end
    9 h3 w% v- J% u
    5 X2 M$ \* h: B) n( E% f9 H7 Z, E在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
    ( E6 ^# t$ T( K$ h' K! Y3 `- O
    5 \& V. i  P  N5 {6 v+ [, s4 t; C7 _model:0 N0 ^- U/ [& f1 H
    sets:
    ; s) B% Z4 ?2 _nodes/s,1,2,3,4,t/;
    ! g* {5 t1 }, e$ l. Yarcs(nodes,nodes):c,f;
    ( A( P& f* Z9 ~; F8 I* O9 cendsets6 @7 G4 F. K$ g# F; q3 t
    data:, Z* U; X4 l1 c2 s3 i4 [* k
    c=0;
    1 C  Z! u8 k/ b+ d' `@text('fdata.txt')=f;& q$ r# b/ T% f
    enddata4 U5 e# i# y, U" R+ x
    calc:
    ) r8 p0 ]8 S' Y5 Z8 t  Wc(1,2)=8;c(1,4)=7;
    2 v4 M& E/ K  B  ec(2,3)=9;c(2,4)=5;
    . j) t  K5 s/ o6 S: q. z* Sc(3,4)=2;c(3,6)=5;' {6 p6 z+ U# G
    c(4,5)=9;c(5,3)=6;c(5,6)=10;
    1 [  S3 Y2 j: M) Z8 v" t( G- Eendcalc
    - H6 t0 B5 X5 A; \n=@size(nodes); !顶点的个数;: z* k, Z4 E5 z: y3 D% W6 @* q
    max=flow;
    0 H( X# x* Q+ y5 x2 N" q@for(nodes(i)|i #ne#1 #and# i #ne# n:
    $ b/ E- W9 J1 f    @sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));
    6 H2 k  l" P/ o, X0 _5 t" ~@sum(nodes(i):f(1,i))=flow;
    $ \# v; n+ p' ?; I@sum(nodes(i):f(i,n))=flow;
    4 V$ G7 L. ]/ k0 K% F@for(arcsbnd(0,f,c));
    1 d3 N" w! _" E9 |! y! m$ Bend
    / `) c- F- t+ g; q7 {" g9 O* m: M* d6 n9 O
    ————————————————
    . G& p; @. Y# }6 ~7 ?* o/ Z* Q版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    * E- c9 K+ K$ F+ x原文链接:https://blog.csdn.net/qq_29831163/article/details/897863137 h2 l7 |8 }. r

    % r( E) q$ Q" m5 P+ u" B
    $ {5 m2 p/ O; o
    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-6-10 01:34 , Processed in 0.464462 second(s), 51 queries .

    回顶部