流网络上 mincut 的方向性
Directionality of mincut on a flow network
我不确定我是否对mincut有误解，但我已经使用edmond-karps写了一个mincut算法，然后在流网络上进行了BFS。
如果我告诉它做一个从 A 到 B 的最小切割，它会起作用，因为剩余流 A->B = 0，所以它产生集合 {A}，切割 A->B ( 1).
但是，如果我告诉它从 B 到 A 进行最小切割，它不会增加任何边（因为没有来自 C 的边），所以结果集是 {C}，带有B->C (2).
的剪切
在我看来，我可能以两种方式中的一种误解了这一点。首先，从 B 到 A 的 mincut 可能是正确的，因为只会计算 B 的集合的边，而不是到的边（意味着 mincut 是问 "what is the minimum to not allow B to connect to A"，而不是“将图形拆分成的最小值是多少2 个分区）。
或者，如果要求您在流网络上查找最小截断（一般最小截断，我目前使用的是 "pick an arbitrary source, try all other nodes" 方法），它必须要求任何方向上的双向流量相等边缘。
"source=B, sink=A" 的 'correct' 最小割为 0，因为没有边 B->A（等效地，c(B, A) = 0）；看起来您的实施可能会回答不同的问题。您是否在 BFS 阶段检查每条潜在的最短路径以确保它在汇点结束？
(meaning mincut is asking "what is the minimum to not allow B to
connect to A", rather than "what is the minimum to split the graph
into 2 partitions).
是的，第一个：我们只关心从源到汇的瓶颈（最大流最小割定理）。 Min-cut 做 "partition" 将图一分为二，但还有一个额外的要求，即源和汇在不同的集合中。
(a general min-cut, where I'm currently using a "pick an arbitrary source, try all other nodes" method)
如果你说 "treat all the other nodes as sinks," 这是对源的外边缘进行的简单度数计算。
编辑：这不完全是度数计算，因为边是加权的，但它只是将边权重相加，不需要搜索。
it must require equal flow in both directions on any edge.
不存在这样的要求（流网络是有向图——任何无向边都映射到两条反平行边，对于特定的流问题，只使用其中一条边）。
我不确定我是否对mincut有误解，但我已经使用edmond-karps写了一个mincut算法，然后在流网络上进行了BFS。
如果我告诉它做一个从 A 到 B 的最小切割，它会起作用，因为剩余流 A->B = 0，所以它产生集合 {A}，切割 A->B ( 1).
但是，如果我告诉它从 B 到 A 进行最小切割，它不会增加任何边（因为没有来自 C 的边），所以结果集是 {C}，带有B->C (2).
的剪切在我看来，我可能以两种方式中的一种误解了这一点。首先，从 B 到 A 的 mincut 可能是正确的，因为只会计算 B 的集合的边，而不是到的边（意味着 mincut 是问 "what is the minimum to not allow B to connect to A"，而不是“将图形拆分成的最小值是多少2 个分区）。
或者，如果要求您在流网络上查找最小截断（一般最小截断，我目前使用的是 "pick an arbitrary source, try all other nodes" 方法），它必须要求任何方向上的双向流量相等边缘。
"source=B, sink=A" 的 'correct' 最小割为 0，因为没有边 B->A（等效地，c(B, A) = 0）；看起来您的实施可能会回答不同的问题。您是否在 BFS 阶段检查每条潜在的最短路径以确保它在汇点结束？
(meaning mincut is asking "what is the minimum to not allow B to connect to A", rather than "what is the minimum to split the graph into 2 partitions).
是的，第一个：我们只关心从源到汇的瓶颈（最大流最小割定理）。 Min-cut 做 "partition" 将图一分为二，但还有一个额外的要求，即源和汇在不同的集合中。
(a general min-cut, where I'm currently using a "pick an arbitrary source, try all other nodes" method)
如果你说 "treat all the other nodes as sinks," 这是对源的外边缘进行的简单度数计算。
编辑：这不完全是度数计算，因为边是加权的，但它只是将边权重相加，不需要搜索。
it must require equal flow in both directions on any edge.
不存在这样的要求（流网络是有向图——任何无向边都映射到两条反平行边，对于特定的流问题，只使用其中一条边）。