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

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''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.

Навигация