Деревья

Определение.

Неориентированным деревом называют граф, удовлетворяющий одному из условий:

· связный граф без циклов;

· связный граф из n вершин и (n-1) ребра;

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

Задача. Докажите, что все три условия описывают один и тот же объект и что из того, что граф обладает одним из этих свойств, следуют два других.

Ориентированным деревом называют связный граф, в котором в каждую вершину, кроме одной, называемой корнем дерева, заходит ровно одна дуга. В корень дерева ни одна дуга не заходит.

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

Задача. Покажите, что если ориентированному дереву сопоставить неорграф, получим неориентированное дерево.

На рис.3.6 приведен граф – ориентированное дерево. Корнем дерева является вершина 1, вершины 12, 13, 14, 7, …,19, 20 - листья. Вершины дерева разбиваются по уровням. Корень относят к нулевому уровню, связанные непосредственно с ним вершины относят к 1-му уровню и т.д. К j+1-му уровню относят вершины, непосредственно связанные с j-м уровнем.

Рис. 3.6

Деревья используются для описания структур организаций, предприятий и др. Такие структуры называются иерархическими. Примером может быть структура управления, где корень дерева - управляющий, с ним связаны непосредственно подчиненные ему руководители - вершины 1-го уровня, которым, в свою очередь непосредственно подчинены другие - вершины 2-го уровня и так вплоть до исполнителей нижнего уровня – листьев. Дерево образует структура предприятия, где корень - само предприятие, под ним - входящие в него цехи и службы, ниже - входящие в цехи участки и т.д. Принято дерево изображать именно так, как приведено на рис.3.6, корнем вверх.

3.5.2.1. Дерево решений

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

Рис. 3.6

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

Стратегии поиска по дереву решений.

Предположим, что дерево решений очень велико, поэтому поиск путём полного перебора всех возможных решений невозможен. Рассмотрим стратегии поиска, связанные с сокращённым перебором решений: метод ветвлений и метод ветвей и границ.

Метод ветвлений. Поиск начинается от корня дерева. Выбирают минимальную по стоимости исходящую дугу и по ней переходят к следующей вершине. Если эта вершина не является листом, снова переходят по минимальной исходящей дуге, пока не будет достигнут лист. Алгоритм очень просто реализуется, но очевидно, что при этом решение может быть далёким от минимального.

ПримерПример. Определим по методу ветвления путь в дереве на рис.3.6. Путь пройдет по вершинам 1,3,8,16 и равен 21.

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

Рассмотрим шаги построения по этому методу на примере дерева, приведённого на рис.3.6

На первом шаге границей является корень дерева, который заменяется вершинами, связанными с ним по исходящим дугам – вершинами 2(12), 3(3), 4(4). Здесь в скобках приведены веса, приписываемые вершинам. Среди вершин границы выбирается вершина 3, имеющая минимальный вес. Эта вершина не является листом, она удаляется из границы, а вместо неё в границу вводятся вершины 7, с весом, равным 12 (сумма весов вершины 3, равной 3, и дуги (3,7), равной 9) и 8 с весом 11.

Новая граница: 2(12), 7(12), 8(11), 4(4). На ней выбирают вершину 4, которую заменяют вершинами 9,10 и 11, что приводит к новой границе: 2(12), 7(12), 8(11), 9(11), 10(10), 11(7). Для продолжения берётся ветвь, связанная с вершиной 11. Она удаляется из границы, и вместо неё вводятся связанные с ней по исходящим дугам вершины 18, 19, 20. Результатом будет новая граница из вершин 2(12), 7(12), 8(11), 9(11), 10(10), 18(11), 19(9), 20(10). Выбирается новая ветвь с минимальным весом – вершина 19, а она есть лист. Решение найдено. Им является путь в вершине 19, вес решения равен 9.

3.5.2.2. Поиск минимального остова

Остовом графа Gназывается его частичный граф типа дерево.
Таким образом, остов выделяется из графа G удалением из него ребер до тех пор, пока он не станет графом типа дерево, включающим все вершины.

Так, на рис. 3.7 приведен граф, в котором толстыми линиями выделен один из его остовов. В графе может быть несколько различных остовов.

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

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

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

Может быть предложена такая трактовка задачи. Вершины - абоненты, связанные линиями связи, веса на ребрах - оценка потери конфиденциальной информации при ее передаче по этой линии связи. Тогда задаче выделения остова с минимальным произведением весов, входящих в остов ребер, соответствует задача определения наиболее надежной сети для передачи информации.

