 |
 |
13 of 32 |  |
 |
 |
MIT
Analysis II
l
Algorithm succeeds if never accidentally
contracts min-cut edge
l
Contracts #vertices from n
down to
2
l
When k
vertices, chance of error is 2/k
»
thus, chance of being right is 1
-2/
k
l
Pr[always right] is product of
probabilities of being right each time