流网实例 1.例1:管道中的流体 第九讲 Maximum flow 2.例2:电网中的电流 极大流 3.例3:通信网络中的信息流 4.例4:装配线上的零件流 清华大学 宋斌恒 清华大学就件学院末恒 请华大学轼件学院宋斌恒 概念 12/12 11/16 15/20 1.有向边:传输物质的管道 2.容量:每条管道有静态容量:单位时间 101/4/7 内可以通过物质的最大数量,如每天可 以通过100万立方米的石油管道 8/13 3.点:管道连接点,满足流量守恒律 清华大学软件学院宋恒 請华大学轼件学院宋斌包 流网的定义 Kirchhoffs电流定律 1.流网G=(VE)是一个具有非负边权的有向图 边权c(uV)叫做容量,如果(uv)不属于E,我 1.流量守恒定律: 们约定其容量c(uv)=0 流入同一节点的总流量等于流出同一节点总 2.在流网上有两个特殊点源s和汇t 流量 2.对于电流就是 Kirchhoffs定律 3.对于每个点v,都有一条从s经过v到达t的路 3.极大流问题:计算流网中满足约束(上 述守恒律)的从源到汇的最大流量 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒1 清华大学 软件学院 宋斌恒 1 第九讲. Maximum Flow 极大流 清华大学 宋斌恒 清华大学 软件学院 宋斌恒 2 流网实例 1. 例1：管道中的流体 2. 例2：电网中的电流 3. 例3：通信网络中的信息流 4. 例4：装配线上的零件流 清华大学 软件学院 宋斌恒 3 概念 1. 有向边：传输物质的管道 2. 容量：每条管道有静态容量：单位时间 内可以通过物质的最大数量，如每天可 以通过100万立方米的石油管道 3. 点：管道连接点，满足流量守恒律 清华大学 软件学院 宋斌恒 4 1 3 2 4 s t 清华大学 软件学院 宋斌恒 5 Kirchhoff’s 电流定律 1.流量守恒定律： 1.流入同一节点的总流量等于流出同一节点总 流量 2.对于电流就是Kirchhoff’s 定律 3.极大流问题：计算流网中满足约束（上 述守恒律）的从源到汇的最大流量。 清华大学 软件学院 宋斌恒 6 流网的定义 1. 流网G=(V,E)是一个具有非负边权的有向图， 边权c(u,v)叫做容量，如果(u,v)不属于E，我 们约定其容量c(u,v)＝0。 2. 在流网上有两个特殊点源s和汇t。 3. 对于每个点v，都有一条从s经过v到达t的路 径