是否有不止一个最小割口的流网系列？ [英] Are there more than one families of flow networks with non unique minimum cuts?

问题描述

我想知道构建具有多个最小割口的流动网络的唯一方法是否是包括至少两个具有相同容量的连续边，以使其中任何一个都在最小割口集中。

很明显，这种网络最简单的类型是所有边缘具有相同容量的路径，因此在这种情况下| E |中的任何一个边缘可以是将S与T分开的边缘。

这是构造此类网络的唯一方法吗？如果是这样，我怎么证明呢？

解决方案

我不认为这是真的：

考虑以下网络：

  A-> B容量4 
 B-> ; C容量2 
 A-> C容量1 
 C-> D容量3 
  

我们既可以削减（A，B，C）/（D），也可以削减（A，B）/（C，D）两者都削减3。

I'm wondering if the only way to construct a flow network with several minimum cuts is to include at least 2 consecutive edges with the same capacity, such that any one of them will be in the minimum cut edge set.

It's clear that the simplest kind of such a network is a path with all edges of the same capacity, so in that case any one of |E| edges can be the edge separating S from T.

Is this the only way to construct such networks? If so, how can I prove it?

解决方案

I don't think this is true:

Consider this network:

A->B capacity 4
B->C capacity 2
A->C capacity 1
C->D capacity 3

We can either have a cut (A,B,C)/(D) or (A,B)/(C,D) both with cut of 3.

这篇关于是否有不止一个最小割口的流网系列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！