为什么找到最大切割 NP-hard？
Why is finding the maximum cut NP-hard?
我最近发现在带加权边的图中找到最大割是 NP 难的。然而，找到最小割并不是 NP 难的。
如果我反转所有边上的权重然后搜索最小割，那不是给我原始图上的最大割吗？如果不是，为什么？
图的最大割不是具有逆权重的图的最小割。考虑下图：红线是最小切割，绿色是最大切割。
如果您所说的逆是指"opposite"，那么确实为一个找到最大值归结为为另一个找到最小切割。证明很简单。
令G为任意图，G'为具有相反权重的图。令 v_1,..., v_n 为要删除以进行 G 的最大切割的顶点序列，w_1,..., w_n 为相关权重。 M = w_1 + ... + w_n = max(cuts)。显然v_1,..., v_n是G'中的一个截断。令 v'_1,...,v'_m 为 G' 中的任何切割，w'_1,..., w'_n 它们在 G' 中的权重。
那么v'_1,...,v'_m也是G中权重-(w'_1+...+w'_q)的一个切割。根据 M 的定义，我们有 -(w'_1+...+w'_q) <= M 等 w'_1+...+w'_q >= -M。所以我们有-M是G'中的min cut值，v_1,..., v_n实现这个值，就是G'的min cut。
至于为什么这不是一个容易解决的问题，请看
Peter de Rivaz 的回答。
我假设你的意思是将权重 w 更改为 -w。
在这种情况下，调整图的最小割确实解决了原始图的最大割问题。
不幸的是，解决最小割问题的有效算法只有在所有权重都为非负数时才为人所知，这意味着我们只有在所有权重都为非正数的情况下才能有效地解决最大割问题。
要找到问题（多项式或非多项式）的class，您应该使用Reduction which is a mechanism to transform a problem into another problem. You can find more discussion in https://cs.stackexchange.com/questions/1531/is-logical-min-cut-np-complete。
我最近发现在带加权边的图中找到最大割是 NP 难的。然而，找到最小割并不是 NP 难的。 如果我反转所有边上的权重然后搜索最小割，那不是给我原始图上的最大割吗？如果不是，为什么？
图的最大割不是具有逆权重的图的最小割。考虑下图：红线是最小切割，绿色是最大切割。
如果您所说的逆是指"opposite"，那么确实为一个找到最大值归结为为另一个找到最小切割。证明很简单。
令G为任意图，G'为具有相反权重的图。令 v_1,..., v_n 为要删除以进行 G 的最大切割的顶点序列，w_1,..., w_n 为相关权重。 M = w_1 + ... + w_n = max(cuts)。显然v_1,..., v_n是G'中的一个截断。令 v'_1,...,v'_m 为 G' 中的任何切割，w'_1,..., w'_n 它们在 G' 中的权重。
那么v'_1,...,v'_m也是G中权重-(w'_1+...+w'_q)的一个切割。根据 M 的定义，我们有 -(w'_1+...+w'_q) <= M 等 w'_1+...+w'_q >= -M。所以我们有-M是G'中的min cut值，v_1,..., v_n实现这个值，就是G'的min cut。
至于为什么这不是一个容易解决的问题，请看 Peter de Rivaz 的回答。
我假设你的意思是将权重 w 更改为 -w。
在这种情况下，调整图的最小割确实解决了原始图的最大割问题。
不幸的是，解决最小割问题的有效算法只有在所有权重都为非负数时才为人所知，这意味着我们只有在所有权重都为非正数的情况下才能有效地解决最大割问题。
要找到问题（多项式或非多项式）的class，您应该使用Reduction which is a mechanism to transform a problem into another problem. You can find more discussion in https://cs.stackexchange.com/questions/1531/is-logical-min-cut-np-complete。