Деревья как частный вид графов

Размещено на http://www.allbest.ru

Введение

Целью моей курсовой работы является описание частного вида графов -- деревья.

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

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

мультиграф двоичный множественный

1. Понятия теории графов

1.1 Понятие граф

Граф G - пара (V, X), где V конечное непустое множество, содержащее p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V.

Каждую пару X={u,v} вершин в Х называют ребром графа G и говорят, что Х соединяет u и v. Мы будем писать:

X=uv

и говорить, что u и v - смежные вершины. Вершина u и ребро Х инцидентны, так же как v и Х. Если два различных ребра X и Y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (p;q)- графом. Граф (1,0)- называется тривиальным.

Если элементом множества V может быть пара одинаковых элементов u, то такой элемент множества V называется петлёй.

Типы графов:

Мультиграф, в нём не допускаются петли, но пары вершин могут соединяться более чем одним ребром, эти рёбра называются кратными (рис. 1).

Рис. 1

Псевдограф, в нём допускаются петли и кратные рёбра (рис. 2).

Рис. 2

Ориентированный граф, или орграф, состоит из конечного непустого множества V вершин и заданного набора Х упорядоченных пар различных вершин. Элементы из Х называются ориентированными рёбрами, или дугами. Нет петель и кратных дуг (рис. 3).

Рис. 3

Рис. 4

Направленный граф - это орграф, не имеющий симметричных пар ориентированных рёбер (рис. 4).

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

Степенью вершины vi в графе G называется число рёбер, инцидентных vi ,обозначается di. Для орграфа вводятся понятия степени входа и выхода. Степенью выхода вершины v называется количество рёбер, для которых v является начальной вершиной, обозначается outdeg(v). Степенью входа вершины v называется количество рёбер, для которых v является конечной вершиной, обозначается indeg(v). Если indeg(v)=0, то вершина v называется источником. Если outdeg(v)=0, то вершина v называется стоком.

Способы описания графов.

Теоретико-множественное представление графов.

Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на рис. 5 и рис. 6:

G4 = (Х, А),

где Х = {хi}, i = 1, 2, 3, 4 - множество вершин; А = {ai}, i = 1, 2, ..., 6 - множество дуг, причем А = {(х1, х2), (х4, х2), (х2, х4 ), (х2, х3), (х3, х3), (х4 , х1)}.

Рис. 5

G5 = (X, A),

где X = {B, C, D, E, F} - множество вершин графа, A = {ai}, i = 1, 2, ..., 5 - множество дуг графа, причем a1 = (F, B), a2 = (B, E), a3 = (F, D), a4 = (E, C), a5 = (C, D).

Рис. 6

Задание графов соответствием.

Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.

Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).

Отображением вершины хi -- Г(хi) является множество вершин, в которые существуют дуги из вершины хi.

Так для орграфа описание заданием множества вершин и соответствия выглядит следующим образом:

G4=(X, Г),

где X = {хi}, I = 1, 2, ..., 4 - множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = { х3 }, Г(х4) = { х1, х2 } - отображения.

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

Матричное представление графов.

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.

Матрица смежности - это квадратная матрица размерностью n x n, (где n - число вершин графа), однозначно представляющая его структуру.

A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:

aij = 1, если дуга (хi, хj),

aij = 0, если нет дуги (хi, хj).

Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n - количество вершин графа, а m - количество дуг графа. Обозначается матрица инциденций B = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m .

Каждый элемент матрицы определяется следующим образом:

bij = 1, если хi является начальной вершиной дуги aj,

bij = -1, если хi является конечной вершиной дуги aj,

bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.

Граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов i -ой строки матрицы дает полустепень исхода вершины хi, а сумма элементов i -го столбца дает полустепень захода вершины хi. По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i -ю строку матрицы. Если элемент aij=1, то элемент графа хj входит в отображение Г(хi). Например, во 2-й строке матрицы А (рис. 7) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = {х2, х5}.

Рис. 7 Орграф и его матричное представление: а - орграф; б - матрица смежности; в - матрица инциденций

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

Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные -1, заменяются на 1.

1.2 Понятия маршрут и связность

Определение маршрут. Маршрутом в графе:

G = <V,E; I>

