On a digraphMathworldPlanetmath, define a sink to be a vertex with out-degree zero and a source to be a vertex with in-degree zero. Let G be a digraph with non-negative weights and with exactly one sink and exactly one source. A cut C on G is a subset of the edges such that every path from the source to the sink passes through an edge in C. In other words, if we remove every edge in C from the graph, there is no longer a path from the source to the sink.

Define the weight of C as


where W(e) is the weight of the edge e.

Observe that we may achieve a trivial cut by removing all the edges of G. Typically, we are more interested in minimal cuts, where the weight of the cut is minimized for a particular graph.

Title cut
Canonical name Cut
Date of creation 2013-03-22 13:00:53
Last modified on 2013-03-22 13:00:53
Owner vampyr (22)
Last modified by vampyr (22)
Numerical id 5
Author vampyr (22)
Entry type Definition
Classification msc 05C20
Related topic MaximumFlowminimumCutTheorem
Defines minimum cut