我目前正在通过练习来研究网络流算法，并且我坚持我认为解决这样一个练习所必需的子问题 .
问题：如何计算属于流图的每个最小切割的节点集？
直观地说，如果使用Ford-Fulkerson并选择增强路径以便具有最小数量的边缘，这应该给我们一个最小基数的切割集，但是这些节点必须在每个最小切割中吗？
如果是这样，我似乎无法证明这一点 . 如果没有，我没有任何真正的想法 . 也许找到一种在残差图中交换边缘的机制？
请帮忙！
我相信我已经制定了一个合适的答案：
声明：可以在（源侧）最小割集中的每个节点必须在max-flow返回的流残留图Gf（即Ford-Fulkerson）中是源可达的 .
证明：假设没有 . 然后，存在一些u，使得在Fg中没有s-u路径并且在某些源侧最小割集中，S -1729502_不被F-F返回 . 这意味着你在T（最小切割的下沉侧） .
我们现在表明，在保留最小切割属性的同时，没有办法将S转换为S' . 假设它是可能的 . 然后，任何能够进行转换的算法都需要能够识别s-u路径，以便在某些残差图中将流从s推送到u . 但请注意，这是不可能的 .
考虑任何边（v，w），使得v在S中，而w在T中 . 因为你不在S中，它必须是w不是u（即从S到u没有前沿，否则它将是在S已经） . 然后，必须通过添加从S到T的前沿来使s可以访问 . 但是，这是不可能的！仅可通过max-flow / min-cut属性在反向边上添加流量 . 然后证明了这一说法 .
为了解决上面发布的问题，我们简单地计算所有节点的集合，这些节点可以在源端最小割集中（称为集合A），然后反转边缘并计算可以在接收器中的所有节点的集合-min min-cut set（称为B），计算交集（调用此C），然后计算Answer = A-C . 该算法的复杂度与FF相同，即O（| V | ^ 3） .
如果您发现任何错误，请告诉我！很抱歉回答我自己的问题！
1 回答
我相信我已经制定了一个合适的答案：
声明：可以在（源侧）最小割集中的每个节点必须在max-flow返回的流残留图Gf（即Ford-Fulkerson）中是源可达的 .
证明：假设没有 . 然后，存在一些u，使得在Fg中没有s-u路径并且在某些源侧最小割集中，S -1729502_不被F-F返回 . 这意味着你在T（最小切割的下沉侧） .
我们现在表明，在保留最小切割属性的同时，没有办法将S转换为S' . 假设它是可能的 . 然后，任何能够进行转换的算法都需要能够识别s-u路径，以便在某些残差图中将流从s推送到u . 但请注意，这是不可能的 .
考虑任何边（v，w），使得v在S中，而w在T中 . 因为你不在S中，它必须是w不是u（即从S到u没有前沿，否则它将是在S已经） . 然后，必须通过添加从S到T的前沿来使s可以访问 . 但是，这是不可能的！仅可通过max-flow / min-cut属性在反向边上添加流量 . 然后证明了这一说法 .
为了解决上面发布的问题，我们简单地计算所有节点的集合，这些节点可以在源端最小割集中（称为集合A），然后反转边缘并计算可以在接收器中的所有节点的集合-min min-cut set（称为B），计算交集（调用此C），然后计算Answer = A-C . 该算法的复杂度与FF相同，即O（| V | ^ 3） .
如果您发现任何错误，请告诉我！很抱歉回答我自己的问题！