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

Дерево — это связный ациклический граф.[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.

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

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

Источник

Деревья

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

Определение 1.10. Граф называется деревом, если
в нем есть одна вершина , в которую не входят ребра ; она называется корнем дерева ;
в каждую из остальных вершин входит ровно по одному ребру ;
все вершины достижимы из корня.

На рисунке 2 показан пример дерева G_1

С ориентированными деревьями связана богатая
терминология, пришедшая из двух источников: ботаники и области семейных
отношений.

Корень — это единственная вершина, в которую не входят ребра, листья — это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева — это максимальная из длин его ветвей. Глубина вершины — это длина пути из корня в эту вершину.
Для вершины v in V , подграф дерева T=(V,E) ,
включающий все достижимые из вершины и соединяющие их ребра
из , образует поддерево T_v дерева с корнем .. Высота вершины — это высота дерева T_v . Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

Дерево G1

Рис.
1.2.
Дерево G1

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

Пример 1.4. В дереве на рис. 1.2 вершина является корнем, вершины a, b, f, g, k — листья. Путь c,d,h,k — одна из ветвей дерева G_1 . Вершина является отцом (родителем) вершин e, g и , а каждая из этих вершин — ее сыном
(ребенком). Между собой вершины e, g и являются
братьями (сестрами). Глубина равна 1, а высота — 2. Высота всего дерева G_1 равна 3.

Для деревьев часто удобно использовать следующее индуктивное определение.

Определение 1.11. Определим по индукции класс графов , называемых деревьями. Одновременно для каждого из них определим выделенную вершину — корень.
Граф , с единственной вершиной и
пустым множеством ребер является деревом (входит
в ). Вершина называется корнем этого дерева.
Пусть графы с корнями принадлежат , а — новая вершина, т.е. $r_0 notin bigcup_{i=1}^k V_i$ .
Тогда классу принадлежит также следующий граф , где $V= { r_0} cup bigcup_{i=1}^k V_i$ , $E = { (r_0, r_i) | i=1, ldots , k} cup bigcup_{i=1}^k E_i$ . Корнем этого дерева является вершина .
Других графов в классе нет.

Рисунок 1.3 иллюстрирует это
определение.

Индуктивное определение ориентированных деревьев

Рис.
1.3.
Индуктивное определение ориентированных деревьев

Определения ориентированных деревьев 1.10 и 1.11
эквивалентны.

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

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

Источник