Binomial tree: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Binomial tree''' --- биномиальное дерево. There are several equivalent definitions of a '''binomial tree'''. One recursive definition is to de…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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.