Просмотр кода страницы Дерево (теория графов)

{{другие значения|Дерево (значения)}}
'''Дерево''' — [[связный граф|связный]] [[ациклический граф]].<ref>{{книга|часть=§ 13. Определение дерева|заглавие=Лекции по теории графов|ответственный=Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.|место={{М}}|издательство=Наука, Физматлит|год=1990|страницы=53|страниц=384|isbn=5-02-013992-0|тираж=22000}}</ref> Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.

'''Лес''' — множество деревьев.

'''Ориентированное (направленное) дерево''' — ациклический [[ориентированный граф]], в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется ''корнем'' дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются ''концевыми вершинами'' или ''листьями''.<ref>{{книга|автор=Альфс Берзтисс.|часть=Глава 3. Теория графов. 3.6. Деревья|заглавие=Структуры данных|оригинал=A. T. Berztiss. Data structures. Theory and practice|место={{М}}|издательство=Статистика|год=1974|страницы=131|тираж=10500}}</ref>

== Связанные определения ==
* ''Степень вершины'' — количество инцидентных ей ребер.
* ''Концевой узел'' (''лист'', ''терминальная вершина'') — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).
* ''Узел ветвления'' — неконцевой узел.
* Дерево с отмеченной вершиной называется ''корневым деревом''.
** <math>m</math>-й ''ярус'' дерева <math>T</math> — множество узлов дерева, на уровне <math>m</math> от корня дерева.
** [[Частично упорядоченное множество#Формальное определение|частичный порядок]] на вершинах: <math>u \prec v</math>, если вершины <math>u</math> и <math>v</math> различны и вершина <math>u</math> лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной <math>v</math>.
** ''корневое поддерево'' с корнем <math>v</math> — подграф <math>\{v\}\cup\{w\mid v<w\}</math>.
** В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется ''свободным''.
* ''Уровень узла'' — длина пути от корня до узла. Можно определить рекурсивно:
# уровень корня дерева <math>T</math> равен 0;
# уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева <math>T</math>, содержащего данный узел.

* ''[[Остовное дерево]]'' (''остов'') — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются '''хордами''' графа относительно остова.
* ''Несводимым'' называется дерево, в котором нет вершин степени 2.
* ''Лес'' — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
* ''Центроид'' — вершина, при удалении которой размеры получившихся компонент связности не превышают <math>\dfrac{n}{2}</math> (половины размера исходного дерева)

== Двоичное дерево ==
[[Файл:binary tree.svg|right|192px|thumb|Простое бинарное дерево размера 9 и [[Высота дерева|высоты]] 3, с корнем значения 2. Это дерево не сбалансировано и не отсортировано.]]
Термин ''[[двоичное дерево]]'' (применяется так же термин бинарное дерево) имеет несколько значений:

* [[Неориентированный граф|Неориентированное]] дерево, в котором [[Степень вершины (теория графов)|степени вершин]] не превосходят 3.
* [[Ориентированный граф|Ориентированное]] дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
* Абстрактная [[структура данных]], используемая в [[Программирование|программировании]]. На двоичном дереве основаны такие структуры данных, как [[двоичное дерево поиска]], [[двоичная куча]], [[красно-чёрное дерево]], [[АВЛ-дерево]], [[фибоначчиева куча]] и др.

== N-арные деревья ==
N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.

* '''N-арное дерево''' (неориентированное) — это дерево (обычное, неориентированное), в котором [[Степень вершины (теория графов)|степени вершин]] не превосходят N+1.
* '''N-арное дерево''' (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

== Свойства ==
* Дерево не имеет кратных рёбер и [[Петля (теория графов)|петель]].
* Любое дерево с <math>n</math> вершинами содержит <math>n-1</math> ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда <math>B-P=1</math>, где <math>B</math> — число вершин, <math>P</math> — число рёбер графа.
* Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной [[Глоссарий теории графов#простая цепь|простой цепью]].
* Любое ребро дерева является [[Мост_(теория_графов)|мостом]]. Обратное неверно: граф, все рёбра которого являются мостами, может быть как деревом, так и лесом.
* Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
* Любое дерево является [[Двудольный граф#Д|двудольным графом]].
* Любое дерево, множество вершин которого не более чем счётное, является [[Планарный граф|планарным графом]].
* Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

== Подсчёт деревьев ==
{{main|Теорема Кэли о числе деревьев}}
* Число различных деревьев, которые можно построить на <math>n</math> нумерованных вершинах, равно <math>n^{n-2}</math> ('''Теорема [[Кэли, Артур|Кэли]]'''<ref>{{Cite web |url=http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008/ |title=Дискретная математика: алгоритмы. Формула Кэли<!-- Заголовок добавлен ботом --> |accessdate=2009-10-29 |archiveurl=https://web.archive.org/web/20090614011705/http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 |archivedate=2009-06-14 |deadlink=yes }}</ref>).
* Производящая функция
:: <math>T(z)=\sum_{n=1}^\infty T_nz^n</math>
: для числа <math>T_n</math> неизоморфных корневых деревьев с <math>n</math> вершинами удовлетворяет функциональному уравнению
:: <math>T(z)=z\exp\sum_{r=1}^\infty\frac1r T(z^r)</math>.
* Производящая функция
:: <math>t(z)=\sum_{n=1}^\infty t_nz^n</math>
: для числа <math>t_n</math> неизоморфных деревьев с <math>n</math> вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:
:: <math>t(z)=T(z)-\frac12\left(T^2(z)-T(z^2)\right).</math>
* При <math>n\to\infty</math> верна следующая асимптотика
:: <math>t_n\sim C\alpha^n/n^{5/2}</math>
: где <math>C</math> и <math>\alpha</math> определённые константы, <math>C=0,534948...</math>, <math>\alpha=2,95576...</math>.

== Кодирование деревьев ==
* Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой-либо вершины будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем <math>0</math> при движении по ребру в первый раз и <math>1</math> при движении по ребру второй раз (в обратном направлении). Если <math>m</math> — число рёбер дерева, то через <math>2m</math> шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из <math>0</math> и <math>1</math> (код дерева) длины <math>2m</math> позволяет однозначно восстанавливать не только само дерево <math>D</math>, но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с <math>n</math> вершинами:
*: <math>t_n\le T_n< 2^{2n}</math>

[[Файл:Tree_graph.svg|справа|обрамить]]

* [[Код Прюфера]] сопоставляет произвольному конечному дереву с <math>n</math> вершинами последовательность из <math>n-2</math> чисел от <math>1</math> до <math>n</math> с возможными повторениями. Например дерево на рисунке имеет код Прюфера (4,4,4,5). Между деpевьями с помеченными вершинами и их кодами Прюфера существует взаимно однозначное соответствие. Из кода Прюфера выводится [[Теорема Кэли о числе деревьев|формула Кэли]].
* Дерево можно задать в виде стpоки, содержащей символы, помечающие вершины деpева, а также открывающие и закрывающие кpуглые скобки. Между деpевьями и их линейными скобочными записями существует взаимно однозначное соответствие.

== См. также ==
* [[Глоссарий теории графов]]
* [[Лес непересекающихся множеств]]
* [[Проект:Информационные технологии/Списки/Список структур данных#Trees|Список структур данных (деревья)]]
== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|автор = [[Кнут, Дональд Эрвин|Дональд Кнут]].
|заглавие = Искусство программирования, том 
|оригинал = The Art of Computer Programming, vol. 1. Fundamental Algorithms
|том = 1. Основные алгоритмы
|издание = 3-е изд
|место = М. |издательство = [[Вильямс (издательство)|Вильямс]]
|год = 2006
|страниц = 720
|isbn = 0-201-89683-4
}}
* {{книга
|автор = [[Оре, Ойстин|Оре О.]] 
|заглавие = Теория графов
|издание = 2-е изд
|место = М. |издательство = [[Наука (издательство)|Наука]]
|год = 1980
|страниц = 336
}}
* {{книга
|автор = [[Харари, Фрэнк|Харари Ф.]]
|заглавие = Теория графов
|место = М. |издательство = [[Мир (издательство)|Мир]]
|год = 1973
|страниц = 302
}}
{{Деревья (структуры данных)}}

[[Категория:Теория графов]]
[[Категория:Деревья (структуры данных)]]
[[Категория:Деревья (графы)|*]]