Numeric vector giving the edge capacities. If this is
NULL and the graph has a weight edge attribute, then this
attribute defines the edge capacities. For forcing unit edge capacities,
even for graphs that have a weight
Value
A list with entries:
valueNumeric scalar, the size of the
minimum cut(s).
cutsA list of numeric vectors containing edge ids.
Each vector is a minimum $(s,t)$-cut.
partition1sA list of
numeric vectors containing vertex ids, they correspond to the edge cuts.
Each vertex set is a generator of the corresponding cut, i.e. in the graph
$G=(V,E)$, the vertex set $X$ and its complementer $V-X$,
generates the cut that contains exactly the edges that go from $X$ to
$V-X$.
Details
Given a $G$ directed graph and two, different and non-ajacent vertices,
$s$ and $t$, an $(s,t)$-cut is a set of edges, such that after
removing these edges from $G$ there is no directed path from $s$ to
$t$.
The size of an $(s,t)$-cut is defined as the sum of the capacities (or
weights) in the cut. For unweighed (=equally weighted) graphs, this is
simply the number of edges.
An $(s,t)$-cut is minimum if it is of the smallest possible size.
References
JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in
graphs, Algorithmica 15, 351--372, 1996.
# A difficult graph, from the Provan-Shier paperg <- graph_from_literal(s --+ a:b, a:b --+ t,
a --+ 1:2:3:4:5, 1:2:3:4:5 --+ b)
st_min_cuts(g, source="s", target="t")