确定最小切割的唯一性 [英] 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.

我正在努力解决的问题是确定图中 G = (V, E) 中特定的最小 s-t 切割是否是唯一的.根据 some min-cut 非常简单rel="noreferrer">这个例子，但是你会如何显示它是 最小剪裁?

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:
您的链接为我们提供了一个最小切割，即残差图中从 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 可到达的顶点组(意思是所有可以到达 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:
这个组也是一个最小剪辑(或者实际上是 S那个组，准确地说).

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屋！