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

Привет, сегодня поговорим про дерево в теории графов , обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое дерево в теории графов , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

Лес - упорядоченное множество упорядоченных деревьев.

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

Корневое дерево — дерево, в котором выделена одна вершина (корень дерева). Формально корневое дерево определяется как конечное множество одного или более узлов со следующими свойствами:

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

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

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

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

• Дерево с отмеченной вершиной называется корневым деревом.
  • -й ярус дерева — множество узлов дерева, на уровне от корня дерева.
  • частичный порядок на вершинах: , если вершины и различны и вершина лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной .
  • корневое поддерево с корнем — подграф .
  • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.
• Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Об этом говорит сайт https://intellect.icu . Ребра графа, не входящие в остов, называютсяхордами графа относительно остова.
• Несводимым называется дерево, в котором нет вершин степени 2.
• Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.

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

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

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

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

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

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

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

Свойства

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

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

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

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

.

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

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

• При верна следующая асимптотика

где и определенные константы, , .

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

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

Вау!! 😲 Ты еще не читал? Это зря!

• Гипердерево
• Древовидная структура
• Дерево (структура данных)
• Древо решений
• Псевдолес
• Некорневое двоичное дерево

Надеюсь, эта статья про дерево в теории графов , была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое дерево в теории графов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.