Дерево (теория графов) - Tree (graph theory)


Из Википедии, свободной энциклопедии
деревья
Дерево graph.svg
Раскрашенный дерево с 6 вершинами и 5 ребер.
вершины v
Ребра v  - 1
хроматический номер 2 , если v > 1
Таблица графиков и параметров

В математике , и, более конкретно, в теории графов , А дерево представляет собой неориентированный граф , в котором любые две вершины соединены ровно один путь . Каждый ациклический связан граф является деревом, и наоборот. Лес является объединением непересекающихся деревьев, или , что эквивалентно ациклический граф , который не обязательно связан.

Различные виды структур данных , называемых деревьев в информатике имеют базовые графики , которые являются деревья в теории графов, хотя такие структуры данных , как правило , корневые деревья . Корневое дерево может быть направлена, называется направлено корневое дерево , либо делает все его ребра направлены от корня в этом случае он называется древовидное , разветвленности , или из-дерева -или делает все ее края направлены в сторону Root- в этом случае он называется анти-древовидным или в-дерева . Сама Корневое дерево было определено некоторыми авторами как ориентированного графа.

Термин «дерево» был придуман в 1857 году британский математик Артур Кэли .

Определения

дерево

Дерево представляет собой неориентированный граф G , который удовлетворяет любой из следующих эквивалентных условий:

Если G имеет конечное число вершин, скажем , п из них, то приведенные выше утверждения эквивалентны любому из следующих условий:

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

Как и в других графов теории, нулевой порядок-граф (граф без вершин) , как правило , не рассматривается как дерево: в то время как оно бессодержательно подключен в виде графика (любые две вершины могут быть соединены с помощью пути), это не 0 -связный (или даже (-1) связные) в алгебраической топологии, в отличие от непустых дерев, и нарушает «еще одну вершины , чем кромки» отношения. Это, однако, может рассматриваться как лес , состоящий из нулевых деревьев.

Внутренняя вершина (или внутренняя вершина или ветвь вершина ) является вершиной степени , по меньшей мере 2. Аналогичным образом , внешний конец (или внешняя вершина , конечная вершина или лист ) является вершиной степени 1.

Неприводимое дерево (или последовательно уменьшаются дерево ) представляет собой дерево , в котором нет вершин степени 2.

лес

Лес представляет собой неориентированный граф, у которого все компоненты связности дерева; другими словами, граф состоит из несвязного объединения деревьев. Эквивалентный лес неориентированный ациклический граф. В особых случаях, пустой граф, одно дерево, а дискретный граф на множестве вершин (то есть, граф с этими вершинами , что не имеет ребер), являются примерами лесов. Так как для каждого дерева V - E = 1, мы можем легко подсчитать количество деревьев , которые находятся в пределах леса путем вычитания разности между общими вершинами и общих ребер. TV - TE = количество деревьев в лесу.

Polytree

Polytree (или ориентированное дерево или одиночно соединение с сетью ) представляет собой ориентированный ациклический граф (DAG) , чьи основные неориентированный граф является деревом. Другими словами, если заменить его направленные ребра с неориентированных ребер, получаем неориентированный граф , который является одновременно подключен и ациклическим.

Ориентированное дерево является ориентированным графом , который будет деревом , если направления по краям были проигнорированы, т.е. polytree. Некоторые авторы ограничивают фразу в случай , когда ребра все направленные к данной вершине, или все направлено от конкретной вершины (см древовидного ).

Внедренный дерево

Корневое дерево представляет собой дерево , в котором одна вершина была назначена корень . Края корневого дерева могут быть назначены естественную ориентацию, либо от или по направлению к корню, и в этом случае структура становится направлено корневое дерево . Когда направленное корневое дерево имеет ориентацию в стороне от корня, это называется древовидным , разветвленность , или из-дерева ; когда она имеет ориентацию в стороне корня, это называется анти-древовидным или в-дерева . Дерева порядка является частичным порядком на вершинах дерева с U < V тогда и только тогда , когда единственный путь от корня до V проходит через U . Корневое дерево , которое является подграфом некоторого графа G является нормальным деревом , если концы каждого ребра в G сравнимы в этом дереве порядка всякий раз , когда эти концы вершина дерева ( Diestel 2005 , стр. 15). Корневые деревья, часто с дополнительной структурой , такие как упорядочение соседей в каждой вершине, являются ключевой структурой данных в информатике; см структуры данных дерева .

В условиях , когда деревья , как предполагается, имеют корень, дерево без какого - либо указанного корня называется свободным деревом .

Размеченное дерево представляет собой дерево , в котором каждая вершина получает уникальную метку. Вершины раскрашенного дерева на п вершинах обычно дают метки 1, 2, ..., п . Рекурсивное дерево является меченым корневым деревом , где вершинные метки уважают порядок дерева (то есть, если у < V для двух вершин ˙U и V , то метка ц меньше , чем ярлык V ).

В корневом дереве, то родитель вершины является вершиной соединено с ней на пути к корню; каждая вершина , кроме корня имеет уникальный родитель. Ребенок из вершины V является вершиной которой v является родителем. Потомок любой вершины V является любой вершиной, либо ребенок V или (рекурсивно) потомком любого из детей против . Родственный с вершиной V является любой другой вершиной на дереве , которая имеет тот же родительскую как V . Корень является внешней вершиной , если она имеет ровно одного ребенка. Лист отличается от корня.

