3
$\begingroup$

Given an undirected tree (i.e. a tree without any designated root) of even number of nodes. The task is to remove as many edges from the tree as possible to obtain a forest of trees, where each such tree contains even number of nodes. And return/output number of removed edges as an output/answer.

Counting maximum number of removed edges is relatively simple:

  1. Choose any node as a root node;
  2. Recursively traverse a tree using depth-first approach;
  3. Count number of children of each sub-tree (from bottom to up), and cut sub-tree from the tree if this sub-tree has even number of children (i.e. simply increment counter of removed edges);

This solution is correct but I don't understand why.

I would like to see proof of correctness of such algorithm.

In particular, I have the following doubts (when I'm thinking on this solution):

  1. Why starting DFS from any chosen root gives correct maximum number of removed edges?
  2. Why cutting sub-trees with even number of children from bottom to up gives correct result?

I wrote on paper all possible configurations 1, 2, 3, 4, 5, 6-nodes of undirected trees.

For example, there are two possible configurations of undirected tree with 4 nodes:

(a)

x-x-x-x

(b)

x-x-x
  |
  x

In (a), you can split a tree into 2 sub-trees with 2 nodes each.

In (b), you can not do it since it will be two sub-trees of odd number of nodes (with 1 node and with 3 nodes respectively).

So my doubts based on suggestions:

  1. What if it depends where you start cutting sub-trees?
  2. What if greedy cutting sub-trees with even number of children from bottom to up doesn't give correct maximum number of removed edges? (continue of first question)

This puzzle is described on HackerRank as "Even Tree". Their editorial and discussion just declared algorithm but they don't say why it works. Also, I found discussion on stackoverflow but they also don't give explanation why such approach works.

$\endgroup$
  • $\begingroup$ You're looking for a maximum matching, no? $\endgroup$ – Pål GD Mar 22 '15 at 13:43
  • $\begingroup$ @PålGD Not exactly. Take a look at my comments below. $\endgroup$ – uintptr_t Mar 22 '15 at 18:18
0
$\begingroup$

I got my "Aha! Gotcha" moment when I changed my point of view from nodes (as root of a subtree) to edges. Let me explain.

The set of edges that can be cut is a "static property", the set of choices is not changed by the earlier cuts that have been made. Any edge is considered to be "even" if on both sides it has an even number of nodes in the tree. Clearly we can only cut even edges. But also, cutting an even edge does not change the even property of the remaining edges, as we merely remove an even number of nodes in subtrees.

So, we are set to find the even edges, and we will cut them all. The proposed solution uses DFS, but any decent traversal will do I would think. The property that a subtree has an even number of nodes now means (in my terminology above) that the edge outside leading to the root of the subtree is in fact even.

$\endgroup$
  • $\begingroup$ Thank for you the insight. But it's still not entirely clear for me that removing edge doesn't affect on which edges could be removed after. I guess there are some proof by contradiction. But I failed to find one. $\endgroup$ – uintptr_t Mar 22 '15 at 12:10
  • $\begingroup$ Removing an "even" edge deletes an even number of nodes. For other each edge $e$ in the tree these deleted nodes can only be at one side of the edge $e$. Thus it will not change evenness of $e$. $\endgroup$ – Hendrik Jan Mar 22 '15 at 12:35
  • $\begingroup$ I get it! Since a tree by definition is a graph with no cycles, any edge connecting two vertices is only edge between two sub-trees. When we remove this edge, these two sub-trees become two completely independent trees. So we don't care about structure of these trees at all, we only care about how many vertices in these trees. Therefore if before removing this edge, we remove another edge in any of these two sub-trees, then for us only number of vertices in sub-tree was changed. $\endgroup$ – uintptr_t Mar 22 '15 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.