 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
l |
Original CA
finds any given min-cut with
|
|
|
probability at
least 2/n(n-1)
|
|
|
l |
Only one cut
found
|
|
|
l |
Disjoint events,
so probabilities add
|
|
|
l |
So at most n(n-1)/2 min-cuts
|
|
|
|
» |
probabilities
would sum to more than one
|
|
|
l |
Tight
|
|
|
|
» |
Cycle has exactly
this many min-cuts
|
|