Ford-Fulkerson 算法和最大流最小割定理
Ford-Fulkerson Algorithm & Max Flow Min Cut Theorem
您好，我在使用 max-flow min-cut Theorem 学习 Ford-Fulkerson 算法时遇到了问题。
根据定理，最大流量应该等于被切割边的总重量。
然而，看到视频https://www.youtube.com/watch?v=Tl90tNtKvxs，让我感到困惑。讲师说根据 Ford-Fulkerson 算法最大流量是 19，但我找不到以 19 为代价的任何削减。有什么问题吗？
切割意味着您在源极和漏极之间定义切割。该切口不必是直线、曲线或任何其他形状就足够了。
例如这里我选择 blue 切割使得边缘 AB, AD和 CD 正在通过削减。现在，如果我们查看这些边的分配流，并将它们相加，我们得到 4+6+9=19.
另一种剪裁方式是绿色剪裁。这里我们有边 BT、AD 和 AC 移动 "forward"，还有一条边DC 移动"backwards"。因此流量总和为 9+6+9-5=19。所以不管我们采取什么削减，总和总是19（当然我们需要做适当的簿记，并减去相反方向的流量）。
当然你可以选择你想要的任何切割（例如在源之后切割，或者在漏之前切割），如果算法正确完成，那么所有这些切割的总和总是19。这个是合乎逻辑的，因为如果一个切割的流量会多于（或少于）19，那么 "advances" 一个节点的流量为 19 的切割的存在意味着在该节点中，流量消失了, 或出现。
然而，它认为如果您要遍历所有可能的切割，那么最小切割就是容量总和最大化的切割。因此，严格来说，我们可以迭代所有可能的切割，并且每次跟踪容量的总和，最后 select 具有最小流量的那个。然而，如果简单地迭代所有切割，一种天真的方法将导致 O(2n) 算法，与 Ford–Fulkerson算法，当然不可取
您对最大流最小割定理的解释没有错。
最小割集由边SA和CD组成，总容量为19。
要切割并计算成本，您可以：
- 将所有顶点分成2组，S和D，源在S，漏在D。
- 切割从 S 中的顶点到 D 中的顶点的所有边。请注意，您不需要切割从 D 到 S 的边。
- 将您切割的边的容量相加。
对于上面的最小割，S 包含顶点 s 和 c，D 包含其余部分。
您好，我在使用 max-flow min-cut Theorem 学习 Ford-Fulkerson 算法时遇到了问题。
根据定理，最大流量应该等于被切割边的总重量。
然而，看到视频https://www.youtube.com/watch?v=Tl90tNtKvxs，让我感到困惑。讲师说根据 Ford-Fulkerson 算法最大流量是 19，但我找不到以 19 为代价的任何削减。有什么问题吗？
切割意味着您在源极和漏极之间定义切割。该切口不必是直线、曲线或任何其他形状就足够了。
例如这里我选择 blue 切割使得边缘 AB, AD和 CD 正在通过削减。现在，如果我们查看这些边的分配流，并将它们相加，我们得到 4+6+9=19.
另一种剪裁方式是绿色剪裁。这里我们有边 BT、AD 和 AC 移动 "forward"，还有一条边DC 移动"backwards"。因此流量总和为 9+6+9-5=19。所以不管我们采取什么削减，总和总是19（当然我们需要做适当的簿记，并减去相反方向的流量）。
当然你可以选择你想要的任何切割（例如在源之后切割，或者在漏之前切割），如果算法正确完成，那么所有这些切割的总和总是19。这个是合乎逻辑的，因为如果一个切割的流量会多于（或少于）19，那么 "advances" 一个节点的流量为 19 的切割的存在意味着在该节点中，流量消失了, 或出现。
然而，它认为如果您要遍历所有可能的切割，那么最小切割就是容量总和最大化的切割。因此，严格来说，我们可以迭代所有可能的切割，并且每次跟踪容量的总和，最后 select 具有最小流量的那个。然而，如果简单地迭代所有切割，一种天真的方法将导致 O(2n) 算法，与 Ford–Fulkerson算法，当然不可取
您对最大流最小割定理的解释没有错。
最小割集由边SA和CD组成，总容量为19。
要切割并计算成本，您可以：
- 将所有顶点分成2组，S和D，源在S，漏在D。
- 切割从 S 中的顶点到 D 中的顶点的所有边。请注意，您不需要切割从 D 到 S 的边。
- 将您切割的边的容量相加。
对于上面的最小割，S 包含顶点 s 和 c，D 包含其余部分。