1033
правки
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. | |||