知识卡片

普通读书笔记卡 · 3646.g.4 · 生成模型:未记录

顶点容量通过拆点变成边容量

理解等级:中级

把顶点v拆为v_in和v_out,并添加容量为k(v)的边 v_in→v_out;原入边连接v_in,原出边从v_out出发并保留各自原容量。根据问题定义决定源、汇是否也受顶点容量约束。

无向边的建模需明确是否共享双向容量;在普通单物资净流问题中可用两条反向容量边并消去互相抵消的流,但不能把这一转换无条件推广到多物资共享容量。

240的03394通过仓库入点和出点之间的边表达仓库吞吐上限及单位处理成本;源供给与汇需求边则表达上下限。规约后仍需核验总需求是否全部满足,不能只检查求解器返回任意非负流。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      顶点容量 如果流网络中的每个顶点v都有一个最大容量k(v)将会怎么样呢?构建一个修改过的图G'。对于网络中的每个顶点v,构建两个顶点v'和v"。并且创建一条边(v",v'),这条边的容量是k(v)。在图G中创建一条容量为c(x,v)的边(x,v),对应原始图G中的容量为c(x,v)的每条边(x,v"

    • · 查看原书依据

      转运问题转换成最小开销流问题(如图8-8所示),构造了这样一个图G=(V,E): V共有n+m+2*w+2个顶点 每个供应站si被映射成一个顶点i,每个仓库wk映射成两个顶点,m+2*k-1和m+2*k。每个需求站tj映射成顶点1+m+2*w+j。然后创建一个新的源点src(标记为0)和新的汇点tg

    参考来源

    - 位置:《算法技术手册》第8章《相关算法》(spine1633;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1596.html;u232-ch08-005)。 - 结论依据:232全文实读;保留原边容量修正正文转换。 - 原始内容:顶点容量 如果流网络中的每个顶点v都有一个最大容量k(v)将会怎么样呢?构建一个修改过的图G'。对于网络中的每个顶点v,构建两个顶点v'和v"。并且创建一条边(v",v'),这条边的容量是k(v)。在图G中创建一条容量为c(x,v)的边(x,v),对应原始图G中的容量为c(x,v)的每条边(x,v" - 位置:《算法技术手册》第8章《解决方案》(spine1639;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1602.html;u240-ch08-005)。 - 结论依据:240的03394通过仓库入点和出点之间的边表达仓库吞吐上限及单位处理成本;源供给与汇需求边则表达上下限。规约后仍需核验总需求是否全部满足,不能只检查求解器返回任意非负流。 - 原始内容:转运问题转换成最小开销流问题(如图8-8所示),构造了这样一个图G=(V,E): V共有n+m+2*w+2个顶点 每个供应站si被映射成一个顶点i,每个仓库wk映射成两个顶点,m+2*k-1和m+2*k。每个需求站tj映射成顶点1+m+2*w+j。然后创建一个新的源点src(标记为0)和新的汇点tg