Лекции по "Развитию операционных систем"

Лекция 8.

 

п.8.  Деревья. Остовные деревья.

 

8.1.  Деревья.

 

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

Определение 8.1.  Деревом называется граф T(V, E) без циклов. Лес – это граф, компоненты которого являются деревьями.

Ориентированное дерево T¢ представляет собой свободный от петель ориентированный граф, соотнесенный граф которого является деревом.

 

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

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

Если корень выбран, уровень вершины v определяется длиной единственной цепи из корня в вершину v.

 

Определение 8.2.  Высотой дерева называется длина самой длинной цепи от корня до листа. Высоту дерева будем обозначать h(T).

 

Пример 8.1.

 

,

 

 

Примеры изображения деревьев в программировании.

 

 

 

 

 

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

 

Генеалогическое дерево семейства Бернулли.

 

Купеческая протестантская семья Бернулли жила в Антверпене (Нидерланды). Свой род она вела из Фландрии, где Бернулли, в XV в. носили еще фамилию Бернуйла (Bernuilla). В связи с событиями XVI в. на территории Нидерландов, что направленные были против протестантов, семья Бернулли была вынуждена уехать во Франкфурт-на-Майне. В это время главой семьи был Якоб Бернулли, который умер в 1583 г.

Среди Бернулли некоторые имена повторялись из поколения в поколение, поэтому их различают, как королей, присоединив к имени соответствующую цифру. В виде дерева показана родословная семейства Бернулли.

Якоб I (1654-1705) – швейцарский математик. По образованию богослов. С 1687 г. профессор математики Базельского университета. Ему принадлежат важные заслуги в развитии анализа бесконечно малых, начало которому положила работа Лейбница, опубликованная в 1684 г. Он вычислил площади многих плоских фигур, площади поверхностей и длины линий. Другие работы относятся к алгебре, арифметике, геометрии, теории рядов, теории вероятностей, а также к физике. В книге «Искусство предположений» доказал теорему (названную позже его именем), имеющую важное значение в теории вероятностей и ее приложениях к статистике. Учениками Якоба I были: его младший брат Иоганн I, племянник Николай I, член Петербургской академии наук, механик и математик Я. Герман, отец великого Л. Эйлера — Пауль Эйлер.

Иоганн I (1667-1748). Брат Якоба I. Десятый ребенок в семье Николая. По образованию врач. С 1695 г. профессор математики Гронингенского университета (Голландия). С 1705 г. профессор математики Базельского университета. Почетный член Петербургской академии наук.

Николай I (1687-1759) – швейцарский математик, сын Николая. По образованию юрист. Был профессором математики в Падуе, а затем профессором логики и права в Базельском университете. Его исследования посвящены теории вероятностей, интегральному исчислению, демографии.

Николай II (1695-1726), сын Иоганна I. По образованию юрист. Профессор права в Берне, профессор математики в Петербурге.

Даниил I (1700-1782). Уроженец Гронингена, сын Иоганна I. По образованию врач. В 1725-1733 гг. работал на кафедрах физиологии и механики в Петербургской академии наук. С 1733 г. профессор по кафедре физиологии, с 1750 г. профессор по кафедре механики в Базеле. Почетный член Петербургской академии наук. В математике Даниилу Бернулли принадлежат: метод численного решения алгебраических уравнений с помощью возвратных рядов, работы по обыкновенным дифференциальным уравнениям, по теории вероятностей с приложением к статистике народонаселения и отчасти у астрономии, по теории рядов. В работах, завершенных написанным в Петербурге трудом «Гидродинамика» (1738), вывел основное уравнение стационарного движения идеальной жидкости, носящее его имя. Разрабатывал кинематические представления о газах.

Иоганн II (1710-1790), сын Иоганна I. По образованию юрист. Профессор элоквенции (красноречия), профессор математики в Базеле.

Иоганн III (1744-1807), старший сын Иоганна II. По образованию юрист. Астроном Берлинской академии наук, там же директор математического класса.

