后向弧定义

发布网友发布时间：2022-04-29 18:47

共1个回答

热心网友时间：2022-06-19 18:30

向和链的正方向一相反的弧。后向弧为与前向弧顶点相同，方向相反的弧。且后向弧的流量永远为所对应前向弧的流量的相反数。

前后向弧：一条从起点v到终点vt的链μ，规定从v到v的方向为链μ的方向，链上与μ方向一致的边叫前向弧（边），记作μ；与μ方向相反的边称为后向弧（边），记作μ。

增广路

增广路是一条链，链上的前向弧都是非饱和弧链上的后向弧都是非零弧。给定一个可行流f = fij，把网络中fij = cij的弧称为饱和弧，fij < cij的弧称为非饱和弧。把fij = 0的弧称为零流弧，把fij > 0的弧称为非零流弧。

若P是网络中连接源点和汇点的一条路，定义流的方向s->t，则路上的弧被分为两类：一类与流的方向一致，称为前向弧；另一类与流的方向相反，称为后向弧（反向边）。

增广路定义①：给定一个可行流f，若P是网络中连接源点和汇点的一条路，若P满足：前向弧是非饱和弧，后向弧是非零弧，则称P为关于f的一条增广路。

增广路定义②：在一个可行流对应的残余网络中，从源点出发，沿着容量＞0的弧，到达汇点的路径。