Network::minCut -- computes a
minimal cut
Introduction computes a
minimal cut in Network::minCut(G, q, s)G separating node q from node
s.
Call(s)Network::minCut(G,q,s)
Parametersq,s |
- | expressions (nodes in the network) |
G |
- | network |
Returns
DetailsNetwork::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.
Example
1In 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]]
Example
2In 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