Граф с каким свойствами называют деревом что такое корень дерева

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

Лес — множество деревьев.

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

Связанные определения[править | править код]

Степень вершины — количество инцидентных ей ребер.

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

Узел ветвления — неконцевой узел.

Дерево с отмеченной вершиной называется корневым деревом.

Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

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

Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

Несводимым называется дерево, в котором нет вершин степени 2.

Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.

Двоичное дерево[править | править код]

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

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

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

N-арные деревья[править | править код]

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

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

Свойства[править | править код]

Подсчёт деревьев[править | править код]

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

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

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

При верна следующая асимптотика

где и определённые константы, , .

Кодирование деревьев[править | править код]

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

См. также[править | править код]

Глоссарий теории графов
Лес непересекающихся множеств
Список структур данных (деревья)

Примечания[править | править код]

↑ § 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 экз.
↑ Дискретная математика: алгоритмы. Формула Кэли (недоступная ссылка). Дата обращения 29 октября 2009. Архивировано 14 июня 2009 года.

Литература[править | править код]

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

Источник

Корневые деревья

Произвольно зафиксируем
некоторую вершину дерева
и назовем
ее корнем дерева. Само дерево в этом случае будем называть деревом
с корнем или корневым деревом.

Иногда полезно, руководствуясь
какими–либо соображениями, выделять в дереве некоторую определенную цепь , которую обычно называют
стволом дерева. Корень дерева обычно является одной из концевых
вершин ствола. Каждая концевая вершина дерева связана с ближайшей вершиной ствола единственной цепью.
Эту цепь называют ветвью дерева, выходящей из вершины в вершину . При отсутствии у дерева
ствола, ветвями дерева называют цепи, связывающие концевые вершины дерева
с его корнем.

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

На рис. 4. 38 приведены примеры дерева
с корнем ,
его ориентированного дерева и сети сборки .

Деревья графов

Пусть дерево является подграфом графа
.
Ребра графа , которые принадлежат дереву
,
называются ветвями дерева ,
а ребра, не принадлежащие дереву , –
хордами относительно дерева . Если есть суграф , то есть вершины дерева совпадают с вершинами графа , то говорят, что дерево
покрывает граф . В этом случае дерево называют остовом
или каркасом графа .

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

; .

Следовательно, существует
50 различных деревьев, покрывающих этот граф. Один из 50 остовов мультиграфа
изображен на рис. 4.39 жирными линиями.

Экстремальные графы

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

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

Поскольку полный граф покрывает различных основных деревьев, то
решение этой задачи полным перебором вариантов потребовало бы чрезвычайно
больших вычислений даже при относительно малых . Уже при таких вариантов больше миллиона.

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

Теорема 4.13. Алгоритм Краскала позволяет построить экстремальный
граф любого связного графа.

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

На первом шаге выбираем самый короткий участок искомой сети дорог, связывающей
поселки. Это дорога длиною 12 км между поселками П1 и П2. Затем добавляем
к ней дороги между П1 и П3 (13 км), П1 и П9 (14 км), П5 и П7 (15 км),
П3 и П4 (18 км). Следующее минимальное расстояние между поселками
равно 19 км. Таково расстояние между П1 и П8 и между П6 и П7. Так
как обе эти дороги не образуют цикла с уже отобранными дорогами, то
обе они добавляются в список. Следующие по длине (25 км и 26 км) дороги
между П1, П2 и П5, П6 нельзя добавлять в наш список – иначе появятся циклы: П1, П2, П3, П2 или П5, П6, П7,
П5. Восьмая и последняя дорога искомого минимального остова имеет
длину 28 км, она проходит между П5 и П8. Минимальный остов, связывающий
девять поселков, изображен на рис. 4.40. Минимальная длина дорог, связывающих поселки, равна
138 км.

Рис.4.40

Экстремальное дерево может быть построено для произвольного графа, а не
только для полного графа. Например, связи между некоторыми вершинами
могут быть нежелательными или недопустимыми.

Источник

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

