Binomial tree

Материал из WikiGrapp
Перейти к:навигация, поиск

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

There are several equivalent definitions of a binomial tree. One recursive definition is to define the tree B_{0} as a single vertex, and then the rooted tree B_{i+1} is obtained by taking one copy of each of B_{0} through B_{i}, adding a root, and making the old roots the children of the new root. In particular, the tree B_{i} has 2^{i} 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 B_{i+1} is the corona of B_{i}.

Литература

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