Binomial tree

Binomial tree — биномиальное дерево.

There are several equivalent definitions of a binomial tree. One recursive definition is to define the tree [math]\displaystyle{ B_{0} }[/math] as a single vertex, and then the rooted tree [math]\displaystyle{ B_{i+1} }[/math] is obtained by taking one copy of each of [math]\displaystyle{ B_{0} }[/math] through [math]\displaystyle{ B_{i} }[/math], adding a root, and making the old roots the children of the new root. In particular, the tree [math]\displaystyle{ B_{i} }[/math] has [math]\displaystyle{ 2^{i} }[/math] vertices.

An equivalent definition is based on the corona of a graph. Recall that the corona of a graph is obtained by adding a new leaf adjacent to each existing vertex. Then [math]\displaystyle{ B_{i+1} }[/math] is the corona of [math]\displaystyle{ B_{i} }[/math].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.