What is the formal method (map, transformation, ...) of the following exemplarly given tree into a binary tree?

55 Views Asked by At

I have a given (rooted, directed, labeled) tree that will be transformed into the binary one as shown by the figure below.

Some algebraic/graph-theoretic tranformations such as path contraction are well known. But what is the official method/formalism of the transformation below?

Transformation of a tree into a binary tree

1

There are 1 best solutions below

1
On BEST ANSWER

The edges are changed according to the following procedure: whenever a node $v$ has edges $w_1, w_2, \dots, w_n$ on the old tree (we sort $w_1, w_2, \dots, w_n$ in increasing order of label) we draw an edge from $v$ to $w_1$, and edges from $w_i$ to $w_{i+1}$ for each $i =1,\dots,n-1$, in the new tree.