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

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

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

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.

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

Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.

дерево

Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.

Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .

Дерево с ‘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».

4.3. Деревья и лес

Свойства деревьев

Определение 4.12. Граф  
называется
деревом, если он связный и не имеет циклов.
Лесом называют граф, связные компоненты которого являются деревьями.
В частности, дерево не может иметь петель и кратных ребер.

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

Среди различных деревьев выделяют два важных частных
случая: последовательное дерево, представляющее собой простую
цепь, и звездное дерево (или куст), в котором одна из вершин
(центр) смежна со всеми остальными вершинами.

  Пусть множество  содержит  вершин. Связав эти вершины
ребрами так, чтобы отсутствовали циклы, получим некоторое дерево, покрывающее
данное множество вершин. Для двух вершин существует одно покрывающее дерево
– сами вершины и ребро, их связывающее. С увеличением
 число различных
деревьев  быстро
увеличивается:
.

  Деревья считаются существенно
различными, если они не изоморфны. Всего деревьев с четырьмя вершинами
16, из них существенно различных только 2; деревьев с шестью вершинами 1296,
а существенно различных всего 6, но уже при  насчитывается около миллиона существенно различных
деревьев.. На рис. 4.34 приведены существенно различные деревья с четырьмя и
с шестью вершинами:

Среди графов n-го порядка (с n вершинами) без кратных
ребер полный граф имеет наибольшее количество ребер, а дерево
(n-го порядка) – наименьшее. Дерево содержит минимальное количество
ребер, необходимое для того, чтобы граф был связным.

Теорема 4.9. Каждое
дерево с  вершинами
имеет в точности  ребро.

► Действительно, две
вершины связываются одним ребром, и для связи каждой добавляемой вершины с
одной из уже имеющихся вершин необходимо еще одно ребро. Если же добавить
два ребра, то есть соединить новую вершину с двумя вершинами, из  уже рассмотренных
вершин, то обязательно образуется цикл. Следовательно, для минимальной связи
 вершин необходимо
и достаточно  ребер. ◄

  Нетрудно убедиться в справедливости
следующих теорем.

Теорема 4.10. Граф
является деревом тогда и только тогда, когда каждая пара различных вершин
графа соединяется одной и только одной простой цепью.

Теорема 4.11. У
каждого дерева найдется висячая вершина.

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

Дерево на рис. 4. 35 при
удалении ребра  распадается
на лес из двух деревьев  и , а после добавления ребра  превращается в циклический
граф .

 
Рассматриваются также
деревья с ориентированными ребрами (дугами). Ориентированное дерево называется
прадеревом с корнем ,
если существует простой путь между вершиной и любой

другой его вершиной (рис. 4.36). Прадерево может иметь только один корень.

Типы вершин
дерева и его центры

Рассмотрим
дерево  с
 вершинами. Назовем его
концевые вершины вершинами типа 1. Теперь удалим все вершины типа
1 и концевые ребра. В результате получим связный граф без циклов , то есть опять дерево,
но с уже меньшим количеством вершин. Концевые вершины дерева  назовем вершинами типа
2 в дереве .
Аналогично определяются вершины типов 3, 4 и т. д. Легко видеть, что дерево
может иметь либо одну вершину максимального типа, либо две таких вершины.
Типы вершин дерева ,
изображенного на рис. 4. 37, записаны рядом
с соответствующими вершинами. Здесь же показаны последовательные этапы процедуры,
позволяющей их определить. Это дерево имеет две вершины максимального типа.
Если у дерева  удалить
одну из вершин типа 2 и ребра, ей инцидентные, то получившееся при этом
дерево будет иметь уже только одну вершину максимального типа.

Пусть вершина типа k
 есть вершина максимального
типа. Из определения типа вершин дерева следует, что эксцентриситет
единственной вершины максимального типа равен ее типу, то есть равен
k, а
эксцентриситет каждой из двух вершин максимального типа равен k-1. При этом эксцентриситет
любой вершины не максимального типа будет обязательно больше. Поэтому
центрами любого дерева являются его вершины максимального типа, следовательно,
дерево имеет либо один, либо два центра. Нетрудно убедиться, что диаметральные
цепи в деревьях проходят через его центр или через оба центра, если
их два. В первом случае длина диаметральной цепи равна
2k-2, а во втором 2k-1.

Деревья

Деревом называется связный граф,
не имеющий циклов. В графе без
циклов, таким образом, каждая компонента связности является деревом.
Такой граф называют лесом.

Из теоремы 2
“Маршруты, связность, расстояния”
следует, что во всяком дереве, в котором не
меньше двух вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами, или листьями. В действительности
легко
доказать, что в каждом дереве не меньше двух листьев, а цепь –
пример дерева, в котором точно два листа.

В следующих двух теоремах устанавливаются некоторые свойства деревьев.

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