Граф с какими свойствами называют деревом что такое корень дерева ветви листья
Дерево (граф)
В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.
Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:
Содержание
Связанные определения
Двоичное дерево
Термин двоичное дерево имеет несколько значений:
N-арные деревья
N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.
Свойства
Подсчёт деревьев
Кодирование деревьев
См. также
Книги
Полезное
Смотреть что такое «Дерево (граф)» в других словарях:
граф — Графическое изображение электрической цепи, в котором ветви электрической цепи представлены отрезками, называемыми ветвями графа, а узлы электрической цепи — точками, называемыми узлами графа. [ГОСТ Р 52002 2003] граф Основное понятие и… … Справочник технического переводчика
Граф — [graph] основное понятие и объект изучения теории графов, математически определяется двояко. С одной стороны как совокупность двух множеств: множества элементов x Î X и множества соответствий, отношений между этими элементами t Î T. С другой… … Экономико-математический словарь
Дерево — [tree] в теории графов, связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин (элементов графа), то он содержит ровно n 1 ребро, не имеет циклов; если добавить… … Экономико-математический словарь
дерево решений — Граф схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений. Ветви дерева отображают различные события, которые могут иметь место, а узлы (вершины) состояния, в которых возникает необходимость выбора. [ОАО РАО… … Справочник технического переводчика
дерево целей — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] дерево целей В программно целевых методах планирования и управления — граф, схема, показывающая членение общих (генеральных) целей плана или… … Справочник технического переводчика
Дерево целей — [relevance tree] в программно целевых методах планирования и управления граф, схема, показывающая членение общих (генеральных) целей плана или программы на подцели, последних на подцели следующего уровня и т.д. (дерево это связный граф,… … Экономико-математический словарь
Дерево решений — [decision tree] граф, схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений. Применяется в динамическом программировании и в других областях для анализа решений, структуризации проблем. Ветви дерева отображают… … Экономико-математический словарь
Какой граф называется деревом? Что такое дерево в информатике?
Содержание:
Граф-дерево является очень распространенным видом графов в информатике. Они нужны для хранения какой-либо информации в нелинейной структуре в иерархическом порядке.
Граф — это структура, состоящая из множества вершин, соединенных ребрами. Все в своей жизни видели транспортные схемы (передвижение автобусов или метро). Если эти схемы смоделировать в компьютере, то остановки и станции — это будут вершины графа, а маршрут транспорта между остановками/станциями — ребра графа.
В зависимости от того, каким образом расположены вершины, какое отношение между ними и каким способом они соединяются между собой ребрами, различают различные виды графов. Граф-дерево — это всего лишь один из множества видов графов.
Граф-дерево
Самое главное, все имена вы соединяли линиями зависимости между собой. Например, свое имя соединили с именами братьев и сестер и с именами своих родителей. Имена ваших родителей вы соединили с именами их братьев и сестер и с их родителями и т. д.
В информатике, граф-дерево выглядит точно так же, как и ваше генеалогическое дерево, только вместо имен — вершины, а вместо линий, связывающих имена — ребра.
Охарактеризовать граф-дерево в информатике можно так — это связный граф, где между двумя вершинам есть единственный связный путь. Вернемся к нашему дереву. Ваше имя будет связано линиями только с вашими родителями и вашими братьями/сестрами, с другими именами дерева у вас нет прямой связи. Например, с вашими дядями, тетями, бабушками и дедушками вы будете связаны только через ваших родителей, а не напрямую. А с вашей прабабушкой или вашим прадедушкой вы будете связаны только через родителей и бабушек с дедушками.
То есть граф-дерево в информатике следует строгой иерархии — одни элементы находятся «наверху» графа и будут называться «корнем дерева», другие элементы будут чуть ниже и будут называться «потомками», от «потомков» будут исходить «листья» — это те вершины, которые не имеют «потомков». Любой элемент верхнего уровня по отношению к нижнему уровню будет называться «предком».
Вернемся к нашему генеалогическому дереву. Бабушка с дедушкой (или прабабушка с прадедушкой, то есть в зависимости до какой глубины своих предков вы дойдете) будут корнем вашего граф-дерева (либо подкорнем, если у вас в корне будут прабабушка с прадедушкой). Ваши родители — это «потомки» вашего граф-дерева и бабушка с дедушкой для них будут «предками» вашего дерева. Вы будете «листьями» граф-дерева, потому что у вас пока нет своего потомства, как только у вас появятся дети, то вы станете «потомками» графа, а ваши дети «листьями». Ваши родители для вас будут «предками» графа.
Дерево (структура данных)
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
Содержание
Определения
Дерево считается ориентированным, если в корень не заходит ни одно ребро.
Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья ‘растут’ вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.
Корневые узлы
Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.
Поддеревья
Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).
Упорядочивание деревьев
Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.
Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.
Представление деревьев
Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).
Деревья как графы
В теории графов дерево — связанный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения «родитель-потомок». Ациклический граф со множеством связанных компонентов или набор корневых деревьев иногда называется лесом.
Методы обхода
Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.
Граф с какими свойствами называют деревом что такое корень дерева ветви листья
Дерево — это связный ациклический граф.[1] Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.
Лес — множество деревьев.
Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.[2]
Связанные определения[править | править код]
Двоичное дерево[править | править код]
Простое бинарное дерево размера 9 и высоты 3, с корнем значения 2. Это дерево не сбалансировано и не отсортировано.
Термин двоичное дерево (применяется так же термин бинарное дерево) имеет несколько значений:
N-арные деревья[править | править код]
N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.
Свойства[править | править код]
Подсчёт деревьев[править | править код]
для числа неизоморфных корневых деревьев с вершинами удовлетворяет функциональному уравнению
.
для числа неизоморфных деревьев с вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:
Кодирование деревьев[править | править код]
См. также[править | править код]
Примечания[править | править код]
Литература[править | править код]
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными.
Определения[править | править код]
Дерево считается ориентированным, если в корень не заходит ни одно ребро.
Узлы[править | править код]
Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья «растут» вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.
Корневые узлы[править | править код]
Узел, не имеющий предков (самый верхний), называется корневым узлом. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам) (согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.
Поддеревья[править | править код]
Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).
Упорядочивание деревьев[править | править код]
Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.
Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.
Представление деревьев[править | править код]
Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).
Деревья как графы[править | править код]
В теории графов дерево — связный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения «родитель-потомок». Несвязный граф, состоящий исключительно из деревьев, называется лесом.
Методы обхода[править | править код]
Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков, называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.
Общие операции[править | править код]
Общее применение[править | править код]
См. также[править | править код]
Распространённые древовидные структуры
Самобалансирующиеся двоичные деревья поиска
Примечания[править | править код]
Литература[править | править код]
Ссылки[править | править код]
Корневые деревья
Произвольно зафиксируем
некоторую вершину дерева
и назовем
ее корнем дерева. Само дерево в этом случае будем называть деревом
с корнем или корневым деревом.
Корневые деревья естественно
ориентировать, если в этом есть необходимость, от корня. Все
ребра, инцидентные корню дерева, считаются исходящими из корня и заходящими
в вершины, смежные корню. Все ребра дерева, инцидентные вершинам, удаленным
на расстояние 1 от корня, считаются исходящими из этих вершин и заходящими
в вершины, им смежные. Процесс ориентации ребер продолжается подобным
образом до тех пор, пока не будут ориентированы все ребра дерева. Поученное
в результате такой ориентации дерево с корнем называется ориентированным
деревом. В нем все ребра имеют направление от корня. Если поменять
направления всех дуг ориентированного дерева на противоположные (к
корню), то получившийся в итоге ориентированный граф называют
сетью сборки.
Деревья графов
Следовательно, существует
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 км.
Экстремальное дерево может быть построено для произвольного графа, а не
только для полного графа. Например, связи между некоторыми вершинами
могут быть нежелательными или недопустимыми.
1 В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.
Степень узла — количество поддеревьев узла
Концевой узел (лист) — узел со степенью нуль.
Узел ветвления — неконцевой узел.
Уровень узла определяется рекурсивным образом:
Уровень корня дерева T равен нулю
Уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T, содержащего данный узел.
Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
Ориентированное дерево — это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Иногда, термин «ориентированное дерево» сокращают до «дерева».
N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.
Дерево не имеет кратных ребер и петель.
Любое дерево с n вершинами содержит n − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B − P = 1, здесь B — число вершин, P — число рёбер графа.
Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём.
Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.
Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.(гамильтонов)
Простой цикл — цикл, не проходящий дважды через одну вершину
Цикл — замкнутая цепь. Для орграфов цикл называется контуром.
Цикл (простой цикл) в орграфе — это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.
Цикломатическое число графа — число компонент связности графа плюс число рёбер минус число вершин.
Чи́сла Фибона́ччи — элементы числовой последовательности
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS)
в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (или Фибоначчи) [1].
Более формально, последовательность чисел Фибоначчи задается рекуррентным соотношением:
Иногда числа Фибоначчи рассматривают и для неположительных номеров n как двусторонне бесконечную последовательность, удовлетворяющую основному соотношению. Члены с такими номерами легко получить с помощью эквивалентной формулы «назад»: Fn = Fn + 2 − Fn + 1: