 |
 |
5 of 32 |  |
 |
 |
MIT
Minimum Cut
l
Min-cut: smallest cut of graph
»
Most likely cut to “disappear” in G(p
)
»
Most likely to have less than k
edges
»
Value c
l
If p < 1/c, disconnect often
»
if p<<(log
n)/
c, non-negligible disconnect
»
compare to Erdos-Renyi (log
n)/
n
l
Can we find min-cuts? Count them?