Minimum CutWhat is a Minimum Cut in a graph?LetG be a graph and weight a non-negative function
on the edges of G. A cut in G a is a subset
of the nodes that is neither empty nor the complete set of nodes. The weight
of a cut is the sum of the weights of the edges having exactly
one end node in the cut. A minimum cut is a cut of minimum weight.
Remark: To use the minimum cut algorithm provided by LEDA the edge weights must be non-negative. Application of Minimum CutThe problem of finding the minimum weight cut in a graph plays an important role in the design of communication networks. If a few of the links are cut or otherwise fail, the network may still be able to transmit messages between any pair of its nodes. If enough links fail, however, there will be at least one pair of nodes that cannot communicate with each other. Thus an important measure of the reliability of a network is the minimum number of links that must fail in order for this to happen. Algorithm for Minimum Cut
Example of How to Use
Running TimeFor a graph |
See also:Manual Entries: Manual Page Minimum Cut |