Minimum cut in a graph
min_cut calculates the minimum st-cut between two vertices in a graph
target arguments are given) or the minimum
cut of the graph (if both
min_cut(graph, source = NULL, target = NULL, capacity = NULL, value.only = TRUE)
- The input graph.
- The id of the source vertex.
- The id of the target vertex (sometimes also called sink).
- Vector giving the capacity of the edges. If this is
NULL(the default) then the
capacityedge attribute is used.
- Logical scalar, if
TRUEonly the minumum cut value is returned, if
FALSEthe edges in the cut and a the two (or more) partitions are also returned.
The minimum st-cut between
target is the minimum
total weight of edges needed to remove to eliminate all paths from
The minimum cut of a graph is the minimum total weight of the edges needed to remove to separate the graph into (at least) two components. (Which is to make the graph not strongly connected in the directed case.)
The maximum flow between two vertices in a graph is the same as the minimum
min_cut essentially calculate the same
quantity, the only difference is that
min_cut can be invoked without
target arguments and then minimum of all
possible minimum cuts is calculated.
For undirected graphs the Stoer-Wagner algorithm (see reference below) is used to calculate the minimum cut.
min_cuta numeric constant, the value of the minimum cut, except if
value.only = FALSE. In this case a named list with components:
value Numeric scalar, the cut value. cut Numeric vector, the edges in the cut. partition1 The vertices in the first partition after the cut edges are removed. Note that these vertices might be actually in different components (after the cut edges are removed), as the graph may fall apart into more than two components. partition2 The vertices in the second partition after the cut edges are removed. Note that these vertices might be actually in different components (after the cut edges are removed), as the graph may fall apart into more than two components.
M. Stoer and F. Wagner: A simple min-cut algorithm, Journal of the ACM, 44 585-591, 1997.
g <- make_ring(100) min_cut(g, capacity=rep(1,vcount(g))) min_cut(g, value.only=FALSE, capacity=rep(1,vcount(g))) g2 <- graph( c(1,2,2,3,3,4, 1,6,6,5,5,4, 4,1) ) E(g2)$capacity <- c(3,1,2, 10,1,3, 2) min_cut(g2, value.only=FALSE)