называется последовательность вершин и рёбер вида v 0 ,e 1 ,v 1 ,e 2 , ..., v n- 1 ,e n ,v n , где v i О V, i О [0 ,n ], e i О E, ( v i- 1 ,e i ), ( v i ,e i ) О I, i О [1, n ]. Вершины v 0 , v n называются связанными данным маршрутом (или просто связанными). Вершину v 0 называют началом, а v n - концом маршрута. Если v 0 = v n , то маршрут называют замкнутым. Число n называется длиной маршрута.

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

Определение связные компоненты. Связными компонентами графа называются подграфы данного графа, вершины которых являются классами эквивалентности отношения связанности в данном графе.

Определение цикломатическое число. Цикломатическим числом графа называется число связных компонент графа плюс число рёбер минус число вершин.

Граф G/(U/,V/) называется подграфом графа G(U,V), если U/IU и V/IV. Обозначение: G/IG.

Если V/=V, то G/ называется остовным подграфом G.

Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер v0, x1, v1,…vn-1, xn, vn; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v0 и vn и его можно обозначить v0v1v2…vn (наличие рёбер подразумевается). Эта последовательность иногда называется (v0-vn) - маршрутом. Маршрут замкнут, если v0=vn, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его n вершин различны и n?3.

1.3 Цепь, простая цепь, цикл

Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Маршрут, в котором все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

Под длиной маршрута понимают количество ребер маршрута.

О: Маршрут именуют цепью в случае, когда все его ребра различны. Простой цепью маршрут можно назвать, если все его вершины, за исключением первой и последней, различны.

Так, для графа, изображенного на рис. 38.4 обозначим:

- маршрут, а не цепь, представляет собой непростую цепь, является простой цепью.

О: Цепь, которая предполагает совпадение начальной и конечной вершин, имеет название цикла, в случае, когда цепь простая, -- простого цикла.

Рис. 8

Рис. 9

В частности, всякая петля представляет собой цикл.

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

Составление теории графов связывают с постановкой и решением задачи о Кенигсбергских мостах Эйлером.

Задача. На рис. 10. обозначено расположение мостов. Необходимо пройти каждый мост единожды и вернуться в начальную часть города (суши).

Рис. 10

Рис. 11

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

О: Связный неориентированный мультиграф именуют эйлеровым при условии, что имеется цикл, который включает в себя все ребра графа (так называемый эйлеров цикл).

Эйлеров граф или цикл определяют в качестве следа пера, вычеркивающего данный граф, который не отрывается от бумаги.

Т: Неориентированный связанный мультиграф G является эйлеровым только в случае четности степени его вершин.

В соответствии с теоремой заключим, что для задачи о Кенигсбергских мостах не существует решения в силу того, что для всех вершин характерна нечетная степень. На рис. 12. обозначен Эйлеров граф.

Рис. 12

Рис. 13

О: Связной неориентированный граф G именуют гамильтоновым в случае, когда имеется простой цикл, который проходит через все вершины графа (так называемый гамильтонов цикл).

На рис. 13 представлен гамильтонов цикл.

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

2. Деревья

2.1 Определение, виды, связанные определения

Определение. Граф G называется деревом, если это связный ациклический граф, то есть если он является связным и не имеет циклов. Граф G, все компоненты, связности которого являются деревьями, называется лесом.

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

На рис.14 изображены два дерева G1, G2 и лес G3.

Рис. 14

Ориентированное (направленное) дерево -- ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.

Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:

- существует один корень дерева T

- остальные узлы (за исключением корня) распределены среди

- m ? 0 непересекающихся множеств T1,...,Tm, и каждое из множеств является деревом; деревья T1,...,Tm называются поддеревьями данного корня T.

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

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

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

Пусть G - связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G)-1 ребер.

Таким образом, любое остовное дерево графа G есть результат удаления из графа G ровно:

m(G) - (n(G) - 1) = m(G) - n(G) + 1 ребер.

Число:

v(G) = m(G) - n(G) + 1

называется цикломатическим числом связного графа G.

Одной из самых распространенных задач является задача построения остовного дерева минимальной длины графа. Для решения этой задачи применяется следующий алгоритм.

1) Выберем в графе G ребро минимальной длины. Вместе с инциндентными ему вершинами оно образует подграф G2.

2) Строим граф G3, добавляя к графу G2 новое ребро минимальной длины, выбранное среди ребер графа G, каждое из которых инциндентно какой либо вершине графа G2, и одновременно инциндентно какой - либо вершине графа G, не содержащейся в графе G2.

