In this case we have a graph and we want to find a partition of the node of the graph into two disjoint sets such that the number of edges, which go form one partition to the other, is maximised.
Basically, you can think this problem as follows: how many edges we can cut with just one cut?
