Chinaunix

标题: 关于最大流算法中反向平行边的处理 [打印本页]

作者: Forif 时间: 2014-02-08 00:06
标题: 关于最大流算法中反向平行边的处理
最近在学网络流，有这样一个问题困扰了我很久，就是对于两个节点u和v，从u到v有一条边（u，v），比如它的容量是C（u，v）=4，而从v到u也有一条边（v，u），C（v，u）=10，我在算法导论里看到对于两点之间的边的定义是如果存在（u，v），那（v，u）就不能存在，如果存在的话这两条边就叫Antiparallel edges，对于它的处理就是任选一条边比如（v，u）将它分裂成两条边（v，e）和（e，u）并且C（v，e）=C（e，u）=C（v，u）=10。因为算法需要一个对应原图的Residul network，每条有向边都需要用一个正向和一个反向的余度边来表示。
我的问题是我在网上看到许多最大流算法的实现中都没有对反向平行边做处理（新增一个节点和两条边），而是直接读入并将相应的正向和反向边存入邻接矩阵或是邻接表里，而程序依然可以正确运行，这是为什么？是出于巧合还是有相关的证明？如果有相关证明那具体是怎样的，到哪里可以找到？谢谢！

作者: folklore 时间: 2014-02-08 09:05
没看懂，楼主NB。

作者: exprosic 时间: 2014-02-09 19:35
回复 1# Forif

这个规定只是为了使残量网络里没有平行边，使得 (26.2) 的定义有唯一性，方便之后的讨论
但有平行边不影响增广过程，所以放着不管也没问题

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)