Высота вершины в корневом дереве является длиной самого длинного пути вниз к листу из этой вершины. Высота дерева высота корня. Глубина вершины есть длина пути к корню ( корневой путь ). Это часто необходимо при манипулировании различных самобалансирующейся деревьев, AVL деревья , в частности. Корень имеет глубину ноль, листья имеют высоту нуля, и дерево только с одной вершиной (отсюда и корень и лист) имеет глубину и высоту нуля. Обычно, пустое дерево (дерево, без вершин, если таковые разрешены) имеет глубину и высоту -1.

К-ичных дерево является корневое дерево , в котором каждая вершина имеет не более K детей. 2-ичных деревьев, часто называют бинарных деревьев , в то время как 3-ичных деревьев иногда называют тройные деревьев .

Заказанное дерево

Заказали дерево (или платан ) является корневым деревом , в котором порядок задаются для детей каждой вершины. Это называется «платан» , потому что упорядочение детей эквивалентно вложение дерева в плоскости, с корнем в вершине и детьми каждой вершины ниже этой вершины. Учитывая вложение корневого дерева в плоскости, если один фиксирует направление детей, скажем , слева направо, то вложение дает упорядочение детей. С другой стороны , учитывая упорядоченное дерево, и обычно рисунок корня в верхней части, то дочерние вершины упорядоченного дерева можно сделать левую-направо, получая , по существу , плоское уникальное вложение.

свойства

  • Каждое дерево является двудольным графом и средний график . Каждое дерево только счетное число вершин является плоским графом .
  • Каждый связный граф G допускает остов , который является деревом , которое содержит все вершины G и ребро которого являются ребрами G .
  • Граф является двудольным тогда и только тогда, когда она не содержит циклов нечетной длины. Поскольку дерево не содержит циклов на всех, она является двудольным.
  • Каждый связный граф только счетное множество вершин допускает нормальный остов ( Diestel 2005 , Prop. 8.2.4).
  • Там существуют связные графы с несчетным множеством вершин , которые не допускают нормальный остов ( Diestel 2005 , Prop. 8.5.2).
  • Каждое конечное дерево с п вершинами, с п > 1 , имеет , по меньшей мере , две концевые вершины (листья). Это минимальное количество листьев характерно графиков пути ; максимальное число, п - 1 , достигаются только звездными графиками . Число листьев, по крайней мере максимальная степень вершины.
  • Для любых трех вершин в дереве, три пути между ними есть ровно одна вершина общие.
  • Каждое дерево имеет центр , состоящий из одной вершины или двух смежных вершин. Центр является средней вершиной или две средних вершин в каждом длинном пути. Аналогичным образом , каждый п -vertex дерево имеет центроид , состоящий из одной вершины или два смежных вершин. В первом случае удаление вершины разбивает дерево в поддеревьев меньше , чем п / 2 вершин. Во втором случае удаление ребра между двумя вершинами центра тяжести разбивает дерево на две поддерева ровно п / 2 вершин.

перечисление

Помеченные деревья

Формула Кэли утверждает , что существует п п -2 деревьев на п помеченными вершинами. Классическое доказательство использует прюферовым последовательность , которые , естественно , показывают более сильный результат: число дерев с вершинами 1, 2, ..., п степеней d 1 , д 2 , ..., d п , соответственно, является мультиномиальным коэффициентом

Более общая задача заключается в подсчете связующих деревьев в неориентированного графа , который адресуется по теореме матрицы дерева . (Формула Кэли является частным случаем остовных деревьев в полном графе .) Аналогичная проблема подсчета всех поддеревьев независимо от их размера было показано, что # Р-полной в общем случае ( Jerrum (1994) ).

Немеченые дерева

Подсчет количества немеченых свободных деревьев сложнее проблема. Ни одна замкнутая формула для числа т ( п ) деревьев с п не вершинами до изоморфизма графов известно. Первые несколько значений т ( п ) являются

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301 3159, ... (последовательность A000055 в OEIS ).

Выдра (1948) доказал асимптотическую оценку

со значениями С и & alpha ; известно, приблизительно 0,534949606 ... и 2.95576528565 ... (последовательность A051491 в OEIS ), соответственно. (Здесь, е ~ г означает , что Нт п → ∞ F / г = 1 ) . Это является следствием его асимптотической оценки для числа г ( п ) немеченых корневых деревьев с п вершинами:

с D вокруг 0.43992401257 ... и той же & alpha ;, как указано выше (см Кнут (1997) , гл. 2.3.4.4 и Flajolet & Седжвик (2009) , глава VII.5, стр. 475).

Первые несколько значений г ( п ) являются

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, ...

Виды деревьев

  • Путь графа (или линейный граф ) состоит из п вершин , расположенных в линию, так что вершины я и я + 1 соединены ребром для я = 1, ..., п -1.
  • Звездное дерево состоит из центральной вершины называется корнем и несколько путей графов , прикрепленных к нему. Более формально, дерево является звездообразным , если она имеет ровно одну вершины степени больше 2.
  • Дерево звезды представляет собой дерево , которое состоит из одной внутренней вершины (и п -1 листьев). Другими словами, звезда дерево порядка п дерево порядка п с таким количеством листьев , как это возможно.
  • Гусеница дерево представляет собой дерево , в котором все вершины находятся в пределах расстояния 1 центрального пути подграфа.
  • Омары дерево представляет собой дерево , в котором все вершины находятся в пределах расстояния 2 центрального пути подграфа.
  • Регулярное дерево степени д есть бесконечное дерево с д ребер в каждой вершине. Они возникают как графы Кэлей из свободных групп , и в теории Титс .

Смотрите также

Заметки

Рекомендации

дальнейшее чтение