Flow Networks
Flow Networks
复制标题
流网络
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Carola Wenk
中科院分区：
文献类型：
--
作者：
Carola Wenk
阿隆·埃弗拉特幻灯片由查尔斯·莱瑟森提供，并由卡罗拉·温克进行了微小的修改。一个流网络是一个有向图G =（V，E），有两个不同的顶点：一个源点s和一个汇点t。每个边（u，v）∈ E有一个非负容量c（u，v）.如果（u，v）≠ E，则c（u，v）= 0。示例：s t 3 2 3 2 3 1 2 1流网络定义。G上的正流是满足以下条件的函数p：V × V → R：·容量约束：对所有u，v ∈ V，0 ≤ p（u，v）≤ c（u，v）。·流量保护：对于所有u ∈ V - {s，t}，0），（），（= − ∑ ∑ ∈ ∈ V v v v u v p v u p.流的值是从源流出的净流量：∑ ∑ ∈ − V v v s v p v s p），（），（.
Alon Efrat Slides courtesy of Charles Leiserson with small changes by Carola Wenk Flow networks Definition. A flow network is a directed graph G = (V, E) with two distinguished vertices: a source s and a sink t. Each edge (u, v) ∈ E has a nonnegative capacity c(u, v). If (u, v) ∉ E, then c(u, v) = 0. Example: s t 3 2 3 3 2 2 3 3 1 2 1 Flow networks Definition. A positive flow on G is a function p : V × V → R satisfying the following: • Capacity constraint: For all u, v ∈ V, 0 ≤ p(u, v) ≤ c(u, v). • Flow conservation: For all u ∈ V – {s, t}, 0) , () , (= − ∑ ∑ ∈ ∈ V v V v u v p v u p. The value of a flow is the net flow out of the source: ∑ ∑ ∈ ∈ − V v V v s v p v s p) , () , (.