Определения[править | править код]

Корневой узел — самый верхний узел дерева (узел 8 на примере).
Корень — одна из вершин, по желанию наблюдателя.

Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов (узлы 1, 4, 7, 13).

Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом (3, 6, 10, 14).

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

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

Узлы[править | править код]

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

Корневые узлы[править | править код]

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

Поддеревья[править | править код]

Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).

Упорядочивание деревьев[править | править код]

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

Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.

Представление деревьев[править | править код]

Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).

Деревья как графы[править | править код]

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

Методы обхода[править | править код]

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков, называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Общие операции[править | править код]

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

Общее применение[править | править код]

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

См. также[править | править код]

Двоичное разбиение пространства
Куча (структура данных)
Дерево (теория графов)
Дерево (теория наборов)
Древовидная структура
Префиксное дерево
Экспоненциальное дерево

Распространённые древовидные структуры

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

Самобалансирующиеся двоичные деревья поиска

АА-дерево
АВЛ-дерево
Красно-чёрное дерево
Расширяющееся дерево
Дерево со штрафами

Прочие деревья

B-дерево (2-3-дерево, B+-деревья, B*-дерево, UB-дерево)
DSW-алгоритм
Танцующее дерево
Анфилада
Смешанное дерево
k-мерное дерево
Октодерево
Квадродерево
R-дерево (структура данных)
Дерево покрытий
Дерево остатков
Сегментное дерево
Список с пропусками
T-дерево
T-пирамида
Верхнее дерево
Дерево ван Емде Боаса
Прошитое двоичное дерево
Список структур данных (деревья)

Примечания[править | править код]

Литература[править | править код]

Дональд Э. Кнут. Глава 2.3. Деревья // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2002. — Т. 1. Основные алгоритмы. — 720 с. — ISBN 5-8459-0080-8 (рус.) ISBN 0-201-89683-4 (англ.).
Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Introduction to Algorithms. — 2nd Edition. — MIT Press, McGraw-Hill, 2001. — ISBN 0-262-03293-7.
- Section 10.4: Representing rooted trees, pp.214-217.
- Chapters 12-14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253—320.

Ссылки[править | править код]

Обходы бинарных деревьев
Красно-черные деревья

Источник

Центр дерева

Центр графа может состоять из одной вершины (как, например, в графе $K_{1,q}$ ), а может включать все его вершины (полный граф). Для
дерева,
как мы увидим, имеется гораздо более узкий диапазон возможностей.

Теорема 3. Центр дерева состоит из одной вершины или из двух
смежных вершин.

Доказательство.

Допустим, что в некотором дереве имеются две
несмежные центральные вершины $c_{1}$ и $c_{2}$ . На
пути,
соединяющем эти вершины, найдем промежуточную вершину с
максимальным
эксцентриситетом, и пусть $b_{1}$ и $b_{2}$ –
вершины, соседние
с на этом пути (см. рис. 3.1).
Пусть – вершина, наиболее удаленная
от в дереве, т.е. d(a,x)=ecc(a) . Путь,
соединяющий с ,
не может проходить через обе вершины $b_{1}$
и $b_{2}$ . Допустим,
он не проходит через $b_{1}$ . Тогда единственный путь из $b_{1}$
в проходит через и $d(b_{1},x) gt d(a,x)$ . Отсюда следует, что $ecc(b_{1} ) gt ecc(a)$ , а это противоречит выбору вершины , если $b_{1} ne c_{1}$ , или тому, что $c_{1}$ –
центральная вершина, если $b_{1} =c_{1}$ .

Следовательно, любые две центральные вершины смежны, а так как в дереве
не может быть трех попарно смежных вершин, то в нем не больше двух
центральных вершин.

Рис.
3.1.

Корневые деревья

Часто в дереве особо выделяется одна вершина, играющая роль своего рода
“начала отсчета”. Дерево с выделенной вершиной называют корневым
деревом, а саму эту вершину – корнем. Из дерева с вершинами
можно, таким образом, образовать различных корневых
деревьев.

