Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Max-flow min-cut theorem
Summary
In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.
This is a special case of the duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem.
The theorem equates two quantities: the maximum flow through a network, and the minimum capacity of a cut of the network. To state the theorem, each of these notions must first be defined.
A network consists of
a finite directed graph N = (V, E), where V denotes the finite set of vertices and E ⊆ V×V is the set of directed edges;
a source s ∈ V and a sink t ∈ V;
a capacity function, which is a mapping denoted by cuv or c(u, v) for (u,v) ∈ E. It represents the maximum amount of flow that can pass through an edge.
A flow through a network is a mapping denoted by or , subject to the following two constraints:
Capacity Constraint: For every edge ,
Conservation of Flows: For each vertex apart from and (i.e. the source and sink, respectively), the following equality holds:
A flow can be visualized as a physical flow of a fluid through the network, following the direction of each edge. The capacity constraint then says that the volume flowing through each edge per unit time is less than or equal to the maximum capacity of the edge, and the conservation constraint says that the amount that flows into each vertex equals the amount flowing out of each vertex, apart from the source and sink vertices.
The value of a flow is defined by
where as above is the source and is the sink of the network. In the fluid analogy, it represents the amount of fluid entering the network at the source. Because of the conservation axiom for flows, this is the same as the amount of flow leaving the network at the sink.
The maximum flow problem asks for the largest flow on a given network.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.