Деревья с корнями графы

Деревья

Как уже упоминалось, есть класс графов, называемых деревьями, которые особенно интенсивно используются в вычислительных приложениях. Граф G = (V, E) называется деревом, если он связен и ацикличен(т.е. не содержит циклов).

Пусть G = (V, E) – граф с n вершинами и m ребрами. Можно сформулировать несколько необходимых и достаточных условий, при которых G является деревом:

Любая пара вершин в G соединена единственным путем.
G связен и m=n– 1.
G связен, а удаление хотя бы одного его ребра нарушает связность графа.
G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.

Эквивалентность большинства из этих условий устанавливается без особого труда. Наиболее сложно разобраться со вторым из них. В следующем примере мы докажем, что дерево с n вершинами имеет ровно n– 1 ребро. Пример 7.7. Докажите с помощью индукции по числу вершин, что для дерева T с n вершинами и m ребрами выполнено соотношение: m=n– 1. Решение. Поскольку дерево с единственной вершиной вообще не содержит ребер, то доказываемое утверждение справедливо при n = 1. Рассмотрим дерево Т с n вершинами (и m ребрами), где n> 1 и предположим, что любое дерево с kn вершинами имеет ровно k – 1 ребро. Удалим ребро из Т. По третьему свойству дерево Т после этой процедуры превратится в несвязный граф. Получится ровно две компоненты связности, ни одна из которых не имеет циклов (в противном случае исходный граф Т тоже содержал бы циклы и не мог бы быть деревом). Таким образом, полученные компоненты связности – тоже деревья. Обозначим новые деревья Т₁ и Т₂_. Пусть n₁ – количество вершин у дерева Т₁, а n₂ – y T_2.Поскольку n₁+ n₂= n, то n₁< n и n₂< n. По предположению индукции дерево Т₁ имеет n₁ – 1 ребро, а Т₂–n₂ – 1. Следовательно, исходное дерево Т насчитывало ( с учетом одного удаленного) (n₁– 1) + (n₂ – 1) + 1 = n – 1 ребро, что и требовалось доказать. Несложно доказать, что в любом связном графе найдется подграф, являющийся деревом. Подграф в G , являющийся деревом и включающий в себя все вершины G, называется остовным деревом. Остовное дерево в графе G строится просто: выбираем произвольное его ребро и последовательно добавляем другие ребра, не создавая при этом циклов, до тех пор, пока нельзя будет добавить никакого ребра, не получив при этом цикла. Благодаря примеру 7.7, мы знаем, что для построения остовного дерева в графе из n вершин необходимо выбрать ровно n – 1 ребро. Пример 7.8. Найдите два разных остовных дерева в граве, изображенном на рис. 7.12. Рисунок 7.12. Связный граф GРешение. В этом графе существует несколько остовных деревьев. Одно из них получается последовательным выбором ребер: a,b,d, и f. Другое – b,c,e и g. Названные деревья показаны на рисунке 7.13. Процесс, описанный в примере 7.8, можно приспособить для решения задачи кратчайшего соединения:Нужно построить железную сеть, связывающую некоторое число городов. Известна стоимость строительства отрезка путей между любой парой городов. Требуется найти сеть минимальной стоимости. На языке теории графов нам нужно в нагруженном графе найти остовное дерево наименьшего общего веса. Такое дерево принято называть минимальным остовным деревом или, сокращенно МОД. В отличие от задачи коммивояжера, здесь есть эффективный алгоритм, находящий действительно минимальное остовное дерево. Он похож на алгоритм Прима. Рисунок 7.13. Остовные деревья графа GАлгоритм поиска минимального остовного дерева. Пусть G= (V,E) – связной взвешенный граф. Алгоритм строит МОД в графе G, последовательно выбирая ребра наименьшего возможного веса до образования остовного дерева. МОД в памяти компьютера хранится в виде множества Т ребер. begine:=ребро графаGс наименьшим весом;T:=;E’:=E\ whileE’ ≠øbegine‘:= ребро изE‘ наименьшего веса;Т:= Т U e‘>;E‘ := множество ребер изE‘ \T>,чьё добавление к Т не ведетк образованию циклов;endendПример 7.9. В таблице 7.3 дано расстояние (в милях) между пятью деревнями A, B, C, D и E. Найдите минимальное остовное дерево. Таблица 7.3

Читайте также: Как изменяется дерево осенью

A B C D E

A — 13 3 9 9

B 13 — 11 11 13

C 3 11 — 9 7

D 9 11 9 — 2

E 9 13 7 2 —

