| Analyze Trees |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Recall: [G] packs c
(directed)-edge |
||||||||||
| disjoint spanning
trees |
|||||||||||
| l | Corollary: in such a packing, some tree |
||||||||||
| crosses min-cut
only twice |
|||||||||||
| l | To find min-cut: |
||||||||||
| » | find tree packing |
||||||||||
| » | find smallest cut
with 2 tree edges crossing |
||||||||||
