Network::minCut
-- computes a
minimal cut
computes a
minimal cut in Network::minCut
(G, q, s)G
separating node q
from node
s
.
Network::minCut(G,q,s)
q,s |
- | expressions (nodes in the network) |
G |
- | network |
Network::minCut
(G,q,s)
computes a minimal
cut in G
that separates q
from
s
, i.e., a subset T
of the set S
of edges of G
such that every path from q
to
s
contains at least one edge in T
. The cut is
minimal with respect the capacities of the edges.Network::minCut
(G,q,s)
returns a sequence
consisting of the cut value (the sum of the edge weights of the cut
edges) and a list with the edges of the cut.q
is separated from s
, not vice
versa.In a complete network, a node can be separated from another one only by cutting all edges starting at the first node.
>> N1 := Network::complete(4): Network::minCut(N1, 1, 4)
3, [[1, 2], [1, 3], [1, 4]]
In the following example, the edge from node
q
to node 1
could have been used as well, but
its edge capacity is higher than that of the edge used, so the
minimality condition precludes this choice:
>> V := [1, 2, 3, q, s]: Edge := [[q, 1], [1, 2], [1, 3], [2, 3], [3, s]]: up := [5, 2, 6, 6, 1]: N2 := Network(V, Edge, Capacity=up): Network::minCut(N2, q, s)
1, [[3, s]]
There is no path from node s
to node
q
(or any other vertex of the network), so no cut is
necessary to separate s
from q
:
>> Network::minCut(N2, s, q)
0, []
Network::MinCut