Cuts in Undirected Graphs. I

This part of the paper analyzes new properties of cuts in undirected graphs, presents various models for the maximum cut problem, based on the established correspondence between the cuts in this graph and the specific bases of the extended polymatroid associated with this graph. With respect to the model, formulated as maximization of the convex function on the compact set (extended polymatroid), it was proved that the objective function has the same value at any local and global maxima, i.e., to solve the maximum cut problem, it will suffice to find a base of the extended polymatroid as a local or global maximum of the objective function.