Binomial tree: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Binomial tree''' --- биномиальное дерево. There are several equivalent definitions of a '''binomial tree'''. One recursive definition is to de…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Binomial tree''' --- биномиальное дерево.  
'''Binomial tree''' — ''[[биномиальное дерево]].''


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


An equivalent definition is based on the ''corona'' of a graph.
An equivalent definition is based on the ''[[corona]]'' of a [[graph, undirected graph, nonoriented graph|graph]].
Recall that the corona of a graph is obtained by adding a new leaf
Recall that the corona of a graph is obtained by adding a new [[leaf]]
adjacent to each existing vertex. Then <math>B_{i+1}</math> is the corona of
[[adjacent vertices|adjacent]] to each existing vertex. Then <math>B_{i+1}</math> is the corona of
<math>B_{i}</math>.
<math>B_{i}</math>.
==Литература==
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 16:31, 23 октября 2018

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.