Всякое дерево является планарным графом

Содержание

Дерево (граф)
Связанные определения
См. также
Книги
Дерево (теория графов)
Связанные определения
N-арные деревья
Свойства
Подсчёт деревьев
Кодирование деревьев

Дерево (граф)

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

Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:

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

Степень узла — количество поддеревьев узла
Концевой узел (лист) — узел со степенью нуль.
Узел ветвления — неконцевой узел.
Уровень узла определяется рекурсивным образом:

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

Дерево с отмеченной вершиной назывется корневым деревом.
- m -й ярус узла T — множество узлов дерева, на уровне m от корня дерева.
- частичный порядок на вершинах: $u \prec v$ , если вершины u и v различны и вершина u лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v .
- корневое поддерево с корнем v — подграф $\<v\ data-lazy-src=$ \cup\» width=»» height=»»/>.
Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
Ориентированное дерево — это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Иногда, термин «ориентированное дерево» сокращают до «дерева».

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

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

Двоичное (бинарное) дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят 3.
Двоичное (бинарное) дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
Двоичное дерево (структура данных) — это специальная абстрактная Структура данных используемая в программировании. На двоичном дереве основаны такие структуры данных, как Двоичное дерево поиска, Двоичная куча, Красно-чёрное дерево, АВЛ-дерево, Фибоначчиева куча и др.

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

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

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

Свойства

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

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

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

$T(z)=x\exp\sum_<r=1 data-lazy-src=$ ^\infty\frac1r T(x^r)» width=»» height=»»/>.

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

$t(z)=T(z)-\frac12\left(T^2(z)-T(z^2)\right).$

При $n\to\infty$ верна следующая ассимптотика

$t_n\sim C\alpha^n/n^<5/2 data-lazy-src=$ » width=»» height=»»/> где C и α определённые константы, C = 0,534948. , α = 2,95576. .

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

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

См. также

Книги

Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
Оре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.

Wikimedia Foundation . 2010 .

Источник

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

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

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

Формально дерево определяется как конечное множество одного или более узлов со следующими свойствами:

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

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

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

Дерево с отмеченной вершиной называется корневым деревом.
- -й ярус дерева — множество узлов дерева, на уровне от корня дерева.
- частичный порядок на вершинах: $u \prec v$ , если вершины и различны и вершина лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной .
- корневое поддерево с корнем — подграф $\<v\ data-lazy-src=$ \cup\» width=»» height=»»/>.
Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.

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

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

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

Свойства

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

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

Число различных деревьев, которые можно построить на нумерованных вершинах, равно » width=»» height=»»/> (Теорема Кэли[3] ).
Производящая функция

T_n неизоморфных корневых деревьев с вершинами удовлетворяет функциональному уравнению $T(z)=z\exp\sum_<r=1 data-lazy-src=$ ^\infty\frac1r T(z^r)» width=»» height=»»/>.

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

t_n неизоморфных деревьев с вершинами можно представить с помощью перечисляющего ряда для корневых деревьев: $t(z)=T(z)-\frac12\left(T^2(z)-T(z^2)\right).$

При $n\to\infty$ верна следующая асимптотика

$t_n\sim C\alpha^n/n^<5/2 data-lazy-src=$ » width=»» height=»»/> где $\alpha$ определённые константы, , $\alpha=2,95576.$ .

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

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

$t_n\le T_n< 2^<2n data-lazy-src=$

» width=»» height=»»/>

См. также

Примечания

↑ § 13. Определение дерева // Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.. — М .: Наука, Физматлит, 1990. — С. 53. — 384 с. — 22 000 экз. — ISBN 5-02-013992-0
↑Альфс Берзтисс. Глава 3. Теория графов. 3.6. Деревья // Структуры данных = A. T. Berztiss. Data structures. Theory and practice. — М .: Статистика, 1974. — С. 131. — 10 500 экз.
↑Дискретная математика: алгоритмы. Формула Кэли

Литература

Дональд Кнут. Искусство программирования, том = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд. — М .: Вильямс, 2006. — Т. 1. Основные алгоритмы. — 720 с. — ISBN 0-201-89683-4
Оре О. Теория графов. — 2-е изд. — М .: Наука, 1980. — 336 с.

Дерево (структура данных)
Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура
Двоичные деревья	Двоичное дерево · T-дерево
Самобалансирующиеся двоичные деревья	АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи
B-деревья	B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево
Префиксные деревья	Суффиксное дерево · Radix tree · Ternary search tree
Двоичное разбиение пространства	k-мерное дерево · VP-дерево
Недвоичные деревья	Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево
Разбиение пространства	R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков
Другие деревья	Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree
Алгоритмы	Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева

Источник