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

2. Назовите элементы, составляющие следующие системы: автомобиль, молекула воды, компьютер, магазин. Солнечная система, семья, футбольная команда, армия. Обоснуйте взаимозависимость элементов этих систем.

Автомобиль: кузов, двигатель, шасси (без чего-либо из этого автомобиль не поедет)

Молекула воды: два атома водорода, атом кислорода (атомы соединены химическими связями)

Компьютер: корпус, системная плата, периферийные устройства (корпус содержит системную плату, к системной плате прикрепляются периферийные устройства)

Магазин: продавцы, товар (продавцы продают товар)

Солнечная система: планеты, спутники планет, Солнце, кометы, астероиды, … (объекты действуют друг на друга гравитацией)

Семья: родители, дети, родственники мужа, родственники жены (все связаны родственными связями)

Футбольная команда: игроки, тренеры, обслуживающий персонал (тренер тренирует игроков, персонал поддерживает игроков, технику, поля в форме) 

Армия: военные, оружие, техника (военные управляют оружием и техникой)

3. Что такое граф? Какую информацию он может нести в себе?

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

 
4. Как на графе изображаются элементы системы и отношения между ними?

Элементы системы изображаются вершинами графа, взаимоотношения — рёбрами.

5. Что значит «симметричное отношение», «несимметричное отношение»? Как они изображаются на графе? Приведите примеры.

Симметричное отношение — такое, в котором оба объекта равноценны, т.е. если А находится в отношении с Б, то и Б находится в отношении с А. На графе симметричные отношения неориентированные рёбра и или пары противоположно направленных рёбер. Пример симметричного отношения: быть супругом, быть сестрой, давать в сумме с числом 1000.

Несимметричное отношение — отношение, не являющееся симметричным, на графе обозначается направленными рёбрами. Примеры: влюблённость, отношения порядка (например, «больше»).

6. Дайте имена возможным связям между следующими объектами и изобразите связи между ними в форме графа: брат и сестра; ученик и школа; Саша и Маша; Москва и Париж; министр, директор, рабочий; Пушкин и Дантес; компьютер и процессор.

Брат — сестра (родственники), школа -> ученик (местоположение), Саша — Маша (имена, оканчивающиеся на одинаковые буквы), Москва — Париж (города разных стран), министр -> директор -> рабочий (подчинение), Пушкин <- Дантес (кто умер позже), компьютер -> процессор (входит в состав)

7. Граф с какими свойствами называют деревом? Что такое корень дерева, ветви, листья?

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

8. Какие системы называют иерархическими?

Отношения между элементами которых можно представить в виде дерева.

9. Можно ли систему файлов в MS Windows (и ей подобных) назвать иерархической? Какой смысл имеют связи между ее элементами? Что в ней является листьями, ветвями, корнем?

Можно, отношение — «находится в», листья — файлы, ветви — папки, корень — диск или «Мой компьютер»

10. Нарисуйте в виде графа систему, состоящую из четырех одноклассников, между которыми существуют следующие связи (взаимоотношения):
дружат: Саша и Маша, Саша и Даша, Маша и Гриша, Гриша и Саша.
Глядя на полученный граф, ответьте на вопрос: с кем Саша может поделиться секретом, не рискуя, что он станет известен кому-то другому?

С Дашей, Маша и Гриша дружат друг с другом и могут проболтаться.

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.

Дерево — это частный случай графа, наиболее широко применяемый в программировании.

Основные определения

Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.

Дерево — это связный граф без циклов.

Дерево — это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

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

Аналогичным образом определяется и ориентированное дерево — как орграф, в котором между любыми двумя вершинами существует не более одного пути.

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

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

Расстояние до корневой вершины V0 называется ярусом s вершины.

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

При удалении ребра единственный маршрут прерывается и граф распадается на два подграфа.

Корневое дерево — это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья (другое их название: терминальные вершины) и остальные вершины (нетерминальные); причем должны выполняться два обязательных условия:

из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;

в корень не заходит ни одна дуга; во все остальные вершины заходит ровно по одной дуге.

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

Предок вершины v — это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v — это вершина, в которую заходит дуга, исходящая из вершины v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.

Бинарное дерево — это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины.

Высота корневого дерева — это максимальное количество дуг, отделяющих листья от корня. Если дерево не взвешенное, то его высота — это просто расстояние от корня до самого удаленного листа.

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

Граф G(V,X) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

4. Граф G(V,X) связен и не содержит циклов.

5. Граф G(V,X) связный , но утрачивает это свойство после удаления любого ребра.

Итак, дерево с n вершинами имеет n-1 ребро, поэтому оно будет минимальным связным графом.

Висячие вершины, за исключением корневой, называют листьями.

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

Подграф G1 = (V1, E1) графа G = (V, E), называется остовным деревом в

графе G = (V, E), если G1 = (V1, E1) — дерево и V1 = V.