 |
 |
4 of 32 |  |
 |
 |
MIT
Cuts in Graphs
l
A cut
is a vertex partition
l
Value is number (or total weight) of
crossing edges
l
Determines connectivity
»
disconnected iff no edges cross some cut
»
k
-connected iff every cut has
k
edges