CODEWITHSUNDEEP
algorithm
Pavel
Pavel

Reputation: 1

Are there more than one families of flow networks with non unique minimum cuts?

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?

Upvotes: 1

Views: 1040

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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.

enter image description here

Upvotes: 1

Related Questions