Даниил II (1751-1834), второй сын Иоганна II. По образованию врач, профессор красноречия в Базеле.

Якоб II (1759-1789), третий сын Иоганна II. По образованию юрист. Математик Петербургской академии наук.

Кристоф (1782-1863), сын Даниила II. Профессор технологии в Базеле.

Иоганн-Густав (1811-1863), сын Кристофа. Профессор технологии в Базеле.

Представители рода Бернулли живут в Базеле и в настоящее время.

 

Рассмотрим некоторые утверждения, которые относятся к деревьям.

Теорема 8.1.  Для любых вершин a и b дерева T существует единственная цепь из a в b.

Доказательство.  Доказательство проведем методом «от противного». Предпо-ложим, что для некоторых вершин a и b дерева T цепь из a и b не является единственной, и покажем, что в таком случае T не будет деревом.

 

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

Теорема 8.2.  Если для любых двух вершин графа G существует единственная цепь из вершины a в вершину b, тогда G является деревом.

 

Теорема 8.3.  Если у дерева T имеется e ребер и v вершин, то v=e+1.

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

Рассмотрим теперь ориентированное дерево T¢, порожденное деревом T. У каждой дуги ориентированного дерева одна и только одна конечная вершина. Следовательно, число дуг и вершин одно и то же, исключая корневую. Если учесть корневую вершину, получим, что вершин на одну больше, чем дуг.

Значит, и исходное дерево имеет число вершин на одну больше, чем число ребер.

■

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

Теорема 8.4.  Если в связном графе G, содержащем e ребер и v вершин и имеем v=e+1, то G является деревом.

 

 

8.2.  Остовные деревья.

 

В этой части лекции мы рассмотрим так называемые остовные деревья и их применение для решения некоторого класса прикладных задач. Сначала дадим определение остовного дерева.

Определение 8.3.  Дерево T называется остовным деревом графа G, если T – подграф графа G и каждая вершина G является вершиной в T.

 

Теперь сформулируем теорему, которую примем без доказательства.

Теорема 8.5.  У каждого связного графа существует подграф, который является остовным деревом.

 

Для построения остовных деревьев существуют разные методы. Самыми распространенными являются два метода: метод поиска в ширину и метод поиска в глубину.

Согласно методу поиска остовного дерева в ширину произвольную вершину v0 графа G выбираем в качестве корня дерева T. Для каждой вершины v графа G, смежной с вершиной v0, в дерево T добавляется вершина v и ребро (v0, v). Это вершины уровня 1. Затем берем каждую вершину vi уровня 1 и для каждой вершины vj графа G, смежной с вершиной vi из тех, что еще не выбраны, добавляем в дерево T вершину vj и ребро (vi, vj). Вершины, добавленные на этом этапе, - это вершины уровня 2. Продолжаем процесс, пока в графе G не останется вершин, которые можно было бы добавить в дерево. По построению T является деревом. Если расстояние от v0 до вершины v графа G равно n, то эта вершина будет добавлена в дерево на уровне n. Следовательно, T несомненно, является остовным деревом.

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

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

Метод поиска в глубину начинается с задания вершины графа, которую будем считать корнем. Выбираем вершину vi, смежную с корнем, и формируем ребро дерева. Затем выбираем вершину vj, смежную с ранее выбранной вершиной vi, и формируем новое ребро. По ходу необходимо помечать использованные вершины, с тем, чтобы каждая вершина использовалась один раз. Если, находясь в вершине v, мы выбираем другую вершину w и обнаруживаем, что вершина w уже была добавлена в дерево, то ребро (v, w) между этими вершинами не может быть добавлено в дерево.

 

Когда имеем исходный граф, то само собой возникает вопрос: сколько можно построить остовных деревьев для помеченного графа с n вершинами? Ответ на этот вопрос дает теорема Кэли, которая рассматривает число остовных деревьев для Kn.

