为什么图论中的最大流算法对于最大二分匹配是正确的
Why is max flow algorithm in graph theory correct for maximal bipartite matching
我看过很多文章，说可以使用最大流算法找到二分图的最大匹配。但是有可能我们从最大流得到的匹配不是最大的或者匹配没有最大边。
Anti Laaksonen 的《竞争性编程手册》中的示例：
但是如果我以不同的方式呈现图表，那么现在的图表是：
然后随着最大流算法的进行，匹配将是
1----5,
2----7
因为 1 只是擦除到汇点的路径，但如果它会走到边缘
1----6
那么匹配可能是
1----6,
3----5,
4----7
我一直陪着你到现在：
Then as the algorithm of max flow progresses the matching would be 1----5, 2----7
您在这里描述的实际上并不是图中的最大流量。我们可以通过从 1 到 6 发送一个流量单位，从 2 到 7 发送一个流量单位，以及从 3 到 5 发送一个流量单位来推动更多流量。
阅读你的问题，我认为你最终得到（非最大）流量而不是最大流量的原因是因为这个陈述：
because 1 simply erases path to the sink
根据您在此处的描述，我假设您正在使用类似于 Ford-Fulkerson 算法的算法来计算最大流量：找到从源到汇的增广路径并将流量推过它。但是 Ford-Fulkerson 在这里还有第二步：在将流推过边之后，我们在推流的相反方向上引入 residual 边。这让我们有机会在找到更好的路径时“撤消”我们所做的决定。
这样一来，我们把一个单位的流量从1推到5之后，再加入一个从5回到1的残差边，单单位容量。这意味着图表现在看起来像这样：
此处，青色边从 s 流向 t，紫色边从 t 流向 s。
请注意，我们可以“撤消”将 1 分配给 5 的决定，如下所示。在路径上推送一个流量单元
s → 3 → 5 → 1 → 6 → t
给这个流量网：
现在，在路径上再推一个单位的流量
s → 2 → 7 → t
给出整体匹配1--6、2--7、3--5，为最大匹配。
我看过很多文章，说可以使用最大流算法找到二分图的最大匹配。但是有可能我们从最大流得到的匹配不是最大的或者匹配没有最大边。
Anti Laaksonen 的《竞争性编程手册》中的示例：
但是如果我以不同的方式呈现图表，那么现在的图表是：
然后随着最大流算法的进行，匹配将是 1----5, 2----7
因为 1 只是擦除到汇点的路径，但如果它会走到边缘 1----6 那么匹配可能是
1----6, 3----5, 4----7
我一直陪着你到现在：
Then as the algorithm of max flow progresses the matching would be 1----5, 2----7
您在这里描述的实际上并不是图中的最大流量。我们可以通过从 1 到 6 发送一个流量单位，从 2 到 7 发送一个流量单位，以及从 3 到 5 发送一个流量单位来推动更多流量。
阅读你的问题，我认为你最终得到（非最大）流量而不是最大流量的原因是因为这个陈述：
because 1 simply erases path to the sink
根据您在此处的描述，我假设您正在使用类似于 Ford-Fulkerson 算法的算法来计算最大流量：找到从源到汇的增广路径并将流量推过它。但是 Ford-Fulkerson 在这里还有第二步：在将流推过边之后，我们在推流的相反方向上引入 residual 边。这让我们有机会在找到更好的路径时“撤消”我们所做的决定。
这样一来，我们把一个单位的流量从1推到5之后，再加入一个从5回到1的残差边，单单位容量。这意味着图表现在看起来像这样：
此处，青色边从 s 流向 t，紫色边从 t 流向 s。
请注意，我们可以“撤消”将 1 分配给 5 的决定，如下所示。在路径上推送一个流量单元
s → 3 → 5 → 1 → 6 → t
给这个流量网：
现在，在路径上再推一个单位的流量
s → 2 → 7 → t
给出整体匹配1--6、2--7、3--5，为最大匹配。