ru.wikipedia.org

Дерево (теория графов) — Википедия

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

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

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

  • Степень вершины — количество инцидентных ей ребер.
  • Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).
  • Узел ветвления — неконцевой узел.
  • Дерево с отмеченной вершиной называется корневым деревом.
  • Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:
  1. уровень корня дерева {\displaystyle T} равен 0;
  2. уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева {\displaystyle T}, содержащего данный узел.
  • Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
  • Несводимым называется дерево, в котором нет вершин степени 2.
  • Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
  • Центроид — вершина, при удалении которой размеры получившихся компонент связности не превышают {\displaystyle {\dfrac {n}{2}}} (половины размера исходного дерева)
Простое бинарное дерево размера 9 и высоты 3, с корнем значения 2. Это дерево не сбалансировано и не отсортировано.

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

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

  • N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
  • N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.
  • Дерево не имеет кратных рёбер и петель.
  • Любое дерево с {\displaystyle n} вершинами содержит {\displaystyle n-1} ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда {\displaystyle B-P=1}, где {\displaystyle B} — число вершин, {\displaystyle P} — число рёбер графа.
  • Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной простой цепью.
  • Любое ребро дерева является мостом. Обратное неверно: граф, все рёбра которого являются мостами, может быть как деревом, так и лесом.
  • Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
  • Любое дерево является двудольным графом.
  • Любое дерево, множество вершин которого не более чем счётное, является планарным графом.
  • Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.
{\displaystyle T(z)=\sum _{n=1}^{\infty }T_{n}z^{n}}
для числа {\displaystyle T_{n}} неизоморфных корневых деревьев с {\displaystyle n} вершинами удовлетворяет функциональному уравнению
{\displaystyle T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})}.
  • Производящая функция
{\displaystyle t(z)=\sum _{n=1}^{\infty }t_{n}z^{n}}
для числа {\displaystyle t_{n}} неизоморфных деревьев с {\displaystyle n} вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:
{\displaystyle t(z)=T(z)-{\frac {1}{2}}\left(T^{2}(z)-T(z^{2})\right).}
  • При {\displaystyle n\to \infty } верна следующая асимптотика
{\displaystyle t_{n}\sim C\alpha ^{n}/n^{5/2}}
где {\displaystyle C} и {\displaystyle \alpha } определённые константы, {\displaystyle C=0,534948...}, {\displaystyle \alpha =2,95576...}.
  1. ↑ § 13. Определение дерева // Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.. — М.: Наука, Физматлит, 1990. — С. 53. — 384 с. — 22 000 экз. — ISBN 5-02-013992-0.
  2. ↑ Альфс Берзтисс. Глава 3. Теория графов. 3.6. Деревья // Структуры данных = A. T. Berztiss. Data structures. Theory and practice. — М.: Статистика, 1974. — С. 131. — 10 500 экз.
  3. ↑ Дискретная математика: алгоритмы. Формула Кэли. Дата обращения: 29 октября 2009. Архивировано из оригинала 14 июня 2009 года.