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

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

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

Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:

  1. существует один корень дерева T
  2. остальные узлы (за исключением корня) распределены среди m\geq 0 непересекающихся множеств T1,...,Tm, и каждое из множеств является деревом; деревья T1,...,Tm называются поддеревьями данного корня T

Содержание

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

  • Степень узла — количество поддеревьев узла
  • Концевой узел (лист) — узел со степенью нуль.
  • Узел ветвления — неконцевой узел.
  • Уровень узла определяется рекурсивным образом:
  1. Уровень корня дерева T равен нулю
  2. Уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T, содержащего данный узел.
  • Дерево с отмеченной вершиной назывется корневым деревом.
    • m-й ярус узла T — множество узлов дерева, на уровне m от корня дерева.
    • частичный порядок на вершинах: u \prec v, если вершины u и v различны и вершина u лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v.
    • корневое поддерево с корнем v — подграф \{v\}\cup\{w\mid v<w\}.
  • Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
  • Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
  • Ориентированное дерево — это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Иногда, термин «ориентированное дерево» сокращают до «дерева».

[править] Двоичное дерево

Пример дерева

Термин двоичное дерево имеет несколько значений:

[править] N-арные деревья

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

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

[править] Свойства

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

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

  • Число различных деревьев которые можно построить на n нумерованных вершинах, равно nn − 2 (Теорема Кэли).
  • Производящая функция
T(z)=\sum_{n=1}^\infty T_nz^n
для числа Tn неизоморфных корневых деревьев с n вершинами удовлетворяет функциональному уравнению
T(z)=x\exp\sum_{r=1}^\infty\frac1r T(x^r).
  • Производящая функция
t(z)=\sum_{n=1}^\infty t_nz^n
для числа tn неизоморфных деревьев с n вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:
t(z)=T(z)-\frac12\left(T^2(z)-T(z^2)\right).
  • При n\to\infty верна следующая ассимптотика
t_n\sim C\alpha^n/n^{5/2}
где C и α определённые константы, C = 0,534948..., α = 2,95576....

[править] Кодирование деревьев

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

t_n\le T_n< 2^{2n}

[править] См. также

[править] Книги

  • Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
  • Оре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.
Источник — «http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)»