Previous Page Next Page Contents

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

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




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000