MIT
52
Analyze Trees
lRecall: [G] packs c
(directed)-edge disjoint spanning trees
lCorollary: in such a
packing, some tree crosses min-cut only twice
lTo
find min-cut:
»find
tree packing
»find
smallest cut with 2 tree edges crossing