## `Network::minCut` -- computes a minimal cut

#### Introduction

``Network::minCut`(G, q, s)` computes a minimal cut in `G` separating node `q` from node `s`.

#### Call(s)

`Network::minCut(G,q,s)`

#### Parameters

`q,s` | - | expressions (nodes in the network)
`G` | - | network

#### Returns

#### Details

- ``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.
- Note that `q` is separated from `s`, not vice versa.

#### Example 1

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]]

#### Example 2

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, []

#### Changes

- used to be called `Network::MinCut`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000