Hi there! Our project relies on ads or donation to keep the site free to use. Please sending a donation . Thanks!
Подождите, пожалуйста, выполняется поиск в заданном разделе

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

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

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

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

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

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

Содержание

  • 1 Связанные определения
  • 2 Двоичное дерево
  • 3 N-арные деревья
  • 4 Свойства
  • 5 Подсчёт деревьев
  • 6 Кодирование деревьев
  • 7 См. также
  • 8 Примечания
  • 9 Литература

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

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

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

Дерево (теория графов) - портал intellect.icu

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

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

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

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

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

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

Свойства

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

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

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

Дерево (теория графов) - портал intellect.icu

для числа Дерево (теория графов) - портал intellect.icu неизоморфных корневых деревьев с Дерево (теория графов) - портал intellect.icu вершинами удовлетворяет функциональному уравнению

Дерево (теория графов) - портал intellect.icu.

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

Дерево (теория графов) - портал intellect.icu

для числа Дерево (теория графов) - портал intellect.icu неизоморфных деревьев с Дерево (теория графов) - портал intellect.icu вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

Дерево (теория графов) - портал intellect.icu

  • При Дерево (теория графов) - портал intellect.icu верна следующая асимптотика

Дерево (теория графов) - портал intellect.icu

где Дерево (теория графов) - портал intellect.icu и Дерево (теория графов) - портал intellect.icu определённые константы, Дерево (теория графов) - портал intellect.icu, Дерево (теория графов) - портал intellect.icu.

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

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

Дерево (теория графов) - портал intellect.icu

подробнее на сайте https://intellect.icu/derevo-teoriya-grafov-4588

Комментарии (5)

avatar
Павел 21.3.2020 21:24

Такая кодировка мне понятна, доступна. Учусь кодить. Пишу html графы деревьев.

avatar
Admin 21.3.2020 21:42

что значит html графы ?

avatar
Павел 22.3.2020 15:13

https://code.sololearn.com/WZTTXNB4wCy1/?ref=app

avatar
Павел 22.3.2020 15:15

Наверное, правильнее сказать не графы, а схемы деревьев.

avatar
Admin 22.3.2020 15:57

Да, существует большое количество библиотек для визуализации графов,
а вообще т.к понятие граф растяжимое в прямом смысле (один и тот же граф можно изобразить -
визуализировать бесконечным количесвтом образов),
существуют специальные теории и алгоритмы визуализации графов,
например можно прочитать тут
https://intellect.icu/sposoby-vizualizatsii-grafov-silovye-algoritmy-vizualizatsii-grafov-9034


еще есть даже Non-SQL для работы с графами в том числе с визуализацией
вот пример такой БД
http://console.neo4j.org/
https://neo4j.com/

Визуализация гибкого force-directed графа осуществляется с использованием метода численного интегрирования Верле библиотека JS https://github.com/d3/d3

библиотека https://www.graphviz.org/

и другие


avatar

Чтобы оставить комментарий войдите или зарегистрируйтесь



Дискретная математика. Теория множеств . Теория графов . Комбинаторика.