Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ОСНОВЫ ТЕОРИИ ДЕРЕВЬЕВ И ИХ ИСПОЛЬЗОВАНИЕ В ЗАДАЧАХ СЕРВИСА

Основы теории деревьев

Деревьями называются связные неориентированные ациклические графы Т= (V, Е) (рис. 2.1).

Неориентированное дерево

Рис. 2.1. Неориентированное дерево

Дерево на множестве п вершин всегда содержит пг = п — 1 ребер. Дерево не имеет петель и кратных ребер. Любые две вершины дерева связаны между собой единственной простой цепью. При добавлении любого ребра к дереву образуется один цикл. При удалении хотя бы одного ребра нарушается связность и дерево распадается на компоненты. Поэтому дерево можно также определить как минимальный связный граф; здесь минимальность понимается в том смысле, что он не содержит подграфа, который состоит из всех его вершин и является связным. Единственная цепь для любой пары вершин — это достаточное условие того, чтобы граф был деревом.

Лес из двух деревьев

Рис. 2.2. Лес из двух деревьев

Лесом называется несвязный граф, компоненты которого являются деревьями. Удаление ребра е у дерева, изображенного на рис. 2.1, дает лес из двух деревьев (рис. 2.2). В общем случае после удаления к — 1 ребер получается лес из к деревьев. Ациклический граф, состоящий из к компонентов Т, ?2, Тк, называется к-дере- вом. Лес из ^-деревьев, содержащий п вершин, имеет п — к ребер. Поддеревом Т называется связный подграф дерева Т. Множество всех ребер, выходящих из вершины графа, называют звездой этой вершины. Любую вершину в неориентированном дереве можно принять в качестве корня.

Ориентированное дерево

Рис. 2.3. Ориентированное дерево

Ориентированное дерево — это дерево, в котором никакие две дуги не заходят в одну и ту же вершину (рис. 2.3); это ориентированный граф без циклов, в котором полустепень захода каждой вершины равна 1, за исключением одной, называемой корнем, с полусте- пенью захода, равной 0. Ориентированный граф G называется ориентированным, или корневым деревом, если он является деревом и имеет корень. Дерево с ориентированными ребрами называется прадеревом с корнем г, если существует путь между вершиной г и любой другой его вершиной. Корень в стандартном расположении находится вверху и связан с одним или более поддеревьев.

На произвольном графе можно выделить часть вершин и инцидентных им ребер, образующих в совокупности дерево. Если такое дерево содержит все вершины графа, т.е. является суграфом, то оно называется покрывающим (стягивающим) деревом или остовом, или каркасом (рис. 2.4). При этом множество ребер графа разбивается на два подмножества: в первое входят ребра, образующие ветви дерева, а во второе — ребра, дополняющие дерево и называемые хордами. Отметим, что покрывающее дерево имеет по крайней мере одно общее ребро с любым разрезом графа. Не всякий ориентированный граф содержит остовное дерево. Если неориентированный граф связен, то он имеет каркас. Связный граф из п вершин и т ребер содержит v — n—l ветвей и а = т — п + 1 хорд. Очевидно, что только связные графы имеют покрывающие деревья и только деревья имеют единственные покрывающие деревья. В общем случае граф может иметь несколько остовов. Если граф несвязный, то совокупность остовов к его компонентов образует покрывающий лес. Число ветвей равно v = п — к, а число хорд а = т — п + к.

Граф и его остов

Рис. 2.4. Граф и его остов

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

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

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

Бинарное дерево

Рис. 2.5. Бинарное дерево

Для оценки степени сложности дерева используют следующие характеристики:

  • 0 порядок узла — число его дочерних узлов;
  • 0 порядок дерева — наибольший порядок его узлов;
  • 0 глубина узла — число его предков плюс 1;
  • 0 глубина или высота дерева — наибольшая глубина его узлов;
  • 0 расстояние d(x, у) между вершинами х и у в дереве — число ребер в цепи, соединяющей эти вершины;
  • 0 эксцентриситет е(х) вершины х — расстояние от вершины х до наиболее удаленной от нее вершины:

Интуитивно понятно, что вершина является центральной, если е(х) относительно мало. Наименьший эксцентриситет называется радиусом r( Т) дерева Т:

а наибольший — диаметром D( Т) дерева Т:

