知识卡片
可行流满足容量与守恒
对每条实际有向边使用非负流量 f(e),要求 0≤f(e)≤c(e);除源和汇外,每个顶点流入总量等于流出总量。流值可由源点净流出或汇点净流入计算。
也可使用反对称净流表示,但此时 f(v,u)=−f(u,v) 不能与每个方向独立非负流的记号直接混用;若两方向都有实际边,应明确净流与独立边流如何对应。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
容量限制 通过一条边的流f(u,v)不能为负,而且不能超过边的容量c(u,v),即0≤f(u,v)≤c(u,v)。如果在网络中不存在边(u,v),那么c(u,v)=0。 流守恒 除开源点s和汇点t,每个顶点u∈V必须满足所有的入流等于所有的出流。这个性质确保了在网络中,除了源点和汇点,不会产生和消耗
参考来源
- 位置:《算法技术手册》第8章《网络流》(spine1627;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1590.html;u225-ch08-002)。
- 结论依据:225全文及03377网络图实读。
- 原始内容:容量限制 通过一条边的流f(u,v)不能为负,而且不能超过边的容量c(u,v),即0≤f(u,v)≤c(u,v)。如果在网络中不存在边(u,v),那么c(u,v)=0。 流守恒 除开源点s和汇点t,每个顶点u∈V必须满足所有的入流等于所有的出流。这个性质确保了在网络中,除了源点和汇点,不会产生和消耗