每个图上的Max-Cut实例可以自然地转化为一个Max 2-SAT实例，其中每条边对应一个子句，要求两个端点属于不同部分。