Дерево (граф)
В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.
Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:
Связанные определения
- Степень узла — количество поддеревьев узла
- Концевой узел (лист) — узел со степенью нуль.
- Узел ветвления — неконцевой узел.
- Уровень узла определяется рекурсивным образом:
- Уровень корня дерева T равен нулю
- Уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T , содержащего данный узел.
- Дерево с отмеченной вершиной назывется корневым деревом.
- m -й ярус узла T — множество узлов дерева, на уровне m от корня дерева.
- частичный порядок на вершинах:
, если вершины u и v различны и вершина u лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v .
- корневое поддерево с корнем v — подграф
- Двоичное (бинарное) дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят 3.
- Двоичное (бинарное) дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
- Двоичное дерево (структура данных) — это специальная абстрактная Структура данных используемая в программировании. На двоичном дереве основаны такие структуры данных, как Двоичное дерево поиска, Двоичная куча, Красно-чёрное дерево, АВЛ-дерево, Фибоначчиева куча и др.
N-арные деревья
N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.
- N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
- N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.
Свойства
- Дерево не имеет кратных ребер и петель.
- Любое дерево с n вершинами содержит n − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B − P = 1 , здесь B — число вершин, P — число рёбер графа.
- Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём.
- Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
- Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.
Подсчёт деревьев
- Число различных деревьев которые можно построить на n нумерованных вершинах, равно nn − 2 (Теорема Кэли).
- Производящая функция
- При
верна следующая ассимптотика
Кодирование деревьев
Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем 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 .
Деревья — Теория графов
В этом уроке мы изучим еще один вид графов — древовидные. Именно этот вид графов активно используется в программировании — он связан с алгоритмами сортировки и поиска.
Деревья
Деревья — это связные графы без циклов. Их часто применяют в математике и информатике. Вот так они выглядят:
Как видно из примера, у деревьев определенная древовидная ветвистость, откуда они и получили свое название.
Благодаря связности и отсутствию циклов у деревьев есть ряд свойств:
- В любом дереве есть ровно один путь из каждой вершины в каждую другую. Например, если есть два пути к вершине, то их можно объединить, чтобы получить цикл
- У деревьев наименьшее количество ребер, которое только может быть у графа. При этом они остаются связными. Каждое ребро дерева — режущее, значит, не лежит в цикле
- У деревьев наибольшее число ребер, которое может быть у графа без циклов. Добавление любого ребра к дереву создает ровно один цикл. Например, если добавить ребро между вершинами и , то получится цикл, включающий ребро и путь. Он гарантированно существует между и
Листья и индукция
С древовидными графами работает механизм индукции — это значит, что по каждому дереву с
вершинами можно перемещаться с шагом
Для этого нам понадобится лист в дереве — вершина, которая находится на концах каждого дерева.
Разберем следующую теорему: у каждого дерева с хотя бы двумя вершинами есть хотя бы два листа. Докажем это утверждение.
Рассмотрим любой путь максимальной длины в дереве. Поскольку у дерева две вершины и оно связное, этот путь должен существовать. У обеих конечных точек этого пути степень
в дереве. Их единственные соседи — вершины, которые располагаются перед ними на пути.
Обсудим, почему это работает именно так:
- У конечных точек не может быть других соседей на пути, поскольку это создало бы цикл, что невозможно в дереве
- У конечных точек не может быть других соседей вне пути, поскольку тогда мы могли бы использовать такого соседа для расширения пути. Только это невозможно, так как у пути уже максимальная длина
Воспользуемся индукцией, чтобы доказать, что каждое дерево с
Теория графов – деревья
Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.
Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.
дерево
Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.
Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .
Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.
Пример 1
График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.
Примечание. Каждое дерево имеет как минимум две вершины первой степени.
Пример 2
В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.
лес
Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.
пример
Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.
Охватывающие деревья
Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –
- H это дерево
- H содержит все вершины G.
Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.
пример
В приведенном выше примере G является связным графом, а H является подграфом G.
Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.
Circuit Rank
Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.
Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.
Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.
Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.
пример
Посмотрите на следующий график –
Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.
Тогда ранг цепи
G = m – (n – 1) = 7 – (5 – 1) = 3
пример
Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».
По сумме теоремы о степени вершин
n ∑ i = 1 градус (V i ) = 2 | E |
Схема ранг = | E | – (| V | – 1)
Теорема Кирхгофа
Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.
пример
Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».
Какой граф называется деревом? Что такое дерево в информатике?
Граф-дерево является очень распространенным видом графов в информатике. Они нужны для хранения какой-либо информации в нелинейной структуре в иерархическом порядке.
Граф — это структура, состоящая из множества вершин, соединенных ребрами. Все в своей жизни видели транспортные схемы (передвижение автобусов или метро). Если эти схемы смоделировать в компьютере, то остановки и станции — это будут вершины графа, а маршрут транспорта между остановками/станциями — ребра графа.
В зависимости от того, каким образом расположены вершины, какое отношение между ними и каким способом они соединяются между собой ребрами, различают различные виды графов. Граф-дерево — это всего лишь один из множества видов графов.
Граф-дерево
- в самом низу вы писали свое имя и имена ваших братьев и сестер;
- чуть выше вы записывали имена ваших родителей и соединяли ваши имена с их именами линиями;
- еще выше вы писали имена ваших дедушек и бабушек, которые являются родителями ваших родителей;
- потом записывали имена всех ваших родственников: дядей и тетей, двоюродных братьев и сестер, прадедушек и прабабушек и т. д.
Самое главное, все имена вы соединяли линиями зависимости между собой. Например, свое имя соединили с именами братьев и сестер и с именами своих родителей. Имена ваших родителей вы соединили с именами их братьев и сестер и с их родителями и т. д.
В информатике, граф-дерево выглядит точно так же, как и ваше генеалогическое дерево, только вместо имен — вершины, а вместо линий, связывающих имена — ребра.
Охарактеризовать граф-дерево в информатике можно так — это связный граф, где между двумя вершинам есть единственный связный путь. Вернемся к нашему дереву. Ваше имя будет связано линиями только с вашими родителями и вашими братьями/сестрами, с другими именами дерева у вас нет прямой связи. Например, с вашими дядями, тетями, бабушками и дедушками вы будете связаны только через ваших родителей, а не напрямую. А с вашей прабабушкой или вашим прадедушкой вы будете связаны только через родителей и бабушек с дедушками.
То есть граф-дерево в информатике следует строгой иерархии — одни элементы находятся «наверху» графа и будут называться «корнем дерева», другие элементы будут чуть ниже и будут называться «потомками», от «потомков» будут исходить «листья» — это те вершины, которые не имеют «потомков». Любой элемент верхнего уровня по отношению к нижнему уровню будет называться «предком».
Вернемся к нашему генеалогическому дереву. Бабушка с дедушкой (или прабабушка с прадедушкой, то есть в зависимости до какой глубины своих предков вы дойдете) будут корнем вашего граф-дерева (либо подкорнем, если у вас в корне будут прабабушка с прадедушкой). Ваши родители — это «потомки» вашего граф-дерева и бабушка с дедушкой для них будут «предками» вашего дерева. Вы будете «листьями» граф-дерева, потому что у вас пока нет своего потомства, как только у вас появятся дети, то вы станете «потомками» графа, а ваши дети «листьями». Ваши родители для вас будут «предками» графа.
Граф-дерево в информатике: термины
- корень — это самая «верхняя» вершина графа, с которой начинается сам граф, допустим ваши дедушка и бабушка, если вы начали вести генеалогическое дерево с них;
- ребро — это путь или линия связи между двумя графами, то есть это линия связи между именами в вашем дереве;
- потомок — это вершина графа, у которой есть родительская вершина, то есть это вы по отношению к своим родителям или ваши родители по отношению к вашим бабушке с дедушкой;
- родитель — это вершина графа, у которой есть потомственная или дочерняя вершина, то есть это ваши родители по отношению к вам или бабушка с дедушкой по отношению к вашим родителям;
- лист — это вершина, у которой нет потомственных вершин, а только родительские, то есть это вы, пока у вас нет своих детей;
- высота графа — это длина к самому дальнему листу графа, допустим в вашем дереве есть ваш дядя или тетя, тогда путь от них и до вас это будет высотой графа;
- глубина графа — это длина до корня, то есть это будет путь от дяди с тетей к корню вашего дерева (бабушка с дедушкой или прабабушка с прадедушкой);
- поиск в глубину — это стратегия обхода вершин графа, целью которой является дойти максимально «глубоко» в граф-дерево, то есть если вы возьметесь исследовать ваше генеалогическое древо и попытаетесь найти информацию о родителях ваших прадедушек и прабабушек, а может и дальше;
- поиск в ширину — это стратегия обхода вершин графа с целью нахождения кратчайшего пути, допустим вы хотите выяснить, какая родственная связь связывает вас с детьми вашего троюродного дяди.
Заключение
Граф-дерево встречается не только в информатике. Его очень часто используют и в жизни. Взгляните на иерархию в школе: во главе стоит директор, у него есть несколько заместителей, ниже заместителей находятся учителя и «листьями» графа будут ученики. И если эту зависимость попытаться нарисовать, то у вас получится граф-дерево. Во многих организациях и даже государствах система управления строится именно по таким графам.