MIT
18
Analysis II
lAlgorithm
succeeds if never accidentally contracts min-cut edge
lContracts
#vertices from n down to 2
lWhen
k
vertices, chance of error is 2/k
»thus,
chance of being right is 1-2/k
lPr[always
right] is product of probabilities of being right each
time