30
Minimum Cut Problem
Given:
undirected graph
G=(V,E)
Cut
of a graph …
a partition of
V
into
S ∪ T
S,T
disjoint and both non-empty
its
weight
is the number of edges between
S
and
T
:
ω(
S,T
) = | { {s,t}∈
E
: s∈
S
, t∈
T
} |
Minimum cut problem
… find a cut of
G
with minimal weight
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}