Русская Википедия:Дерево (теория графов)
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Шаблон:Другие значения Дерево — это связный ациклический граф.[1] Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.
Лес — множество деревьев.
Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.[2]
Связанные определения
- Степень вершины — количество инцидентных ей ребер.
- Концевой узел (лист, терминальная вершина) — узел со степенью 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> (половины размера исходного дерева)
Двоичное дерево
Термин двоичное дерево (применяется так же термин бинарное дерево) имеет несколько значений:
- Неориентированное дерево, в котором степени вершин не превосходят 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) вершинами.
- Любое дерево является двудольным графом.
- Любое дерево, множество вершин которого не более чем счётное, является планарным графом.
- Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.
Подсчёт деревьев
- Число различных деревьев, которые можно построить на <math>n</math> нумерованных вершинах, равно <math>n^{n-2}</math> (Теорема Кэли[3]).
- Производящая функция
- <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>
- Код Прюфера сопоставляет произвольному конечному дереву с <math>n</math> вершинами последовательность из <math>n-2</math> чисел от <math>1</math> до <math>n</math> с возможными повторениями. Например дерево на рисунке имеет код Прюфера (4,4,4,5). Между деpевьями с помеченными вершинами и их кодами Прюфера существует взаимно однозначное соответствие. Из кода Прюфера выводится формула Кэли.
- Дерево можно задать в виде стpоки, содержащей символы, помечающие вершины деpева, а также открывающие и закрывающие кpуглые скобки. Между деpевьями и их линейными скобочными записями существует взаимно однозначное соответствие.
См. также
Примечания
Литература
Шаблон:Деревья (структуры данных)
