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

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 июня 2020; проверки требует 1 правка.

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

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

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

• Дерево с отмеченной вершиной назывется корневым деревом.
• Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
• Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
• Ориентированное дерево — это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Иногда, термин «ориентированное дерево» сокращают до «дерева».

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

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

где 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 от корня, считаются исходящими из этих вершин и заходящими
в вершины, им смежные. Процесс ориентации ребер продолжается подобным
образом до тех пор, пока не будут ориентированы все ребра дерева. Поученное
в результате такой ориентации дерево с корнем называется ориентированным
деревом. В нем все ребра имеют направление от корня. Если поменять
направления всех дуг ориентированного дерева на противоположные (к
корню), то получившийся в итоге ориентированный граф называют
сетью сборки.

На рис. 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

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