Арборесценция (теория графов) - Arborescence (graph theory)

В теории графов , древовидный является ориентированным графом , в котором, для вершины U называется корнем и любой другой вершина V , существует ровно один ориентированный путь из U в V . Таким образом, древовидность - это форма ориентированного графа корневого дерева , понимаемая здесь как неориентированный граф .

Эквивалентно, древовидное дерево - это направленное корневое дерево, у которого все края направлены от корня; существует ряд других эквивалентных характеристик. Каждое древообразование является направленным ациклическим графом (DAG), но не каждое древообразование является древовидным.

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

Определение

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

Дальнейшие определения

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

Также можно определить полезное понятие, перевернув все дуги древовидной структуры, то есть сделав так, чтобы все они указывали на корень, а не от него. Такие диграфы также обозначаются множеством терминов, таких как in-tree или anti-arborescence и т. Д. У. Т. Тутте различает эти два случая, используя фразы arborescence, расходящиеся от [некоторый корень], и arborescence, сходящиеся к [некоторому корню].

Количество корневых деревьев (или ветвей) с n узлами задается последовательностью:

0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, ... (последовательность A000081 в OEIS ).

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

использованная литература

внешние ссылки


Значок заглушки

Эта статья о комбинаторике незавершена . Вы можете помочь Википедии, расширив ее .