| 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 |
|||||||||||
