Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 июня 2020 года; проверки требуют 7 правок.
Дерево — это связный ациклический граф.[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 с.
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given a positive integer N, the task is to find the count of edges of a perfect binary tree with N levels.
Examples:
Input: N = 2
Output: 2
1
/
2 3
Input: N = 3
Output: 6
1
/
2 3
/ /
4 5 6 7
Approach: It can be observed that for the values of N = 1, 2, 3, …, a series will be formed as 0, 2, 6, 14, 30, 62, … whose Nth term is 2N – 2.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int cntEdges(int n)
{
int edges = pow(2, n) - 2;
return edges;
}
int main()
{
int n = 4;
cout << cntEdges(n);
return 0;
}
Java
class GFG
{
static int cntEdges(int n)
{
int edges = (int)Math.pow(2, n) - 2;
return edges;
}
public static void main(String[] args)
{
int n = 4;
System.out.println(cntEdges(n));
}
}
Python3
def cntEdges(n) :
edges = 2 ** n - 2;
return edges;
if __name__ == "__main__" :
n = 4;
print(cntEdges(n));
C#
using System;
class GFG
{
static int cntEdges(int n)
{
int edges = (int)Math.Pow(2, n) - 2;
return edges;
}
public static void Main(String[] args)
{
int n = 4;
Console.Write(cntEdges(n));
}
}
Javascript
<script>
function cntEdges(n)
{
var edges = Math.pow(2, n) - 2;
return edges;
}
var n = 4;
document.write(cntEdges(n));
</script>
Time Complexity: O(log n)
Auxiliary Space: O(1)
Last Updated :
10 Mar, 2022
Like Article
Save Article
С древовидными графами работает механизм индукции — это значит, что по каждому дереву с
вершинами можно перемещаться с шагом
ребро.
Для этого нам понадобится лист в дереве — вершина, которая находится на концах каждого дерева.
Разберем следующую теорему: у каждого дерева с хотя бы двумя вершинами есть хотя бы два листа. Докажем это утверждение.
Рассмотрим любой путь максимальной длины в дереве. Поскольку у дерева две вершины и оно связное, этот путь должен существовать. У обеих конечных точек этого пути степень
в дереве. Их единственные соседи — вершины, которые располагаются перед ними на пути.
Обсудим, почему это работает именно так:
-
У конечных точек не может быть других соседей на пути, поскольку это создало бы цикл, что невозможно в дереве
-
У конечных точек не может быть других соседей вне пути, поскольку тогда мы могли бы использовать такого соседа для расширения пути. Только это невозможно, так как у пути уже максимальная длина
Воспользуемся индукцией, чтобы доказать, что каждое дерево с
вершинами имеет
ребро.
Предположим, что все деревья на
вершинах содержат
ребро. Пусть
— дерево на
вершинах. У
есть лист
. У графа
вершин. При этом он является деревом, потому что удаление вершины не может создать цикл, а удаление листа не может разорвать граф.
По гипотезе индукции
имеет
ребер. Чтобы получить
из
было удалено одно ребро, у
должно быть
ребер. Таким образом, результат индукции верен. Такую же технику можно использовать в доказательствах с участием других деревьев.
Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.
Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.
дерево
Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.
Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .
Дерево с ‘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 |
6 × 3 = 2 | E |
| E | = 9
Схема ранг = | E | – (| V | – 1)
= 9 – (6 – 1) = 4
Теорема Кирхгофа
Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.
пример
Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».
Дерево
– связный граф без циклов. Лес
– произвольный граф без циклов.
Очевидно, связные
компоненты леса являются деревьями.
Необходимые и достаточные условия для
графа “быть деревом” даёт следующая
теорема.
Теорема. Связный
граф является деревом в том и только
том случае, если количества его вершин
и рёбер связаны соотношением
Отметим ещё два
свойства деревьев: 1) для любых вершин
и
дерева существует единственный
путь из
в
2) в любом дереве есть висячая вершина
(если дерево имеет хотя бы одно ребро,
то у него не менее двух висячих вершин).
Упражнение 3.12.
Найти количество неизоморфных графов
с 3 вершинами.
Решение.
Если граф с 3 вершинами не имеет ни
одного ребра, то он изоморфен
Рассматривая далее случаи графов с 1,
2, 3 рёбрами, мы получим все неизоморфные
графы с 3 вершинами – см. рис. 3.16. Их всего
4.
Упражнение 3.13.
Найти все
(с точностью до изоморфизма) связные
графы с 4 вершинами.
Р
ешение.
Пусть
– граф с 4 вершинами. Понятно, что если
рёбер два или меньше, то
несвязен. Следовательно, возможное
количество рёбер – это 3, 4, 5, 6. Граф с 6
рёбрами – полный, он изоморфен графу
Несложный перебор оставшихся вариантов
показывает, что графов, удовлетворяющих
требуемым условиям, ровно 6. Они изображены
на рис. 3.17.
Упражнение 3.14.
Найти все (с точностью до изоморфизма)
деревья с 5 вершинами.
Решение.
Пусть
– дерево с 5 вершинами. Понятно, что
возможны ровно 3 следующих случая: а)
все степени вершин не превосходят 2; б)
есть вершина степени 3; в) есть вершина
степени 4. В каждом из этих случаев
имеется по одному дереву – см. рисунок
3.18.
Существуют способы
компактной записи (кодирования)
деревьев. Из них мы рассмотрим два:
двоичное
(или
бинарное)
кодирование
(т.е. составление кода из 0 и 1) и кодирование
Прюфера (код
из натуральных чисел).
П
ри
бинарном кодировании каждому дереву
приписывается последовательность из
0 и 1 длины
где
– количество рёбер дерева. В этой
последовательности ровно
единиц и столько же нулей. Для составления
кода представим себе, что граф представляет
собой реку, по берегу которой мы совершаем
её обход так, чтобы река оставалась всё
время с одной стороны, для определённости
будем считать, что слева. При проходе
по ребру в первый раз в код записывается
0, а второй раз (по противоположному
берегу) – пишется 1. На рисунке 3.19 показано
на примере, как осуществляется бинарное
кодирование.
Двоичное кодирование
дерева неоднозначно.
Оно зависит от выбора начала обхода,
направления обхода, а также изображения
дерева на плоскости. Далее, не всякая
последовательность из
единиц и
нулей является бинарным кодом какого-нибудь
дерева. Необходимое и достаточное
условие существования дерева для данной
двоичной последовательности даёт
следующее утверждение.
Теорема.
Пусть
– последовательность, в которой
нулей и
единиц. Она является бинарным кодом
некоторого дерева в том и только том
случае, если в любом её начальном отрезке
количество нулей не меньше количества
единиц.
Например,
последовательность 0011011100011 не является
кодом никакого дерева (так как содержит
начальный отрезок 00110111), а последовательность
00011010011011 является кодом дерева.
Декодирование
(т.е. построение дерева по коду) можно
осуществить, копируя процесс кодирования,
т.е. восстанавливая “реку”, обход
которой был совершён.
Упражнение 3.15.
Построить дерево по его двоичному коду
00011010011011.
Решение
показано на рисунке 3.20.
Для построения
кода Прюфера вначале следует занумеровать
вершины дерева натуральными числами
(произвольным образом). Далее поступаем
так. Берём висячую вершину с наименьшим
номером. Пусть это будет вершина с
номером
Она инцидентна единственной вершине,
которая имеет номер, скажем,
Тогда записываем
в код и удаляем вершину
с ребром
после чего возвращаемся к началу
алгоритма. Это делается до тех пор, пока
не останется одно ребро. Длина кода
получается равной
где
– количество вершин дерева.
Упражнение 3.16.
Построить код Прюфера дерева, изображённого
на рисунке 3.21.
Р
ешение.
Применим описанный выше алгоритм (см.
рисунок 3. 22):
-
висячая вершина
с наименьшим номером – 2; пишем 1, удаляем
вершину 2 и ребро (1,2); -
висячая вершина
– 1; пишем 3, удаляем вершину 1 и ребро
(1,3); -
висячая вершина
– 5; пишем 4, удаляем вершину 5 и ребро
(4,5); -
висячая вершина
– 4; пишем 3, удаляем вершину 4 и ребро
(4,3).
Получится код
1343.
Декодирование
кода Прюфера осуществляется следующим
образом. Пусть дан код
где
Нарисуем на плоскости
точек, занумерованных числами
пока не соединённые друг с другом
рёбрами. Далее рисуем рёбра одно за
другим согласно следующему правилу:
-
находим
– наименьшее число из множества
которого нет в последовательности
соединяем ребром вершины
и
-
находим
– наименьшее число из множества
не встречающееся в последовательности
соединяем ребром вершины
и
-
находим
– наименьшее число из множества
не встречающееся в последовательности
соединяем ребром вершины
и
. . . . . . . . . .
. .
находим
– наименьшее число из множества
не встречающееся в последовательности
соединяем ребром вершины
и
в последовательности
отсутствуют ровно 2 числа из множества
обозначим их
и
соединим соответствующие вершины.
Упражнение 3.17.
Построить дерево по коду 1353.
Решение.
Применим описанный выше алгоритм.
-
Так как длина кода
равна 4, то дерево будет иметь 6 вершин.
Нарисуем на плоскости точки 1,2,3,4,5,6. -
Наименьшее число
– это 2. Пишем его под 1:
-
Наименьшее число
– это 1. Пишем его под 3:
-
Наименьшее число
– это 4. Пишем его под 5:
-
Н
аименьшее
число
– это 5. Пишем его под 3:
-
Отсутствуют в
последовательности 2145 числа 3 и 6.
Таким образом, в
графе будут следующие рёбра: (1,2), (3,1),
(5,4), (3,5), (3,6). Искомое дерево изображено
на рисунке 3.23.
Замечание.
В отличие от бинарного кода код Прюфера
определяется деревом однозначно,
если зафиксирована нумерация вершин
дерева. Назовём дерево с заданной на
нём нумерацией вершин помеченным
деревом.
Кодирование Прюфера определяет взаимно
однозначное соответствие между
помеченными деревьями и их кодами.
Следовательно, число помеченных деревьев
с
вершинами (обозначим это число
)
равно числу их кодов. Кодом является
произвольная последовательность
чисел, взятых из множества
Таким образом, мы имеем:
(5)
Формула (5) называется
формулой
Кэли.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
