online advertising

Friday, October 30, 2015

Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 1

Problem:

How many different minimum cuts are there in a tree with $ n $ nodes (ie. $ n - 1 $ edges) ?

Solution:

Any edge is a minimum cut, so there are n - 1 minimum cuts.

No comments:

Post a Comment