Дерево (теория графов)

Дерево — это связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.

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

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.

Связанные определенияПравить

• Степень вершины — количество инцидентных ей ребер.

• Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).

• Узел ветвления — неконцевой узел.

• Дерево с отмеченной вершиной называется корневым деревом.
  • $m$$m$ -й ярус дерева $T$$T$  — множество узлов дерева, на уровне $m$$m$  от корня дерева.
  • частичный порядок на вершинах: $u\prec <!--\; \prec \; -->v$$u\prec v$ , если вершины $u$$u$  и $v$$v$  различны и вершина $u$$u$  лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной $v$$v$ .
  • корневое поддерево с корнем $v$$v$  — подграф $\{v\}\cup \{w\mid v<w\}$ .
  • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.

• Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

1. уровень корня дерева $T$$T$  равен 0;
2. уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева $T$$T$ , содержащего данный узел.

• Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

• Несводимым называется дерево, в котором нет вершин степени 2.

• Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
• Центроид — вершина, при удалении которой размеры получившихся компонент связности не превышают $\frac{n}{2}$${\dfrac {n}{2}}$  (половины размера исходного дерева)

Двоичное деревоПравить

 

Простое бинарное дерево размера 9 и высоты 3, с корнем значения 2. Это дерево не сбалансировано и не отсортировано.

Термин двоичное дерево (применяется так же термин бинарное дерево) имеет несколько значений:

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

N-арные деревьяПравить

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

• N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
• N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

СвойстваПравить

• Дерево не имеет кратных рёбер и петель.
• Любое дерево с $n$$n$  вершинами содержит $n-<!--\; -\; -->1$$n-1$  ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда $B-<!--\; -\; -->P=1$$B-P=1$ , где $B$$B$  — число вершин, $P$$P$  — число рёбер графа.
• Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной простой цепью.
• Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
• Любое дерево является двудольным графом.
• Любое дерево, множество вершин которого не более чем счётное, является планарным графом.
• Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

Подсчёт деревьевПравить

Основная статья: Теорема Кэли о числе деревьев

• Число различных деревьев, которые можно построить на $n$$n$  нумерованных вершинах, равно $n^{n-<!--\; -\; -->2}$$n^{{n-2}}$  (Теорема Кэли).
• Производящая функция

$T(z)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{T}_n{z}^n$$T(z)=\sum _{n=1}^{\infty }T_{n}z^{n}$ 

для числа $T_n$$T_{n}$  неизоморфных корневых деревьев с $n$$n$  вершинами удовлетворяет функциональному уравнению

$T(z)=z\exp <!--\; \; -->\underset{r=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{1}{r}T(z^r)$$T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})$ .

• Производящая функция

$t(z)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{t}_n{z}^n$$t(z)=\sum _{n=1}^{\infty }t_{n}z^{n}$ 

для числа $t_n$$t_{n}$  неизоморфных деревьев с $n$$n$  вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

$t(z)=T(z)-<!--\; -\; -->\frac{1}{2}\left(T^2(z)-<!--\; -\; -->T(z^2)\right).$$t(z)=T(z)-{\frac {1}{2}}\left(T^{2}(z)-T(z^{2})\right).$ 

• При $n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$n\to \infty$  верна следующая асимптотика

$t_n\sim <!--\; \sim \; -->C{\mathrm{\alpha <!--\; \alpha \; -->}}^n/n^{5/2}$$t_{n}\sim C\alpha ^{n}/n^{5/2}$ 

где $C$$C$  и $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$  определённые константы, $C=0,\mathrm{534948...}$$C=0,534948...$ , $\mathrm{\alpha <!--\; \alpha \; -->}=2,\mathrm{95576...}$$\alpha =2,95576...$ .

Кодирование деревьевПравить

• Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой-либо вершины будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем $0$$0$  при движении по ребру в первый раз и $1$$1$  при движении по ребру второй раз (в обратном направлении). Если $m$$m$  — число рёбер дерева, то через $2m$$2m$  шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из $0$$0$  и $1$$1$  (код дерева) длины $2m$$2m$  позволяет однозначно восстанавливать не только само дерево $D$$D$ , но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с $n$$n$  вершинами:

  $t_{n}\leq T_{n}<2^{2n}$ 

 

• Код Прюфера сопоставляет произвольному конечному дереву с $n$$n$  вершинами последовательность из $n-<!--\; -\; -->2$$n-2$  чисел от $1$$1$  до $n$$n$  с возможными повторениями. Например дерево на рисунке имеет код Прюфера (4,4,4,5). Между деpевьями с помеченными вершинами и их кодами Прюфера существует взаимно однозначное соответствие. Из кода Прюфера выводится формула Кэли.

• Дерево можно задать в виде стpоки, содержащей символы, помечающие вершины деpева, а также открывающие и закрывающие кpуглые скобки. Между деpевьями и их линейными скобочными записями существует взаимно однозначное соответствие.

См. такжеПравить

• Глоссарий теории графов
• Лес непересекающихся множеств
• Список структур данных (деревья)

ЛитератураПравить

• Дональд Кнут. Искусство программирования, том = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд. — М.: Вильямс, 2006. — Т. 1. Основные алгоритмы. — 720 с. — ISBN 0-201-89683-4.
• Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — 336 с.
• Харари Ф. Теория графов. — М.: Мир, 1973. — 302 с.