4.3.8. Maximum flow and minimum cut
4.3.8.1. Flow networks and the maximum-flow problem
A flow network is a variant of connected, directed graphs that can be used to model physical flows in a network of terminals, such as water coursing through interconnecting pipes or electrical currents flow through a circuit. In a flow network G = (V, E), every edge (u, v) ∈ E has a non-negative capacity c(u, v) that indicates the quantity of flow this edge can hold. If (u, v) ∉ E, c(u, v) = 0. There are two special vertices in a flow network, the source s and the sink t. Every flow must start at the source s and end at the sink t. Hence, there is no edge incident to s and neither an edge leaving t. For convenience, we assume that every vertex lies on some ...
Get Electronic Design Automation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
