我一直在阅读一些关于分割图结构的多重算法的论文。我对这项工作特别感兴趣，它提出了一种算法来解决多切问题的扩展：
关于边缘成本，它说：
...对于任何一对节点，这些节点位于不同组件中的所有分解的实值成本（奖励）
很公平。它进一步说，多割问题的解决方案是一个简单的二进制向量，其长度等于图中的边数，其中“1”表示相应的边将两个属于不同图组件的顶点分开：
对于每条边 vw ∈ E ∪ F ，当且仅当 v 和 w 在 G 的不同分量中时，y(v,w) = 1。
但是优化问题写成：
这似乎没有意义。如果边权重描述了在不同组件中连接节点的边的奖励，这不应该是一个最大化问题吗？在任何一种情况下，如果所有边权重都是正的，那不会导致一个简单的解决方案，其中y全零向量是什么？上面的表达式后面是论文中的一些约束，但我不知道其中任何一个是如何阻止这种结果的。
此外，当它稍后尝试使用贪婪加性边缘收缩生成初始解决方案时，它说：
阿尔格。1 从分解为单个节点开始。在每次迭代中，连接一对相邻组件，该连接最大程度地降低了目标值。如果没有连接严格减少目标值，则算法终止。
同样，如果边权重是保持节点分离的奖励，那么加入任何两个节点不会减少奖励吗？即使我假设边缘权重是保持节点分离的惩罚，这种方法不会简单地将所有节点集中到一个组件中吗？
我看到这可行的唯一方法是边缘权重是正值和负值的平衡组合，但我很确定我错过了一些东西，因为文献中没有提到这个约束。