Решение. Ребра выбираются следующим образом: первое – 1 DE веса 2; второе – AC веса 3; третье – СЕ веса 7. на этой ступени строящееся дерево выглядит так, как на рис. 7.14 Рисунок 7.14. Вид дерева после трех шагов Следующие повесу ребра – AD, AE и CD, каждое из которых имеет вес 9. Однако какое бы из них мы не добавили, получится цикл. Поэтому перечисленные ребра следует исключить из доступных для строительства. Далее идут ребра ВС и ВD веса 11. Можно присоединить любое из них, получив при этом два разных МОД: или веса 23 каждое. Зачастую, нам хотелось бы иметь деревья, представляющие собой формацию с учетом естественной иерархической структуры, такие как, например, генеалогическое дерево (рис.7.15). На нем показаны некоторые члены семьи Бернулли, каждый из которых был известным швейцарским математиком. Генеалогическое дерево можно изобразить и более сжато. Схема приведенная на рисунке 7.16, представляет собой пример так называемого дерева с корнем. Деревом с корнем называется дерево с одной выделенной вершиной. Именно эта выделенная вершина и является корнем дерева. Вершины дерева, лежащие непосредственно под корнем, называются сыновьями. С другой стороны, вершина, стоящая непосредственно перед сыном, называется ее отцом. Рисунок 7.15. Династия Бернулли Рисунок 7.16. Схема генеалогического древа Бернулли Древо с корнем можно определить рекуррентным образом. Отдельная вершина является деревом с корнем (она же служит и корнем такого дерева). Если Т₁, Т₂, …, Т_k — несвязные друг с другом деревья с корнями v₁, v₂, …, v_k, то граф, получающийся присоединением новой вершины v к каждой из вершин v₁, v₂, …, v_k отдельным ребром, является деревом Т с корнем v. Вершины v₁, …, v_k графа Т – это сыновья корня v. Мы изображаем такое дерево с корнем, расположенным наверху, и сыновьями, стоящими ниже, непосредственно под корнем (см. рис. 1.17). Каждую вершину дерева с корнем можно рассматривать как корень другого дерева, которое «растет» из него. Мы будем называть его поддеревом дерева Т. Как мы уже говорили, вершина на самом верху дерева – его корень, а вот те, которые находятся в самом низу дерева (не имеют сыновей) принято называть листьями. Остальные вершины, отличные от корня и листьев, называют внутренними. Область применения деревьев с корнями обширна. Это, например, и информатика, и биология, и менеджмент. Для приложения к информатике наиболее важны так называемые двоичные или бинарные деревья с корнем. Двоичное дерево отличает от остальных то, что каждая его вершина имеет не более двух сыновей. В двоичном дереве с корнем вниз от каждой вершины идет не более двух ребер. v₁ v₂ v_k T₁ T₂ T_k Рисунок 7.17. Таким образом, можно сказать, что каждой вершине двоичного дерева с корнем соответствует не более, чем два поддерева, которые принято называть левыми и правыми поддеревьями этой вершины. Если оказалось, что у какой то вершины дерева отсутствует потомок слева, то ее левое поддерево называют нулевым деревом (т.е. нулевое дерево – это дерево без единой вершины). Аналогично, если у вершины отсутствует правый потомок, то ее правое поддерево будет нулевым. Пример 1.10. Пусть Т – двоичное дерево с корнем, изображенное на рисунке 7.18. Рисунок 7.18. Двоичное дерево с корнем Т Определите (а) корень Т; (б) корень левого поддерева вершины В; (в) листья Т; (г) сыновей вершины С. Нарисуйте двоичное дерево с корнем Т’, полученное из Т перестановкой левых и правых поддеревьев к каждой вершины. Решение. (а) А; (б) D; (в) G, H, E, I и J; (г) F. Двоичное дерево с корнем Т’ начерчено на рис. 7.19. Рисунок 7.19. Двоичное дерево с корнем Т’

Читайте также: Дерево для инкрустаций а
Источник

2.10. Корневые деревья. Код дерева

Любое дерево можно рассматривать как корневое, если одну из вершин выбрать в качестве корня, а остальные расположить на соответствующих уровнях (ярусах). Пример корневого дерева приведен на рис. 2.26. Корень располагается на нулевом уровне. Припишем каждой вершине некоторое число, называемое весом. Веса концевых вершин равны единице, вес корня дерева равен числу всех его вершин. Вес произвольной вершины равен общему числу вершин поддерева, корнем которого она является. Возле каждой вершины дерева на рис. 2.26 указан ее вес. При таком представлении корневое дерево однозначно определяется упорядоченной последовательностью β( G ) весов его вершин, в которой на первом 40

месте стоит вес корня дерева, а затем следуют соответствующие последова- тельности для поддеревьев: β( G ) = (17, 1, 4, 1, 1, 1, 11, 4, 1, 2, 1, 6, 1, 1, 3, 1, 1).

4 1 1 1 Одна из стандартных проце-

дур выбора корня состоит в сле-

1 2 1 1

3 дующем: из дерева удаляются все

1 1 1 3 концевые вершины и ребра, затем

2 в полученном дереве снова удаля-

4 6

1 ются все вершины и ребра. В пер-

1

4 11 вом случае оставшаяся вершина

0 выбирается в качестве корня и

17 Рис. 2.26 называется центром, во втором

случае две вершины и связываю-

щее их ребро образуют бицентр.

При этом за корень принимается та вершина, из которой вырастает дерево

с меньшим числом вершин (если число вершин одинаково, то за корень принимается любая из вершин бицентра).

На рис. 2.27, а приведено дерево, в котором выделен бицентр, корневая

форма этого дерева изображена на рис. 2.27, б.

корень 3

бицентр 2

1

0

а б

Рис. 2.27 Аналитически корневое дерево можно задать также с помощью кода γ( G ), представляющего собой последовательность 0 и 1, записанную в определенном порядке. Осуществляется обход дерева по всем ребрам по одному разу в каждом из противоположных направлений. При движении по ребру от корневой вершины в последовательность g ( G ) записывается 0, а при обратном движении – 1. Обход начинается и заканчивается в корне дерева. Длина последовательности g ( G ) равна удвоенному количеству ребер дерева. Для графа, приведенного на рис. 2.27, б, g ( G ) = (01001011000110010111). 41

Читайте также: Сборник 68 валка деревьев
Источник