3) Строим графы G4, G5, …, Gn, повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.

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

Граф называется нагруженным, если на множестве его дуг задана некоторая функция, которая называется весовой функцией, и определяет длину дуги.

В нашем примере - весовая функция определяет длины дуг числами 1, 2, 3, 4, 5. v2 2 v3

Рис. 15

На четвертом шаге алгоритма получили дерево G5, которое соединяет все вершины исходного графа. Таким образом, дерево G5, будет минимальным остовным деревом графа.

Двоичное дерево.

Термин двоичное дерево (оно же бинарное дерево) имеет несколько значений:

1. Неориентированное дерево, в котором степени вершин не превосходят 3.

2. Ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.

3. древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

Для практических целей обычно используют два подвида бинарных деревьев -- двоичное дерево поиска и двоичная куча.

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

Рис. 16 Двоичное дерево поиска, в котором ключами являются латинские символы, упорядоченные по алфавиту

Связанные определения.

Степень узла -- количество исходящих дуг (или, иначе, количество поддеревьев узла).

Концевой узел (лист) -- узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева -- узел, в который ведёт только одна дуга и не исходит ни одной дуги).

Узел ветвления -- неконцевой узел.

Уровень узла -- длина пути от корня до узла. Можно определить рекурсивно:

- уровень корня дерева T равен 0;

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

Дерево с отмеченной вершиной называется корневым деревом.

N-арные деревья.

N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.

1. N-арное дерево (неориентированное) -- это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.

2. N-арное дерево (ориентированное) -- это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

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

Сформулируем основные свойства деревьев.

Свойство 1.

Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

Рис. 17

По этому дереву однозначно находится предок Максима в любом поколении по любой линии.

Свойство 2.

Всякое ребро в дереве является мостом. Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

Рис. 18

Это легко видеть на рисунке, если удалить, например, ребро А5А6 или ребро А1А3, или ребро А4А10 (оставив «вторым деревом» вершину A10).

Теорема.

Дерево с n вершинами имеет n-1 ребро.

Доказательство.

Для дерева -- изолированной вершины n=1 и ребер 0, что соответствует теореме (n--1 = 1--1 = 0). Если из графа «дерева», не являющегося изолированной вершиной, удалить одно ребро, то получается два дерева с теми же вершинами. Для получения трех деревьев нужно удалить два ребра; для получения четырех деревьев -- три ребра и т. д. Наибольшее количество деревьев из графа с n вершинами можно получить n (n изолированных вершин), чего можно достичь, удалив n--1 ребро. ч. т. д.

Задача. В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?

Решение.

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

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

Теорема 1. Пусть G(X, E) - неориентированный граф с p вершинами и q ребрами. Тогда следующие утверждения эквивалентны.

1. G есть дерево.

2. Любые две различные вершины x и y графа G соединены единственной простой цепью.

3. G - связный граф, утрачивающий это свойство при удалении любого из его ребер.

4. G - связный граф и:

p = q + 1.

5. G - ациклический граф и:

p = q + 1.

6. G - ациклический граф, причем если любые две его вершины x и y соединить ребром e, то в полученном графе будет ровно один простой цикл.

Для доказательства теоремы достаточно доказать следующую цепочку следствий: 1 > 2 > 3 > 4 > 5 > 6 > 1 , так как это означает, что из любого утверждения 1 - 6 выводится любое другое.

1 > 2 . Так как граф связен, то любые две его вершины можно соединить простой цепью. Пусть 1 и 2 - две различные простые цепи, соединяющие вершины x и y. Если цепи 1 и 2 не имеют общих вершин, за исключением вершин x и y, то есть простой цикл. Предположим, что цепи 1 и 2 имеют общие вершины, отличные от x и y. Пусть z - первая из таких вершин при движении от вершины x к вершине y и пусть 1 (x, z) и 2 (x, z) - части цепей 1 и 2, взятые от вершины x до вершины z. Тогда - простой цикл. Это противоречит тому, что граф ацикличен, и поэтому 1=2, т. е. утверждение 2 доказано.

