display | more...

In graph theory, a minimum cut is the number of nodes or vertices necessary to connect two points.

For example, say you have a connected graph of three points, a b, c, d in the following layout:


a 
|  \
b -  c

a, b, and c are each connected. Although there may be maximum flow with the path of a, b, c the minimum cut is actually a, c.

This has a number of real world uses.

In networking circles, determining the minimum cut is necessary to reduce latency.

So for example if every edge takes 100 milliseconds to transfer data, this time is added each time a packet leaves a node.

Log in or register to write something here or to contact authors.