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

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

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

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

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

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

Двоичное дерево

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

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

N-арные деревья

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

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

Свойства

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

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

  • Число различных деревьев, которые можно построить на нумерованных вершинах, равно ( Теорема Кэли ).
  • Производящая функция
для числа неизоморфных корневых деревьев с вершинами удовлетворяет функциональному уравнению
.
  • Производящая функция
для числа неизоморфных деревьев с вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:
  • При верна следующая асимптотика
где и определённые константы, , .

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

  • Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой-либо вершины будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем при движении по ребру в первый раз и при движении по ребру второй раз (в обратном направлении). Если — число рёбер дерева, то через шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из и (код дерева) длины позволяет однозначно восстанавливать не только само дерево , но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с вершинами:
  • Код Прюфера сопоставляет произвольному конечному дереву с вершинами последовательность из чисел от до с возможными повторениями. Например дерево на рисунке имеет код Прюфера (4,4,4,5). Между деpевьями с помеченными вершинами и их кодами Прюфера существует взаимно однозначное соответствие. Из кода Прюфера выводится формула Кэли .
  • Дерево можно задать в виде стpоки, содержащей символы, помечающие вершины деpева, а также открывающие и закрывающие кpуглые скобки. Между деpевьями и их линейными скобочными записями существует взаимно однозначное соответствие.

См. также

Примечания

  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 года.

Литература

Источник —

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