Prerequisite: Graph Concepts

A random contraction algorithm finds the minimum cut of
a graph by randomly contracting edges until only two vertices remain (see pseudo
code). The *minimum cut* is the grouping of vertices into two non-empty groups having
the fewest number of crossing edges. Consider the graph in the graphic below.
There is no other way of dividing the vertices that would result in fewer
crossing edges.

In an undirected graph, a crossing edge is considered any edge that has an end
point in both groups. A crossing edge in a directed graph is when an edge has a
tail in group 1 and a head in group 2. The *minimum cut size* is the number of
crossing edges. Logically, the size cannot exceed the minimum degree of the
graph.

## Source Code

Relevant Files:

Click here for build and run instructions