Вершина х называется центральной вершиной дерева, если для нее е(х) = г(Т). Множество центральных вершин дерева называется его центром. Центр дерева состоит из одной или двух смежных вершин. Дерево, центр которого состоит из двух вершин, называется бицентралъным.

Понятия радиуса, центра и диаметра могут быть обобщены на неориентированные и ориентированные графы.

Известно, что число различных деревьев, которые можно построить на п данных вершинах, равно

Многие из этих деревьев изоморфны, т.е. различаются только нумерацией вершин.

Любое дерево можно рассматривать как корневое, в котором выбранная вершина v0 выступает корнем. Так как корнем может быть любая вершина, то число корневых деревьев на множестве п вершин будет

Бинарное дерево с п вершинами имеет уровней не менее где — округление влево числа X, т.е. наибольшее целое, не превосходящее X. В полном бинарном дереве с /уровнями 2У — 1 узлов.

Рассмотрим неориентированный граф с п вершинами и т < п ребрами. Ориентируем произвольным образом ребра графа и составим матрицу инцидентности для дуг S. Вычеркнем из матрицы п т строк и тем самым образуем квадратную («?х т) матрицу Sm, соответствующую вершинам vl5 v2,..., гти дугам ех, е2,..., ет. Данная матрица не будет представлять граф, так как число вершин может быть настолько малым, что у некоторых ребер не будет обеих или одной граничной точки. Такая матрица называется линейной конфигурацией. В случае, если граф является деревом и имеет п вершин и т = п — 1 ребер, то конфигурация получается вычеркиванием одной строки и имеет размер (п — 1) х (п — 1). Одно ребро в дереве не будет иметь конечной вершины. Для вычисления числа остовных деревьев графа по его линейной конфигурации можно воспользоваться следующей теоремой [7].

Теорема 2.1. Пусть G= (V, Е) — «-вершинный граф без петель, ^'я_1 — его матрица инцидентности с одной удаленной строкой, т.е. с п — 1 независимыми строками. Тогда определитель равен числу

различных остовных деревьев графа G.

Дерево, как и любой другой граф, можно описать с помощью матриц смежности и инцидентности. Матрица смежности дерева весьма разрежена и имеет п — 1 единиц и п2 — п + 1 нулей для неориентированного дерева. Матрица инцидентности дерева размером п х (п — 1) фактически близка к квадратной. Удаление одной строки матрицы инцидентности дает квадратную матрицу, также полностью характеризующую дерево.

Чтобы определить, является ли данный граф деревом, можно воспользоваться следующей теоремой [7].

Теорема 2.2. Граф с п вершинами и т = п— 1 ребрами является деревом тогда и только тогда, когда определитель квадратной матрицы S„„ полученной из матрицы инцидентности S вычеркиванием п-й строки, равен +1 или —1, во всех остальных случаях этот определитель равен нулю.

Часто при решении задач с помощью деревьев необходимо преобразовать одно дерево в другое.

Рассмотрим два остовных дерева Т] = (V, ?,) и Г2 = (V, Е2) графа G = (V,E). Оба дерева имеют п— 1 дуг. Расстояние между деревьями^ Ть Т2) определим как число дуг из Т{, которых нет в Т2. Если d( Ть Т2) = 1, то дерево Т2 можно получить из дерева Г,, удалив из Г, дугу е1 и добавив дугу е2. Такое преобразование дерева Г, в дерево Т2 называется элементарным преобразованием дерева [19].

Остов Тможет быть преобразован в остов Т путем последовательного применения нескольких элементарных преобразований, заключающихся в следующем. К остову Тдобавляется ребро е, в результате чего образуется один цикл. Затем из цикла удаляется другое ребро е', в результате чего цикл разрывается и образуется новый остов Т.

Каждой ветви ек = (v„ vj) дерева Т = (V, Е) можно приписать вес ц(у, ,уу-) = ц(2Г)>0. Определим вес дерева как сумму весов ветвей, его составляющих:

Максимальным (.минимальным) деревом графа G называется дерево с максимально (минимально) возможным весом.

От задачи нахождения минимального дерева можно перейти к задаче нахождения максимального дерева путем изменения знака веса каждой дуги.

Максимальным (.минимальным) ориентированным деревом графа G называется ориентированное дерево с максимально (минимально) возможным весом.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>