При графическом изображении корневого дерева обычно придерживаются
какого-нибудь стандарта. Один из наиболее распространенных состоит
в следующем. Возьмем на плоскости семейство параллельных прямых с равными
расстояниями между соседними прямыми. Изобразим корень точкой на одной из
этих прямых, смежные с корнем вершины – точками на соседней прямой,
вершины, находящиеся на расстоянии 2 от корня, – на следующей, и т.д.
Ребра изобразим отрезками прямых. Ясно, что вершины на каждой прямой можно
разместить так, чтобы ребра не пересекались. Пример нарисованного таким
образом корневого дерева показан на рис. 3.2 (корень обведен кружком). Чаще, впрочем, дерево рисуют корнем
вверх, а не вниз.

Рис.
3.2.

Иногда бывает полезно ребра корневого дерева ориентировать так, чтобы
в каждую вершину вел ориентированный путь из корня (для дерева
на рис. 3.2 это означает, что
каждое ребро
ориентируется снизу вверх). Такое
ориентированное корневое дерево будем называть исходящим деревом.
В исходящем дереве каждая вершина, кроме корня, является концом
единственного ребра. Если в исходящем дереве имеется ребро ,
то вершину называют отцом вершины , а вершину – сыном
вершины . Естественный и для многих
целей удобный способ задания корневого дерева состоит в указании для
каждой вершины ее отца. При этом иногда считают, что корень приходится
отцом самому себе – это равносильно добавлению петли при корне.

Если в исходящем дереве имеется ориентированный путь из
вершины в вершину , то говорят, что – предок ,
а – потомок . В частности, каждая вершина
является предком и потомком самой себя. Множество всех предков
вершины порождает ориентированный путь из корня
в . Множество всех
потомков вершины порождает исходящее дерево с корнем
в ,
оно называется ветвью
дерева в вершине .

Высотой корневого дерева
называется эксцентриситет его корня. Если
мы хотим превратить некоторое дерево в корневое и притом минимальной
высоты, то в качестве корня следует взять центральную вершину.

Каркасы

Пусть – обыкновенный граф. Его каркасом называется
остовный подграф, в котором нет циклов, а области связности совпадают
с областями связности графа . Таким образом, каркас связного
графа –
дерево, а в общем случае – лес.

У любого графа есть хотя бы один каркас. Действительно, если
в
нет циклов, то он сам является собственным каркасом. Если же циклы есть,
то можно удалить из графа любое ребро, принадлежащее какому-нибудь циклу.
Такое ребро не является перешейком, поэтому при его удалении области
связности не изменятся. Продолжая действовать таким образом, после
удаления некоторого количества ребер получим остовный подграф, в котором
циклов уже нет, а области связности – те же, что у исходного графа, то
есть этот подграф и будет каркасом. Можно даже точно сказать, сколько
ребер необходимо удалить для получения каркаса. Если в графе
вершин, ребер и компонент связности, то в
каркасе будет
тоже вершин и компонент связности. Но в любом
лесе с
вершинами и компонентами связности имеется
ровно n-k ребер.
Значит, удалено будет m-n+k ребер. Это число называется цикломатическим
числом графа и обозначается через nu (G) .

Если в графе есть циклы, то у него больше одного каркаса. Определить
точное число каркасов связного графа позволяет так называемая матричная
теорема Кирхгофа. Приведем ее без доказательства. Для графа
определим матрицу K(G) – квадратную матрицу порядка с элементами

$K_{ij} =left{begin{aligned} & -1, & text{если }(i,j)in EG, \ & 0, & text {если }(i,j)notin EG t{ и } ine j,\ & deg (i), & text {если } i=j. end{aligned} right}$

Иначе говоря, K(G) получается из матрицы смежности, если
заменить
все на , а вместо нулей на главной диагонали
поставить степени вершин.
Заметим, что матрица K(G) – вырожденная, так как сумма
элементов
каждой строки равна , то есть столбцы линейно зависимы.

Источник