确定一个最小割的独特性 [英] Determining the uniqueness of a min-cut

问题描述

免责声明：本的已的一门功课的问题的期限已过，现在，这样的讨论可以继续，而无需担心

Disclaimer: this was a homework problem. The deadline has passed now, so discussions can continue without needing to worry about that.

我挣扎的问题是，以确定是否一个特定的最小的 ST 的切图的 G =（V，E）的是独一无二的。这是很简单找到的部分的分切采用最大流算法根据的这个例子，但你会如何表现出来的的在的分切？

The problem I'm struggling with is to determine whether a particular minimum s-t cut in a graph G = (V, E) is unique. It's simple enough to find some min-cut using a max-flow algorithm as per this example, but how would you show it's the min-cut?

推荐答案

好了，因为你不希望整个马上回答，我会给你一些提示。读你觉得是必要的你，如果你放弃了许多 - 请继续阅读所有

Ok, since you don't want the whole answer right away, I'm gonna give you a few hints. Read as many as you feel are necessary for you, and if you give up - go ahead and read them all.

1
切割是唯一的当且仅当没有其他的分切。

1:
The cut is unique iff there is no other min-cut.

2
如果你在寻找不同的分切成功，那么第一分切不是唯一的。

2:
If you succeed in finding a different min-cut, then the first min-cut isn't unique.

3
您的链接给了我们1分钟切，这是从s中残留图中所有可到达顶点。你能想到的方式来获得不同的剪裁，不一定是相同的？

3:
Your link gave us one min-cut, which is all the reachable vertices from s in the residual graph. Can you think of a way to obtain a different cut, not necessarily the same?

4：
没有我们为什么把这些顶点到达从各S？

4:
Why did we take those vertices reachable from s in particular?

5：
也许我们可以做一些类似于从T？

5:
Maybe we can do something analogous from t?

6：
看同样的残留图，开始在t。在箭（这意味着所有的顶点可以达到t）的逆转的方向看该组顶点可达的距离吨。

6:
Look at the same residual graph, starting at t. Look at the group of vertices reachable from t in the reverse direction of the arrows (meaning all the vertices which can reach t).

7
这组也是最小割（或的确对\该组，以precise）。

7:
This group is also a min-cut (or actually S \ that group, to be precise).

8（最后的答案）：
如果切等同于原来的切口，那么就只有一个。否则，你只是发现2切口，所以原来的不可能是唯一的。

8 (final answer):
If that cut is identical to your original cut, then there is only one. Otherwise, you just found 2 cuts, so the original one can't possibly be unique.

这篇关于确定一个最小割的独特性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！