Рассмотрим два алгоритма решения задачи: жадный алгоритм и алгоритм Прима.

Жадный алгоритм.

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

Алгоритм прост для понимания и обеспечивает получение минимального решения. Однако сложность его состоит в том, что в нем неявно присутствует процедура проверки на появления циклов, которая связана с перебором по всему графу, так же как и поиск очередного ребра.

Поиск по этому алгоритму в графе на рис.3.7 приведет к решению, которое представим в виде последовательности просмотренных ребер: (1,4), (3,5), (1,2), [(2,4)], (2,3), (5,7), [(2,5)], [(4,5)], [(4,7)], (4,8), [(5,8)], [(7,8)], (3,6). В квадратные скобки заключены те ребра, которые не включены в остов из-за появления циклов.

Алгоритм Прима.

Пункт 11. Включим любую вершину в остов.

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

В этом алгоритме не нужно следить за образованием циклов. Алгоритм начинает работу с произвольно выбранной вершины. Кроме того, на каждом шаге просматривается только одна строка матрицы смежности.

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

Если для графа на рис 3.7 алгоритм начать с вершины 7 , то последовательность действий будет такой:

Пункт 1. Вершину 7 отнесем к остову.

Пункт 2. Оценим ребра от вершины 7 к 4, 5 и 8. Выберем ребро с минимальным весом (7,5) и вершину 5 отнесем к остову.

Пункт 2. Для вершин 5, 7 рассмотрим ребра в вершины 1, 2, 3, 6, 8, 4 и по минимальной стоимости ребра отнесем вершину 3 к остову.

Пункт 2. Из вершин 5, 7, 3 ребра идут к вершинам 1, 2, 4, 6, 8. По наименьшему из этих ребер в остов отнесем вершину 2.

Пункт 2. Для вершин 5, 7, 3,2 рассматриваем ребра в вершины 1, 4, 6, 8.

По минимальному ребру отнесем к остову вершину 1.

Пункт 2. Для вершин 5, 7, 3, 2, 1 по минимальному исходящему из них ребру выберем вершину 4.

Пункт 2. Для вершин остова 1, 2, 3, 4, 5, 7 по минимальному исходящему из них ребру выделим вершину 6.

Пункт 2. Для вершины 8 определим связывающее ее ребро с вершиной или 4, или 7, или 5.

Решение построено.

3.5.2.3. Деревья Штейнера

Пусть на двумерной плоскости расположены вершины графа, связанные ребрами. Ребро взвесим расстоянием между вершинами, связанными этим ребром. Допустим возможность вводить произвольным образом добавочные вершины, называемые точками Штейнера, и заменять ребра цепью из ребер, проходящей через точки Штейнера. Задачу выделения остова в таком расширенном графе называют задачей Штейнера, а выделенный остов – деревом Штейнера (по фамилии математика, занимающегося этой задачей).

На рис.3.8,а приведен граф из четырех вершин, для которого нужно построить остов, объединяющий все вершины. Минимальный остов выделен жирными линиями. Как видно из рис. 3.8,б, если ввести в этот граф точку Штейнера – вершину 5, то выделенный остов в этом графе будет короче.

Задача Штейнера имеет очевидную инженерную интерпретацию: вершинам сопоставляются эквипотенциальные полюса сети, например полюса, на которые должно быть подано питание. Ребрам соответствуют допустимые способы связи между полюсами. Тогда решению будет соответствовать электрическая цепь минимальной длины, объединяющая все эти вершины. Точки Штейнера - точки «разветвления» в цепи, известны в инженерной практике как «Т-цепи».

В зависимости от метрики пространства, в котором рассматривается задача, возможны следующие задачи Штейнера.

Пусть ребром связаны вершина 1 с координатами (x_1,y₁) и вершина 2 с координатами (x₂,y₂). Если расстояние между вершинами 1 и 2 (длина дуги (1,2)) определяется, как L(1,2)= , то задачаназывается евклидовой.

Если расстояние определяется как

L(1,2)=½x₁-x₂½ + ½y₁- y₂½,

то задача называется линейной.

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

Для евклидовой задачи установлено: вершины Штейнера имеют степень три и располагаются в таком месте, что углы между инцидентными ребрами равны 120°.

Если пространство линейное, то в качестве мест для расположения точек Штейнера достаточно рассмотреть только точки пересечения вертикальных и горизонтальных линий, проходящих через вершины графа. Это резко сокращает число возможных вариантов. В примере для линейного случая рис.3.8,в точка Штейнера – вершина 5.