2 > 3 . Граф G - связен, поскольку любые две его различные вершины x и y соединены простой цепью. Возьмем некоторое ребро графа e = (x, y). Согласно 2 простая цепь ={e} между вершинами x и y единственна. Если ребро e удалить, то вершины x и y будет невозможно соединить простой цепью, и полученный граф будет несвязным. Утверждение 3 доказано.

3 > 4 . По условию 3 граф связен. Соотношение:

p = q + 1

докажем по индукции. Если граф имеет две вершины и удовлетворяет 3 , то он выглядит так:

Рис. 19

В этом случае p = 2, q = 1 и соотношение:

p = q + 1

выполняется. Предположим теперь, что соотношение верно для всех графов, удовлетворяющих 3 и имеющих меньше, чем p вершин, и докажем его для графа G с p вершинами. Удалим из графа G произвольное ребро e. Тогда новый граф G? будет несвязным и будет состоять из двух связных компонент G1 и G2. По предположению индукции имеем:

p1 = q1 + 1,

p2 = q2 + 1,

где pi - число вершин компоненты Gi, qi - число ее ребер. Следовательно,

p = p1 + p2,

q = q1 + q2 + 1,

поэтому:

p = q1 + q2 + 2 = q + 1,

и свойство 4 доказано.

4 > 5 . Предположим, что граф G, удовлетворяющий 4 , имеет простой цикл длиной 1. Этот цикл содержит l вершин и l ребер. Для любой из p - l вершин, не принадлежащих циклу, существует инцидентное ей ребро, лежащее на кратчайшей цепи (т. е. цепи минимальной длины), идущей от данной вершины к некоторой вершине цикла. Все такие ребра попарно различны. Если вершины x1 и x2 инцидентны одному такому ребру e, то e = (x1, x2), и кратчайшая цепь 1 для вершины x1 проходит через вершину x2, а кратчайшая цепь 2 для вершины x2 проходит через вершину x1 (рис. 20). Это противоречит тому, что цепи 1 и 2 - кратчайшие. Общее число ребер q в графе G в этом случае не меньше, чем:

l + p - l = p,

т. е. q = p, что противоречит соотношению:

p = q + 1.

Отсюда следует, что G - ациклический граф, и утверждение 5 доказано.

Рис. 20

5 > 6 . Так как G - ациклический граф, то каждая его компонента связности Gi (i = 1, 2, …, k) является деревом. Для каждой компоненты Gi имеем в соответствии с 5:

pi = qi + 1,

откуда:

,

т. е.:

p = q + k.

С другой стороны,:

p = q + 1,

поэтому k = 1, т. е. граф G связен. Таким образом, G - дерево. Тогда (см. 2 ) любые две различные вершины x и y графа G соединены единственной простой цепью. Если добавить ребро между несмежными вершинами x и y, то оно образует с указанной цепью единственный простой цикл. Утверждение 6 доказано.

6 > 1 . По условию 6 G - ациклический граф. Если граф G не является связным, то возьмем вершины x и y из различных компонент связности графа G и соединим их ребром e. Построенный граф является, как и граф G, ациклическим. Это противоречит свойству G, поэтому G - связный граф, и свойство 1 доказано. Таким образом, доказана и теорема 1.

Определение, аналогичное дереву, можно ввести и для орграфа.

Определение 2. Орграф G(X, E) называется прадеревом или ориентированным деревом, растущим из корня x0, при следующих условиях:

1. Неориентированный граф G', соответствующий графу G, является деревом.

2. Единственная простая цепь между x0 и любой другой вершиной x графа G' является путем в орграфе G, идущим из вершины x0 в вершину x.

На рис. 21 изображено ориентированное дерево.

Рис. 21

В неориентированном графе G(X, E) вершина x называется концевой или висячей, если d(x) = 1, т. е. если этой вершине инцидентно единственное ребро e. Это ребро также называется концевым или висячим. С висячими вершинами связана следующая теорема.

Теорема 2. В любом дереве G(X, E) с p * 2 вершинами имеется не менее двух концевых вершин.

Доказательство. Пусть q - число ребер дерева G. В силу теоремы 1:

p = q + 1.

Кроме того, из теоремы 1.1 имеем:

Таким образом, получаем:

.(1)

Предположим, что x0 - единственная концевая вершина в дереве G. Тогда (x0) = 1, (x) 2, если x0. Отсюда:

.(2)

