 |
 |
17 of 32 |  |
 |
 |
MIT
Counting Minimum Cuts
l
Lemma: at most minimum cuts
l
Proof:
»
suppose
k
minimum cuts
»
each output by CA with probability
»
disjoint events, so
l
Tight: consider cycle
÷
÷
ø
ö
ç
ç
è
æ
2
n
1
2
-
÷
ø
ö
ç
è
æ
n
1
1
2
£
÷
ø
ö
ç
è
æ
-
n
k