1
$\begingroup$

I'm trying to resolve an example from book.

T = (V, E) is a full binary tree, and |V| = n. Show that there exist n!/2^((n-1)/2) full orderings on V which extend transverse ordering.

As I know there are three main types of full orderings - post-, -pre, symmetrical. Having binary tree with root A and two leaves B, C. As I understand only order of leaves can change.

So for preorder we get A < B < C; A < C < B.

For postorder: C < B < A; B < C < A;

Symmetrical: B < A < C; C < A < B.

Finally we get 6 different full orderings, but according to the formula should get (1 * 2 * 3) / 2 ^ ((3-1)/2) = 3. Can anyone help me, maybe I misunderstand conditions of the task?

$\endgroup$
  • $\begingroup$ I’m not familiar with your terminology, but I suspect that transverse ordering refers to the partial ordering of nodes that simply orders each level from left to right but imposes no order relation between nodes on different levels. In that case your original tree has a transverse order with an isolated point $A$ and a chain $B<C$, and there are just $3$ ways to insert $A$ into the chain: $A<B<C$, $B<A<C$, and $B<C<A$. $\endgroup$ – Brian M. Scott Feb 17 '16 at 19:51
  • $\begingroup$ But if not to change the order of nodes within levels, then all the tree will have only three full orders no matter how much levels one adds to it, while according to the formula number of orders should increase significantly with each added level. $\endgroup$ – goodking Feb 17 '16 at 20:13
  • $\begingroup$ That’s not true. The tree in my answer has $30$ linear orders extending the transverse order. Ignore what you know about tree traversal algorithms: this problem really does not have anything to do with them. $\endgroup$ – Brian M. Scott Feb 17 '16 at 20:16
1
$\begingroup$

HINT: I’m not familiar with your terminology, but I suspect that transverse ordering refers to the partial ordering of nodes that simply orders each level from left to right but imposes no order relation between nodes on different levels. In that case your original tree has a transverse order with an isolated point $A$ and a chain $B<C$, and there are just $3$ ways to insert $A$ into the chain: $A<B<C$, $B<A<C$, and $B<C<A$. This interpretation also fits the desired result, that there are $$\frac{n!}{2^{(n-1)/2}}$$ linear extensions of the transverse partial order on the nodes of the tree.

There are $n!$ possible permutations (linear orderings) of the nodes, but of course some of them don’t extend the transverse order. Say that two permutations of the nodes are equivalent one can be transformed into the other by one or more interchanges of sibling nodes. For instance, in your little tree with three vertices the permutations $ABC$ and $ABC$ are equivalent, because each can be obtained from the other by interchanging the siblings $B$ and $C$. In the tree shown below, the permutations $ABCDE$, $ACBDE$, $ABCED$, and $ABCED$ are all equivalent: the second is obtained from the first by interchanging $B$ and $C$, the third by interchanging $D$ and $E$, and the fourth by making both interchanges.

                               A  
                              / \  
                             B   C  
                            / \  
                           D   E
  • Show that this notion of equivalence really is an equivalence relation on the set of permutations of the nodes of the tree.
  • Show that each equivalence class contains $2^{(n-1)/2}$ permutations.
  • Show that in each equivalence class there is exactly one permutation that extends the transverse ordering.
$\endgroup$
  • $\begingroup$ Thank you so much! Transverse ordering applies only to sibling nodes $\endgroup$ – goodking Feb 18 '16 at 18:22
  • $\begingroup$ 1. Equivalence relation must be reflexive, symmetric and transitive which can be easily proved in this case. $\endgroup$ – goodking Feb 18 '16 at 18:22
  • $\begingroup$ 2. p=(n-1)/2 is the number of nodes which are not leaves, that is which have two child nodes. We can consider each such node as an object which can have two states(interchanging its child nodes). The number of combinations of p objects each of which can be selected in 2 ways is 2^p. So we get 2^((n-1)/2). $\endgroup$ – goodking Feb 18 '16 at 18:23
  • $\begingroup$ 3. Here I didn't quite understand you. I think that each permutation extends traversal ordering. Since with any of these permutations, each two nodes from the tree have order relation. We just select groups of permutations any member of which can't be achieved with any siblings changes of other permutations. Am I not right? $\endgroup$ – goodking Feb 18 '16 at 18:23
  • $\begingroup$ @goodking: You’ve done fine with the first two, but you’re wrong about the third. The point is that the original tree already has a specified ordering of each level, so when you switch two siblings, you get a permutation that does not extend that ordering: it disagrees with the original transverse ordering on the two nodes that you switched. $\endgroup$ – Brian M. Scott Feb 18 '16 at 18:25

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.