数学建模社区-数学中国

标题: 节点和边都有容量的有向平面网络中的最小截和最大流 [打印本页]

作者: ゞ_轻描丶幸福的    时间: 2014-12-10 10:30
标题: 节点和边都有容量的有向平面网络中的最小截和最大流
摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方
) d# X& ?6 @9 z% ~  t法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传, R4 |6 l, f0 D5 G; i# ]" k4 r
统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面3 T: d* R- u) t
网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问6 L& F" m1 @, W; M# ~$ x' }
题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从
5 Q) R- i; b3 ?8 }3 t并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点5 z8 m0 d# m. w9 l: V
和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的.
3 P4 T# n# F( z  K. j! `& Y8 a' L3 @关键词 平面网络; 最大流; 最小截; P- 完全; NC2 D! E9 k' H2 @" l
! A# H1 ?4 z/ J0 r  e

5 r6 c% \, e3 F: O" `
3 \4 S- u1 I1 |
) c! ]% j/ v: |+ h# r& j# o* X) l) K' }: v) t7 s

  k, |2 D# }, k# N6 m% f. Y( w1 m' B  U8 l

5 r0 G* a5 W! X  H: a5 Q# b" s! H+ j( x
节点和边都有容量的有向平面网络中的最小截和最大流.pdf (1.26 MB, 下载次数: 0) ' q+ B  ?" x8 k, l' B

3 R6 ]# K) t3 ?, Q3 U

! J8 n. }0 U3 m5 F, K% o( S. e4 v4 I. y4 c' z; e" @





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5