Binomial tree

Материал из WikiGrapp
Версия от 17:57, 21 февраля 2012; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.