Определение и свойства деревьев.
Деревом называется произвольный связный граф без циклов. Деревья обладают следующими свойствами:
любые две вершины соединены единственной простои цепью
количество ребер на единицу меньше количества вершин
при удалении любого ребра дерево становится не связным графом
при добавлении к дереву любого ребра в дереве появляется ровно один простой цикл.
Фактически дерево можно получить из любого связного графа
Утверждение: любой связный граф содержит остовный подграф который является деревом. Этот подграф называется остовыным деревом.
Специальные виды деревьев
1 Корневые деревья
Определение: Корневое дерево — ориентированное дерево, которое удовлетворяет условиям:
a) Имеется ровно один узел в который не входит не одно
В каждый узел кроме корня входит ровно одно ребро
Из корня имеется путь к любому ребру.
Если имеется путь от вершины vl к вершине v2, тогда вершина vl предок вершины v2, а вершина v2 потомок вершины vl.
Вершина которая не имеет потомков называется концевой вершиной или листом. Не концевую вершину называют внутренней. Если V1 и V2 дуга корневого дерева, то V1— отец, a V2— сын
Глубина дерева — длина пути из корня. Узлы находящиеся на одной глубине называются ярусами дерева.
Для задания корневого дерева можно использовать те же способы, что и для любого графа. На практике для представления деревьев используется канонический способ: для каждого узла хранится указатель на отца.
2 Бинарные деревья
Определение: Бинарное дерево — корневое дерево у каждой вершины которого не более двух сыновей.
В таком дереве любой произвольный узел имеет левого и правого сына. Поддерево корнем которого является левый сын называется левым поддеревом. Поддерево корнем которого является правый сын называется правым поддеревом.
Имеется два способа представления бинарных деревьев:
1. Представление в виде двух массивов: первый массив- левые сыновья, второй — правые.
2. Представление в виде списковой структуры tree_ ptr Tree_mode — запись имеющая структуру:
Element- тип узла; Left: tree_ ptr; Right: tree_ ptr;
3 Полные бинарные деревья
Определение: Полное бинарное дерево — бинарное дерево для которого выполняются условия:
a) Заполнение дерева осуществляется от корня к листьям по уровням.
b) Заполнение уровней осуществляется слева направо.
Полные бинарные деревья представляются в виде одномерного массива: первый элемент массива — корень дерева. Для любого i-того узла элемент с индексом (2i) — левый сын, элемент с индексом (2i+l)- правый сын. Отец узла j — (j/2).
4 Бинарные поисковые деревья
Определение: Бинарное поисковое дерево — дерево поиска,
Все ключи в левом поддереве меньше ключа узла V
В правом поддереве все ключи больше, чем ключ V
В дереве нет одинаковых ключей.
5 Сбалансированные деревья
Определение: Дерево называется идеально сбалансированным, если оно является бинарным поисковым деревом и число вершин его левых и правых поддеревьев отличается не более, чем на единицу.
Определение: Дерево называется сбалансированным, если оно бинарное поисковое и высоты двух поддеревьев в каждой из вершин отличаются не более, чем на единицу.
6 Способы обхода узлов в бинарных деревьях
Большинство алгоритмов при работе с деревьями посещают каждый узел в некотором порядке.
Существует три наиболее распространенных способа обхода деревьев:
1. Прямой порядок: корень посещается раньше, чем поддеревья
Порядок обхода: корень — левое поддерево — правое поддерево.
Процедура организуется рекурсивно.
2. Обратный порядок (снизу вверх): корень посещается после поддеревьев.
Порядок обхода: левое поддерево — правое поддерево- корень.
3. Внутренний порядок (слева направо )
Порядок обхода: левое поддерево – корень — правое поддерево.
7 Представление множеств с помощью деревьев
Базовыми операциями над множествами являются:
определение принадлежности элемента множества.
объединение не пересекающихся множеств.
Каждое множество будем представлять в виде корневого дерева. Корень дерева можно использовать для хранения имени множества. Дерево будем представлять в каноническом виде.
Чтобы определить, к какому множеству принадлежит некоторый элемент — находим этот элемент и определяем корень множества, к которому он принадлежит. Этот корень — есть имя искомого множества.
Объединение непересекающихся множеств можем реализовать тремя способами:
Источник
Теория графов
Следующая теорема устанавливает, что два из четырех свойств – связность, ацикличность, древовидность и субцикличность – характеризуют граф как дерево.
- Для
– графа следующие утверждения эквивалентны: - – дерево;
- Любые две несовпадающие вершины графа соединяет единственная простая цепь;
- – связный граф, и любое ребро есть мост;
- – связный граф и древовидный;
- – ациклический граф (лес) и древовидный;
- – ациклический граф (лес) и субцикличекий;
- – связный, субциклический и неполный, ;
- – древовидный и субциклический, исключая и ;
– графа 
следующие утверждения эквивалентны: 
– дерево;
соединяет единственная простая цепь;
– связный граф, и любое ребро есть мост;
– связный граф и древовидный;
– ациклический граф (лес) и древовидный;
– ациклический граф (лес) и субцикличекий;
– связный, субциклический и неполный, 
;
– древовидный и субциклический, исключая 
и 
;- (1->2): Если
-
Ориентированные деревья
- Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
- существует единственный узел, в который не входит ни один другой узел. Он называется корнем ордерева;
- во все остальные узлы входит только по одному узлу;
- каждый узел достижим из корня.
- Ордерево обладает следующими свойствами:
- Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние отт корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.
– дерево, то любые две его несовпадающие вершины соединяет единственная простая цепь. От противного. Пусть существуют две цепи 
(см. рис.). 
Тогда 
— простой цикл. (2->3): Если любые две несовпадающие вершины графа 
соединяет единственная простая цепь, то 
– связный граф, и любое ребро есть мост. Имеем: 
(число компонент связности). Далее от противного. Пусть ребро 
— не мост. Тогда в 
концы этого ребра связаны цепью. Само ребро 
в исходном графе – вторая цепь, что противоречит условию. (3->4): Если 
– связный граф, и любое ребро есть мост, то 
– связный и древовидный (
). Индукция по 
(числу вершин). Если 
, то 
(число ребер). Пусть равенство 
выполняется для всех графов 
с числом вершин меньше 
. Докажем, что оно выполняется и для 
вершин. Удалим из 
ребро 
, являющееся мостом. Получим две компоненты связности 
и 
, для которых верно равенство 
. Т.е. 
, 
. Тогда 
. (4->5): Если 
– связный и древовидный (
), то 
– ациклический граф (лес) и древовидный (
). От противного. Пусть есть цикл с 
вершинами и 
ребрами. Остальные 
вершин связаны с этим циклом ребрами, т.к. граф связный. Следовательно, 
, что противоречит условию 
. Остальное без док-ва. 1. 
; 2. если в ордереве отменить ориентацию ребер, то получится обычное дерево; 3. для каждого узла существует единственный путь, ведущий в этот узел из корня; 4. подграф, определяемый множеством узлов, достижимых из узла 
, является ордеревом с корнем 
. Это ордерево называется поддеревом узла 
.
Источник
§ 3.8. Деревья, лес
Определение 3.8.1. Неориентированным деревом (или просто деревом) называется связный граф без циклов. Дерево есть связный граф, содержащий n вершин и n – 1 ребер, дерево есть граф, любые две вершины которого можно соединить простой цепью.
Пример. Графы, изображенные на рис 21, являются деревьями.
рис.21
Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом. Можно интерпретировать рис.21 как лес, состоящий из трех деревьев.
Определение 3.8.2. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пример. Для графа, изображенного на рис. 22 а), графы на рис. б и в являются остовными деревьями.
рис.22
Определение 3.8.3. Ориентированным деревом называют граф, в котором в каждую вершину, кроме одной, называемой корнем дерева, заходит ровно одна дуга. В корень дерева ни одна дуга не заходит. Вершины, из которых не выходит ни одна дуга, называются листьями (рис.23).
рис.23
§ 3.9. Взвешенные графы
Определение 3.9.1. Взвешенный граф – это граф дугам, которого поставлены в соответствие веса, так что дуге (xi, xj) сопоставлено некоторое число c (xi, xj) = cij, называемое длиной (или весом, или стоимостью) дуги. Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.
Определение 3.9.2. Длина пути во взвешенном графе — это сумма длин (весов) тех ребер, из которых состоит путь.
Определение 3.9.3. Расстояние между вершинами – это длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 24, равно 6.
рис.24
Примеры взвешенных графов
§ 3.10. Эйлеровы и гамильтоновы графы
Определение 3.10.1. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом.
Определение 3.10.2. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то такая цепь называется эйлеровой цепью, а граф называется полуэйлеровым графом.
Эти понятия возникли в статье Эйлера в 1735 г., в которой он решал задачу о Кенигсбергских мостах и впервые ввел понятие графа. На рис.25, а приведен план расположения семи мостов в Кенигсберге (ныне Калининграде). Задача состоит в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку С. Поскольку в конце обхода нужно вернуться в исходную часть города, и на каждом мосту нужно побывать по одному разу, этот маршрут является простым циклом, содержащим все ребра графа. В дальнейшем такие циклы и стали называть эйлеровыми, а графы, имеющие эйлеров цикл – эйлеровыми графами.
Эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги. Таким образом, эйлеровы графы – это графы, которые можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной и той же точке.
Обнаружив, что в данном графе не существует циклических обходов, проходящих по всем ребрам по одному разу, Эйлер обратился к общей задаче: при каких условиях в графе можно найти такой цикл? Ответ на этот вопрос дает следующая теорема.
Теорема Эйлера. Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени было четным.
Определение 3.10.3. Гамильтоновой цепью графа называется его простая цепь, которая проходит через каждую вершину графа точно один раз.
Определение 3.10.4. Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом.
Определение 3.10.5. Граф называется гамильтоновым, если он обладает гамильтоновым циклом.
Гамильтоновы графы применяются для моделирования многих практических задач, например, служат моделью при составлении расписания движения поездов. Основой всех таких задач служит классическая задача коммивояжера: коммивояжер должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.
Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра — связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия по соответствующей дороге, такие, как, например, расстояние между городами или время движения по дороге. Для решения задачи необходимо найти гамильтонов цикл минимального общего веса.
Теорема Кёнига. В полном конечном графе всегда существует гамильтонов путь.
Если в графе G(X) с n вершинами для любой пары вершин xi и xj справедливо неравенство
где m(хi), m(xj) – степени вершин хi и xj, то граф G(X) имеет гамильтонову цепь.
Несмотря на сходство в определении эйлерова и гамильтонового циклов, соответствующие теории для этих понятий имеют мало общего. Критерий существования для эйлеровых циклов был установлен просто, для гамильтоновых циклов никакого общего правила неизвестно. Более того, иногда даже для конкретных графов бывает трудно решить, можно ли найти такой цикл. В принципе, поскольку речь идет о конечном числе вершин, задачу можно решить перебором, однако эффективного алгоритма неизвестно.
Источник