On a digraph, define a sink to be a vertex with out-degree zero and a source to be a vertex with in-degree zero. Let be a digraph with non-negative weights and with exactly one sink and exactly one source. A cut on is a subset of the edges such that every path from the source to the sink passes through an edge in . In other words, if we remove every edge in from the graph, there is no longer a path from the source to the sink.
Define the weight of as
where is the weight of the edge .
Observe that we may achieve a trivial cut by removing all the edges of . Typically, we are more interested in minimal cuts, where the weight of the cut is minimized for a particular graph.
|Date of creation||2013-03-22 13:00:53|
|Last modified on||2013-03-22 13:00:53|
|Last modified by||vampyr (22)|