> one of graph theory’s most central questions. The “MaxCut” problem is about the optimal way to cut a graph into two parts so that there are as many edges as possible connecting the parts.
Wikipedia agrees with this definition of the max-cut problem. But it surprises me, since the max-flow min-cut theorem refers to cuts in a weighted graph. (Where the min-cut is the cut of minimum weight.)
This is the same thing as minimum edge count if you apply it to an unweighted graph. But as far as wikipedia says, the "max-cut" problem is specifically about edge count, and the generalization to a weighted graph is called the "weighted max-cut problem". Why the difference?
thaumasiotes•1w ago
Wikipedia agrees with this definition of the max-cut problem. But it surprises me, since the max-flow min-cut theorem refers to cuts in a weighted graph. (Where the min-cut is the cut of minimum weight.)
This is the same thing as minimum edge count if you apply it to an unweighted graph. But as far as wikipedia says, the "max-cut" problem is specifically about edge count, and the generalization to a weighted graph is called the "weighted max-cut problem". Why the difference?