Неравенство (2) противоречит (1), поэтому либо концевых вершин нет, либо их по крайней мере две. Если концевых вершин в G нет, то (x) 2 для всех X. Тогда:

.(3)

Неравенство (3) тоже противоречит (1). Отсюда следует, что концевых вершин в G две или больше. Теорема доказана.

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

2.3 Подсчет деревьев

Теорема Кэли о числе деревьев -- названное в честь А. Кэли явное выражение в теории графов для числа деревьев с данным числом пронумерованных вершин. А именно, оказывается, что на n вершинах, пронумерованных числами от 1 до р, существует ровно рр ? 2 различных деревьев.

Количество деревьев на n пронумерованных вершинах оказывается также равным числу разложений р-цикла (12…р) в произведение (р-1) транспозиции, а также числу (соответствующим образом нормированных) многочленов степени n с заданными (р-1) критическими значениями общего положения. Наконец, это последнее является частным случаем топологической классификации разветвлённых накрытий сферы Римана -- тем самым, подсчёт числа деревьев оказывается частным случаем вычисления чисел Гурвица, соответствующим случаю накрывающей поверхности рода 0.

Доказательство. Пусть G(X, E) - дерево с p помеченными вершинами. Для простоты предположим, что вершины пронумерованы в произвольном порядке числами 1, 2, …, p. Рассмотрим способ, позволяющий однозначно закодировать дерево G.

В соответствии с теоремой 2 дерево G имеет концевые вершины. Пусть x1 - первая концевая вершина в последовательности 1, 2, …, p и пусть e1 = (x1, y1) - соответствующее концевое ребро. Удалим из дерева вершину x1 и ребро e1. Получим новое дерево G1 с числом вершин p - 1.

Найдем теперь первую концевую вершину x2 дерева G1 в последовательности вершин 1, 2, … …, p из множества {1, 2, …, p }\{x1}, далее возьмем концевое ребро e2 = (x2, y2) и удалим из G1 x2 и e2. Эту процедуру последовательно повторяем. Через (p-2) шага остается дерево из двух вершин xp-1, yp-1 и одного ребра ep-1 = (xp-1, yp-1). Рассмотрим последовательность вершин:

(G) = {y1, y2, …, yp-2}.

Очевидно, что по данному дереву последовательность строится однозначно. Покажем теперь, что по данной последовательности вершин (G) дерево G можно восстановить однозначно. В последовательности 1, 2, …, p существуют вершины, не принадлежащие (G). Выберем первую из них x1 и построим ребро e1 = (x1, y1). Затем удалим x1 из последовательности 1, 2, …, n и y1 удалим из (G). Аналогичным образом построим ребро e2 = (x2, y2). Продолжая этот процесс, мы однозначно восстановим дерево G. Рассмотрим пример.

Табл. 1

Построение кода	Восстановление
(G)	(G) и список вершин

Рассмотренный пример позволяет отметить следующие две особенности:

1. В списке (G) вершины могут повторяться.

2. При восстановлении дерева последнее ребро соединяет вершину yp-2 и оставшуюся в списке 1, 2, …, p вершину не равную yp-2.

Итак, существует взаимно однозначное соответствие между множеством помеченных деревьев с p вершинами и множеством последовательностей вершин (G). Число таких последовательностей равно, очевидно, pp-2, что и требовалось доказать.

Отметим, что среди pp-2 помеченных деревьев с p вершинами могут быть и изоморфные.

Определение 3. Подграф G1(X1, E1) неориентированного графа G(X, E) называется каркасом, или остовным деревом графа G, если G1 - дерево и X = X1.

Теорема 4. Граф G(X, E) тогда и только тогда обладает каркасом, когда он связен.

Доказательство. Необходимость этого очевидна. Докажем достаточность. Пусть G(X, E) - связный граф. Выясним, есть ли в графе G такое ребро, удаление которого не нарушает связности графа G. Если таких ребер нет, то граф есть дерево в соответствии с теоремой 1. Если же такое ребро, например e, существует, то выбросим его и придем к графу G1(X, E\{e}). Затем указанную процедуру проделываем с графом G1 и т. д. Через конечное число шагов будет построен, очевидно, каркас графа G. Теорема доказана.

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

Определение 4. Графом с нагруженными ребрами (нагруженным графом) называется неориентированный граф G(X, E), каждому ребру e?E которого поставлено в соответствие число (e) 0, называемое весом или длиной ребра e.

