I have read an example from a book that takes the algorithm from the 2013-local competition.
Who can say how we can calculate this question?
How much is there in the tree without deduction, in which
npeak andn-1edges?
Any thoughts or hints?
Sunday, 15 April 2012
c++ - How many min-cut is in Tree without weights? -
The minimum cut size is one and is exactly n - 1 like this The cut (we can cut any edge of the tree and get two non-empty components)
Why is this a matter?
The size of the minimum cut is one and it can not be small because the graph is connected. Now we can remove one edge, by removing one edge, specifically sets the corner of two sets and we have the n - 1 the edges, thus we have the n - 1 < / Code> is the minimum cut.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment