Что называется деревом в графе

Какой граф называется деревом? Что такое дерево в информатике?

Содержание:

Граф-дерево является очень распространенным видом графов в информатике. Они нужны для хранения какой-либо информации в нелинейной структуре в иерархическом порядке.

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

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

Граф-дерево

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

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

Охарактеризовать граф-дерево в информатике можно так — это связный граф, где между двумя вершинам есть единственный связный путь. Вернемся к нашему дереву. Ваше имя будет связано линиями только с вашими родителями и вашими братьями/сестрами, с другими именами дерева у вас нет прямой связи. Например, с вашими дядями, тетями, бабушками и дедушками вы будете связаны только через ваших родителей, а не напрямую. А с вашей прабабушкой или вашим прадедушкой вы будете связаны только через родителей и бабушек с дедушками.

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

Вернемся к нашему генеалогическому дереву. Бабушка с дедушкой (или прабабушка с прадедушкой, то есть в зависимости до какой глубины своих предков вы дойдете) будут корнем вашего граф-дерева (либо подкорнем, если у вас в корне будут прабабушка с прадедушкой). Ваши родители — это «потомки» вашего граф-дерева и бабушка с дедушкой для них будут «предками» вашего дерева. Вы будете «листьями» граф-дерева, потому что у вас пока нет своего потомства, как только у вас появятся дети, то вы станете «потомками» графа, а ваши дети «листьями». Ваши родители для вас будут «предками» графа.

Источник

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

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

Формально дерево определяется как конечное множество 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). Каждый уровень обходится слева направо.

Источник

Сколько деревьев в графе

Графы и их остовные деревья

Рассмотрим план шести ежедневных рейсов некоторой авиакомпании между некоторыми парами из аэропортов a, b, c и d, показанный на рисунке 1. Для формализации такой и многих других ситуаций в математике используется понятие граф.

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

Иначе говоря, с математической точки зрения, на рисунке 1 мы видим граф с четырьмя вершинами a, b, c и d, шестью ребрами, из них одно ребро — петля при вершине c и пара ребер соединяет b с d. Число ребер, исходящих из данной вершины, называется ее степенью, при этом петли считаются дважды; степени вершин a, b, c и d — 1, 4, 4 и 3 соответственно.

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

Предположим, нам требуется сократить число ребер связного графа, сохранив его связность. Нетрудно видеть, что это можно сделать тогда и только тогда, когда граф содержит цикл.

Цикл — это маршрут, составленный из различных ребер, обходящий несколько вершин без повторений и возвращающийся в исходную вершину. Число ребер в цикле называется длиной цикла. Например, в нашем графе есть два цикла длины три с вершинами b, c и d, один цикл длины два с вершинами b и d, а также петля при вершине c образует цикл длины один.

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

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

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

На рисунке 2 вы видите все пять различных остовных деревьев нашего исходного графа.

Число остовных деревьев в данном графе Γ мы будем обозначать τ(Γ). Например, если Γ — это граф, рассмотренный выше, то τ(Γ) = 5.

Чтобы проверить понимание данных определений, мы советуем решить следующие два стандартных упражнения про деревья.

1. Докажите, что если дерево имеет хотя бы две вершины, то в нем найдется вершина степени 1.

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

В частности, из упражнения 2 следует, что независимо от выбора ребер число удаленных ребер в процедуре получения остовного дерева из графа, описанной выше, — одно и то же. (Для связного графа Γ это число называют его первым числом Бэтти; оно обычно обозначается β₁(Γ).)

Ребро связного графа называется мостом, если удаление этого ребра из графа делает граф несвязным; такой граф разбивается на два связных графа, называемые его островами (рис. 3).

Упражнение 3. Пусть граф Γ содержит мост между островами Δ₁ и Δ₂. Докажите, что τ(Γ) = τ(Δ₁) · τ(Δ₂).

Удаление-плюс-стягивание

Пусть ρ есть ребро в графе Γ. Обозначим через Γ\ρ граф, полученный из Γ удалением ребра ρ, и через Γ/ρ — граф, полученный из Γ стягиванием ребра ρ в точку (рис. 4).

Если ребро ρ не является петлей, тогда выполняется следующее соотношение:

которое мы будем называть удаление-плюс-стягивание.

Действительно, остовные деревья в Γ можно разделить на две категории — те, что содержат ребро ρ, и те, что его не содержат. Для деревьев из первой категории стягивание ребра ρ в точку дает остовное дерево в Γ/ρ, а деревья второй категории являются также остовными деревьями в графе Γ\ρ. Более того, оба этих соответствия взаимно однозначны. Отсюда вытекает формула (*).

Например, если Γ — это первый пример и ρ есть ребро между вершинами b и c, тогда первые два остовных дерева на рисунке 2 соответствуют дереву в Γ\ρ, а последние два соответствуют дереву в Γ/ρ.

Формулу (*) удобно записывать схематически, как показано на рисунке 4. На графе Γ ребро ρ, для которого применяется формула, перечеркнуто.

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

Из формулы удаление-плюс-стягивание можно вывести несколько других полезных соотношений. Например, если в графе Γ есть концевая вершина w (т.е. вершина степени 1), то w и единственное ребро при w можно удалить и в полученном графе Γ\w число его остовных графов не изменится, т.е.

Действительно, обозначим через ρ единственное ребро при w. Заметим, что граф Γ\ρ несвязен, поскольку вершина w не имеет ребер, и, значит, τ(Γ\ρ) = 0. С другой стороны, Γ/ρ = Γ\w, откуда и получаем наше равенство.

На схемах двусторонняя стрелка «↔» будет означать, что соответствующие графы имеют то же число остовных деревьев; например, из выведенных соотношений можно получить следующую диаграмму (рис. 5), означающую, в частности, что τ(Γ) = 2 · τ(Δ).

Равенства, описанные выше, дают алгоритм вычисления τ(Γ). Действительно, для любого ребра ρ оба графа Γ\ρ и Γ/ρ имеют меньшее число ребер. Таким образом, удаление-плюс-стягивание сводит нахождение числа остовных деревьев Γ к нахождению числа остовных деревьев более простых графов.

Деревья в веерах

Графы следующего вида (рис. 6) называются веерами; веер с n + 1 вершиной будет обозначаться Θ_n.

Применив соотношения, полученные в предыдущем разделе, мы можем составить бесконечную схему, показанную на рисунке 7. В дополнение к веерам \( Θ_n \) в схеме участвуют их вариации \( Θ^′_n \), отличающиеся от \( Θ_n \) дополнительным ребром. При возникновении петель или концевых вершин мы их тут же удаляем.

Введем обозначения \( a_n = τ(Θ_n) \) и \( a^′_n = τ(Θ^′_n) \). Из схемы легко вывести два рекуррентных соотношения:

Таким образом, в последовательности чисел \( a_1, a^′_1, a_2, a^′_2, a_3. \) каждое следующее является суммой двух предыдущих.

Напомним, что последовательность чисел Фибоначчи F_n задается тем же соотношением F_n+1 = F_n + F_n−1 с F₁ = F₂ = 1. Она начинается так:

Далее заметим, что \( Θ_1 \) — это две вершины, соединенные единственным ребром, а \( Θ^′_1 \) — это две вершины, соединенные двойным ребром. Отсюда \( a_1 = 1 = F_2 \) и \( a^′_1 = 2 = F_3 \), а значит,

Можно также вывести рекуррентное соотношение на \( a_n \) без использования \( a^′_n \):

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

Этот процесс подробно описан в книжке [4], которую мы рекомендуем читателю. Поскольку \( 0 Рис. 8

5. Пусть b_n обозначает число остовных деревьев в лестнице Λ_n с n ступеньками в последовательности графов следующего типа (рис. 9):

Воспользуйтесь разработанным методом и докажите, что последовательность b_n удовлетворяет соотношению

(Заметим, что b₁ = 1 и b₂ = 4; отсюда можно быстро посчитать первые члены последовательности:

Вам потребуются еще пара последовательностей графов \( Λ^′_n \) и \( Λ^″_n \), показанных на рисунке 10.

Продвинутое упражнение 6. Колесами называются графы Φ_n следующего типа (рис. 11):

Докажите, что последовательность c_n = τ(Φ_n) удовлетворяет такой рекуррентной формуле:

Замечание. Проще вывести соотношение

Зная, что c₁ = 1, c₂ = 5, последнее равенство позволяет получить выражение для c_n:

здесь L_n = F_n−1 + F_n+1 ; эта последовательность называется числами Люка. Как и числа Фибоначчи, числа Люка часто появляются в различных комбинаторных задачах.

Заключительные замечания

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

Пусть ρ есть ребро Γ с выбранным направлением. Заметим, что все остовные деревья Γ можно разделить на три типа: (1) те, в которых на пути из a в b ребро ρ появляется с положительной ориентацией; (2) те, в которых на пути из a в b ребро ρ появляется с отрицательной ориентацией; (3) те, в которых на пути из a в b ребро ρ не появляется. Обозначим через τ₊, τ₋ и τ₀ число деревьев в этих трех категориях. Очевидно, что τ(Γ) = τ₊ + τ₋ + τ₀.

Силу тока I_ρ вдоль ρ можно вычислить по следующей формуле:

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

Есть множество других примеров использования правил Кирхгофа в теории графов. Например, в [7] они используются в физическом доказательстве формулы Эйлера

где В, Р и Г обозначают число вершин, ребер и граней многогранника соответственно.

Формула удаление-плюс-стягивание применялась при решении так называемой задачи о квадрировании квадрата. История этой задачи и ее замечательное решение обсуждаются в книжках [6] и [2]; идея этого решения также основана на оригинальном использовании электрических цепей.

Приведенный нами вывод рекуррентных формул для чисел остовных деревьев в веерах, лестницах и колесах дается в [8]; эта задача также обсуждается в классической книжке [3].

где Π_n обозначает полный граф с n вершинами (рис. 12).

Равенство (**) называется формулой Кэли. Наиболее известным доказательством является так называемый код Прюфера — способ однозначного кодирования дерева упорядоченной последовательностью из его вершин; нескольким другим доказательствам посвящена глава 30 в [1]. В расширенной версии настоящей статьи [5] приводится доказательство, основанное на формуле удаление-плюс-стягивание.

Для числа раскрасок вершин графа выполняется аналогичная формула: удаление-минус-стягивание. А именно, пусть χ(Γ, k) обозначает число раскрасок графа Γ в k цветов, при которых концы каждого ребра покрашены в разные цвета. Тогда выполняется соотношение

Действительно, допустимые раскраски графа Γ\ρ можно разбить на две категории: (1) те, в которых концы ребра ρ покрашены в разные цвета, такие остаются допустимыми в графе Γ; (2) те, в которых концы ребра ρ покрашены в один цвет, каждой такой раскраске соответствует единственная раскраска Γ/ρ. Отсюда — формула.

Упражнение 7. Докажите что для любого графа Γ функция χ(Γ, k) является многочленом с целыми коэффициентами от k; он называется хроматическим многочленом графа Γ.

Подсказка. Воспользуйтесь индукцией по общему числу ребер и вершин графа и формулой удаление-минус-стягивание.

Источник