Аналогично можно определить нагруженный орграф.

Поставим задачу нахождения такого каркаса G1(X, E1) в нагруженном графе G(X, E), для которого сумма:

минимальна. Каркас с таким свойством называется минимальным каркасом. В соответствии с теоремой 4 каждый нагруженный связный граф обладает минимальным каркасом. Эта задача возникает при проектировании линий связи и электропередач, дорог, трубопроводов и т. п., когда требуется соединить системой каналов связи заданные узлы так, чтобы любые два узла были связаны (возможно, через другие узлы), а общая длина каналов связи была минимальной; при этом узлы можно считать вершинами нагруженного графа, весам ребер которого соответствует длина возможного канала связи между соответствующими узлами. Тогда искомая сеть каналов будет минимальным каркасом этого графа.

2.4 Алгоритм построения минимального каркаса

Пусть G(X, E) - связный нагруженный граф с p вершинами.

Шаг 1 . В качестве первого ребра искомого минимального каркаса выбираем ребро e1 с наименьшим весом (e1). Если таких ребер несколько, то берем любое из них.

Шаг 2 . В качестве второго ребра берем ребро e2 из множества E\{e1}, имеющее наименьший вес (e2), и такое, что множество {e1, e2} не содержит простых циклов. Если таких ребер несколько, то берем любое из них.

Шаг 3 . В качестве третьего ребра выбираем такое ребро e3 из множества E\{e1, e2}, которое имеет наименьший вес ?(e2) и для которого множество {e1, e2, e3} не содержит простых циклов. Если таких ребер несколько, берем любое из них.

Указанный процесс повторяется и через некоторое число k шагов дает множество E = {e1, e2, …, ek}, к которому нельзя добавить ребро без появления цикла. Подграф G1(X, E1) и является минимальным каркасом графа G(X, E).

Обоснование алгоритма.

В силу свойства 6 из теоремы 1 построенный подграф G1(X, E1) является деревом, поэтому:

k = p -1.

Доказательство минимальности каркаса G1(X, E1) разобьем на два этапа. Пусть сначала G(X, E) - полный граф, у которого веса всех ребер различны, и пусть G2(X, E2) - минимальный каркас графа G. Если E2 E1, то рассмотрим el - первое из ребер множества E1, не принадлежащее E2. В графе в силу свойства 6 теоремы 1 существует единственный простой цикл. Цикл содержит ребро e0E1. Граф G3(X, E3), где:

,

не содержит циклов и имеет n-1 ребро, поэтому он является деревом. Множество {e1, e2, …, el-1, e0} содержится в E2 и поэтому не содержит циклов. Тогда в силу рассмотренного выше алгоритма (e0) > (el). Отсюда следует, что суммарный вес дерева G3(X, E3) меньше веса дерева G2(X, E2). Это противоречит минимальности каркаса G2, поэтому E2 = E1 и G1(X, E1) - единственный минимальный каркас графа G.

В полученном графе единственным минимальным каркасом будет каркас, полученный с помощью рассмотренного алгоритма. Легко видеть, что этот каркас будет минимальным и в исходном графе G(X, E).

На рис. 22 изображены нагруженный граф G и его минимальный каркас G1.

Рис. 22

2.5 Кодирование деревьев

Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная, с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине, на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем 0 при движении по ребру в первый раз и 1 при движении по ребру второй раз (в обратном направлении). Если m -- число рёбер дерева, то через 2m шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из 0 и 1 (код дерева) длины 2m позволяет однозначно восстанавливать не только само дерево D, но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с n вершинами:

Список используемой литературы

1. Оре О. Теория графов -- 2-е изд. -- М.: Наука, 1980. -- 336с.

2. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: изд-во МГТУ им. Н.Э. Баумана, 2001.- 744 с. (Сер. Математика в техническом университете; Вып XIX).

3. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.- М.: Наука, Физматлит, 2000.- 544 с.- ISBN 5-02-015238-2.

4. Алексеев В.Б., Ложкин С.А. Элементы теории графов -- 324с.

5. Б.Н. Иванов, Дискретная математика. Алгоритмы и программы -- 561с.

6. М.О. Асанов, В.А. Баранский, В.В. Расин, 2001. (Rus).

Размещено на Allbest.ru

...