Теорема 8.6.  (Теорема Кэли)  Число остовных деревьев для Kn, у которого вершины помечены, равно .

 

Если рассматривать определенный граф, который отличается от полного, то эта формула не годится для определения числа остовных графов. В этом случае используют теорему Кирхгофа. Прежде чем сформулировать теорему, сначала введем понятие матрица Кирхгофа.

Определение 8.4.  Матрицей Кирхгофа связного графа G с помеченными вершинами называется матрица Kv´v=K(G), , которую можно определить следующим образом:

.

Теорема 8.7.  (Теорема Кирхгофа)  Число остовных деревьев в связном графе G порядка n³2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K(G).

 

Пример 8.2.  Найти число остовных деревьев данного графа.

 

 

Решение.  Сначала составляем для данного графа матрицу Кирхгофа.

.

Теперь находим алгебраическое дополнение, например, для элемента k11 матрицы Кирхгофа.

.

Проверим, например, для элемента k23.

.

Итак, получаем, что данный граф имеет 8 остовных деревьев.

,

 

 

8.3.  Алгоритм Краскала и алгоритм Прима.

 

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

Определение 8.5.  Вес остовного дерева взвешенного графа G равен сумме весов, приписанных ребрам остовного дерева. Будем обозначать w(T).

Минимальным остовным деревом называется такое остовное дерево графа G, что вес T меньше или равен весу любого другого остовного дерева графа G. Вес минимального остовного дерева будем обозначать wmin(T).

 

Построение остова графа G, имеющего наименьший вес, имеет широкое применение при решении некоторого класса задач прикладного характера. Дадим формулировку одной из таких задач.

Формулировка задачи:  Пусть, например, G=(V, E, W) служит моделью железнодорожной сети, соединяющей пункты v1, v2, …, vnÎV, а w(vi, vj) – расстояние между пунктами vi и vj. Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все пункты v1, v2, …, vn были связаны между собой телеграфной сетью, протяженность которой была бы наименьшей.

 

Мы рассмотрим два способа построения минимального остовного дерева взве-шенного графа: алгоритм Краскала и алгоритм Прима.

 

Первым рассмотрим алгоритм Краскала. Идея метода состоит в том, чтобы формировать дерево T(V, E), выбирая ребра с наименьшим весом так, чтобы не возникал цикл.

Алгоритм Краскала:

1)  Выбрать в графе G ребро e минимального веса, не принадлежащее множеству E и такое, что его добавление в E не создает цикл в дереве T.

2)  Добавить это ребро во множество ребер E.

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

 

Вторым рассмотрим алгоритм Прима. Принципиальное отличие алгоритма состоит в том, что всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остовное дерево.

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

1)  Выбрать вершину v0 графа G и ребро с наименьшим весом e1, для которого v0 – одна из вершин, и сформировать дерево T1.

2)  Для заданного дерева Tk с ребрами e1, e2, e3, …, ek, если имеется вершина, не принадлежащая Tk, выбрать ребро с наименьшим весом, смежное с ребром дерева Tk и имеющее вершину вне дерева Tk. Добавить в дерево Tk, формируя дерево Tk+1.

3)  Продолжить, пока имеются  вершины графа G, не принадлежащие дереву.

 

Построение минимального оствного дерева можно проводить двумя способами:  1)  остов графа строится непосредственно на самом графе, выделяя ребра утолщенной линией, которые входят в остовное дерево;  2)  строится отдельно корневое дерево, которое будет минимальным остовным деревом. Второй случай используется, если требуется определить высоту построенного дерева.

 

Пример 8.3.  Для данного взвешенного графа:

   1)  определить степень  каждой вершины;

   2)  построить матрицу  смежности вершин, матрицу смежности  ребер, матрицу инциденций;

   3) найти число остовных деревьев, используя теорему Кирхгофа;

   4) найти минимальное корневое остовное дерево, используя алгоритм Краскала или алгоритм Прима. Определить высоту построенного дерева.