数学建模社区-数学中国

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

作者: ゞ_轻描丶幸福的    时间: 2014-12-10 10:30
标题: 节点和边都有容量的有向平面网络中的最小截和最大流
摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方6 d' u+ X. r- x& R& b
法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传9 S, l. r: _0 s7 h
统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面
- A$ [* c- t: o8 x4 N% Y+ m网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问! t6 U9 c; }) E% q! i
题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从
4 q; U& x% r+ p! d- O: n并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点
% N: ^! h; r& E2 y! V和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的.
7 ?# W& @. \6 _1 ?$ X关键词 平面网络; 最大流; 最小截; P- 完全; NC
; P2 @) }! R3 j1 [+ j$ b: T0 ?& ~5 U0 c

2 ^9 u8 O8 u2 {4 X4 M* G( F! `9 b0 O  R2 T2 h* w. ~
2 O, Z6 Z. P9 V* C7 Z% z3 c+ {
( T. k2 K: ~8 u$ s5 O( s

+ Z/ A8 N. t9 ]8 i% U; P+ m. n* E& ]* z

8 J% p: x& E: N: H4 \% |
. V" e' q# q8 e, j 节点和边都有容量的有向平面网络中的最小截和最大流.pdf (1.26 MB, 下载次数: 0) 8 ^( X1 k* o# ]! u' N- z! V

1 V9 B7 T% x5 I6 _! g9 B

4 G8 K) n9 X2 b! o5 W% ?  x) G8 J! T7 ]1 x8 E1 ^





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