Подождите, пожалуйста, выполняется поиск в заданном разделе

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

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

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

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комментарии (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

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



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