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

В теории графов, дерево — связный неориентированный граф, не содержащий циклов.

Содержание

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

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

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

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

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

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

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

Свойства

  • Дерево не имеет кратных ребер и петель.
  • Любое дерево с n вершинами содержит n − 1 ребро. Более того конечный связный граф является деревом тогда и только тогда, когда BP = 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}

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home