Выделение минимального остовного дерева
Изучение и создание алгоритма решения задачи о выделении минимального остовного дерева. Понятие теории графов. Характеристика алгоритма Прима, Краскала, Борувки. Определение каркаса, алгоритм выделения минимального остовного дерева нагруженного графа.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 03.11.2015 |
| Размер файла | 72,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Брянский государственный технический университет
Кафедра Высшей математики
Курсовая работа
по дискретной математике
«Выделение минимального остовного дерева»
Выполнил студент 15-БАС :
Звиададзе Илья
Введение
Цель работы
Целью данной работы является изучение и создание алгоритма решения задачи о выделении минимального остовного дерева.
Теория графов это один из разделов дискретной математики, изучающий свойства графов. Теория графов имеет огромное практическое значение, к примеру, маршрутизация данных.
Остовное дерево -- ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.
Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов:
любой ациклический подграф, в который входят все вершины графа, но не обязательно связный;
в несвязном графе -- подграф, состоящий из объединения остовных деревьев для каждой его компоненты связности.
Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа. Ударение в слове «остовный» у разных авторов указывается на первый (от слова омстов) или на второй слог.
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе -- это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
остовной дерево граф борувка
Теоретическая часть
Рассмотрим чертеж вида
Обозначения и определения
V - множество точек - вершины;
X - множество линий - ребра;
Графом называется совокупность множеств вершин и ребер.
v - номер вершины;
{v,w} - обозначение ребра;
{v,v} - петли;
Одинаковые пары - параллельные или кратные ребра;
Кратностью ребер называют количество одинаковых пар.
Пример: кратность = 3.
Если в графе есть петли и/или кратные ребра, то такой граф называют псевдографом.
Псевдограф без петель называется мультиграфом.
Мультиграф в котором ни одна пара не встречается более одного раза называется графом.
Если пары (v,w) являются упорядоченными, граф называется ориентированным (орграфом).
Ребра ориентированного графа называются дугами.
В неориентированном графе ребра обозначаются неупорядоченной парой - {v,w}.
В ориентированном графе дуги обозначаются упорядоченной парой - (v,w).
G, G0 - неориентированный граф, D, D0 - ориентированный.
Обозначают v,w - вершины, x,y,z - дуги и ребра.
Пример
1) V={v1, v2, v3, v4},
X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.
2) V={v1, v2, v3, v4, v5},
X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.
Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. (Для орграфа то же).
Подграф наз. собственным, если он отличен от самого графа.
Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.
Граф (орграф) наз связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.
Орграф наз односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой.
Псевдографом, ассоциированным с ориентированным псевдографом D=(V,X) наз. псевдограф G=(V,X0), в котором X0 получается из X заменой всех упорядоченных пар (v,w) на неупорядоченные {v,w}.
Орграф наз слабо связным, если связным является ассоциированный с ним псевдограф.
Если граф (орграф) не является связным (слабо связным), то он наз. несвязным.
Компонентой связности графа G (сильной связности орграфа D) наз. его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).
Примеры.
опр || назовем орграф D=(V,X) нагруженным, если на множестве дуг X определена некоторая функция , которую называют весовой функцией
Числа - вес дуги, (цена дуги).
Для любого пути П нагруженного орграфа D обозначим через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).
Величина l называется длиной пути. Если выбрать веса равными 1, то придем к ненагруженному графу.
Деревья и циклы
Граф G называется деревом, если он является связным и не имеет циклов. Граф G называется лесом, если все его компоненты связности - деревья.
Деревья обладают следующими свойствами:
1) Граф G есть дерево.
2) Граф G является связным и не имеет простых циклов.
3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.
4) две различные вершины графа G можно соединить единственной (и при этом простой) цепью.
5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл.
Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.
Предположим, что в графе G нет висячей вершины, тогда найдется цикл (в начале лекции это было доказано), тогда граф - не дерево.
Пусть G связный граф, а висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.
Пусть G - дерево с n-вершинами и m-ребрами. Тогда m(G)=n(G)-1.
Если m<n-1 то граф не связный.
Если m>n-1, и висячих вершин в графе нет, то можно выделить цикл, а следовательно, это - не дерево. В противном случае удалим висячую вершину вместе с инцидентным ей ребром. Повторяя эту операцию n-2 раза, придем к графу с двумя вершинами и более чем одним ребром это не дерево.
Пусть G - дерево. Тогда любая цепь в G будет простой.
Если цепь - не простая, то в G есть циклы G - не дерево.
Цепь единственна по той же причине.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G - связный граф. Тогда остовное дерево графа G должно содержать n(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер. Число называется цикломатическим числом графа G.
1. Постановка задачи
Пусть имеется связный неориентированный граф G, на ребрах которого задана весовая функция c (e). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом (spanning-tree) этого графа (иногда используют термин остовное дерево или остов). Весом остовного дерева будем считать сумму весов всех его ребер. Тогда возникает задача о нахождении максимального покрывающего дерева, т.е. такого, что его вес наибольший, либо равен весу любого из покрывающих деревьев для данного графа. Будем обозначать наибольшее покрывающее дерево графа G как MAX (G).
2. Методы решения данной проблемы
Остовным деревом графа называется дерево, содержащее все вершмины V графа. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер.
Идея решения:
Для остовного дерева верно следующее свойство:
Пусть G= (V,E) - свызный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через U подмножество множества вершин V. Если (u,v) - такое ребро наибольшей стоимости, что u из U и v из V\U, тогда для графа G существует остовное дерево максимальной стоимости, содержащее ребро (u,v)
На этом свойстве основан алгоритм Прима. В этом алгоритме строится множество вершин U, из которого "вырастает" остовное дерево. Пусть V={1,2,. n}. Сначала U={1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (u,v) такое, что u из U и v из V\U, затем вершина v переносится из множества V\U в множество U. Процесс продолжается до тех пор, пока множество U не станет равным множеству V.
Детали реализации:
Удобно выбрать представление в виде списка дуг.
Допустим, необходимо проложить кабель по территории университета, связав все его здания, так, чтобы из каждого здания кабель по какому-либо пути доходил до любого другого здания. Кроме того, предположим, что надо минимизировать общую длину прокладываемого кабеля. Если рассматривать здания как вершины, а кабели между зданиями как ребра, то эта работа с прокладыванием кабеля превращается в задачу определения каркаса, охватывающего здания территории университета, в котором общая длина проложенного кабеля должна быть минимальной. Такую задачу называют нахождением каркаса минимального веса. В нашей работе длина проложенного кабеля должна быть максимальной.
Определим понятие каркаса более формально. Если дан связный неориентированный граф G= (V, E), то каркас (также называемый остовным или стягивающим деревом) T= (V, E'), где E'?E - это связный граф без циклов. Иными словами, каркас неориентированного графа G - это подграф графа G, дерево, содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же набор вершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно |V|-1 ребро.
Предположим, что для каждого ребра e?E существует вес w (e), причем такой вес может выражать, например, цену, длину или время, необходимое для прохода по ребру (в нашем примере - длину кабеля между зданиями). Во взвешенном графе вес подграфа - это сумма весов его ребер. Тогда каркас T максимального веса - это каркас G, в котором вес дерева максимален относительно всех остовных деревьев G.
Если граф G несвязный, он не может иметь остовного дерева, но у него есть остовный лес. Также можно изменить алгоритм нахождения остовного дерева максимального веса, чтобы на выходе получать минимальный остовный лес.
В алгоритме Краскала используется жадный подход к решению задачи, т.е. в любой момент выполнения данных алгоритмов существует множество ребер E', представляющее подмножество некоторого минимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребер выбирается "лучшее" ребро, обладающее определенными свойствами, и добавляется к формируемому каркасу максимального веса. Одним из важных свойств любого ребра, добавляемого к E', является его безопасность, т.е. то, что обновленное множество ребер E' будет продолжать представлять подмножество некоторого минимального остовного дерева..
Алгоритм выделения минимального остовного дерева нагруженного графа
Существует 2 алгоритма для выделения минимального остовного дерева в нагруженном графе: алгоритм Прима и алгоритм Краскала.
Алгоритм Краскала
Идея алгоритма.
Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения. Можно идти от вершин и для каждой из них искать минимальное ребро (как это сделано в алгоритме Прима) а можно для каждого ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.
Другими словами, алгоритм организует процесс роста компонент связности в процессе которого он объединяются друг с другом до тех пор пока не останется одна являющаяся конечным результатом.
Алгоритм:
§ Создаем список ребер по возрастанию.
§ Создаем множество компонент связности, каждая из которых содержит ровно одну вершину.
§ Пока компонент связности больше чем одна.
o Взять ребро из начала списка ребер.
o Если ребро соединяет две разных компоненты связности то
§ Компоненты связности объединить в одну.
Пример работы алгоритма Краскала
Рисунок 1. Начальный граф
Рисунок 2. Максимальное остовное дерево.
Алгоритм Прима
Идея алгоритма.
Пусть часть остовного дерева уже построена. Это утверждения всегда верно, так как в начале процесса вершина с которой начинается построение уже входит в дерево. Итак если часть основного дерева уже есть, то множество вершин графа можно разделить на два подмножества: подмножество состоящее из вершин уже построенного остовного дерева и оставшихся вершин графа.
Очевидно, что среди ребер соединяющихся эти два множества существует ребро наименьшего веса. Можно доказать, (но мы здесь этого делать не будем) что минимальное дерево проходит через это ребро.
Алгоритм:
§ Множество остовных вершин - исходная веришны
§ Множество оставшихся - все вершины за исключением исходной.
§ Пока множество оставшихся не пусто
o Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.
o Для найденного ребра, вершину принадлежащую множеству оставшихся:
§ Вычеркиваем из множества оставшихся.
§ Добавляем к множеству остовных.
Алгоритм Борувки
Алгоримтм Борувки -- это алгоритм нахождения минимального остовного дерева в графе.
Впервые был опубликован в 1926 году Отакаром Борувкой в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например Флореком, Перкалом и Соллином. Последний, кроме того, был единственным западным учёным из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям
Работа алгоритма состоит из нескольких итераций, каждая из которых состоит в последовательном добавлении рёбер к остовному лесу графа, до тех пор, пока лес не превратится в дерево, то есть, лес, состоящий из одной компоненты связности.
Алгоритм:
1)Изначально, пусть T -- пустое множество рёбер (представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).
2)Пока T не является деревом (что эквивалентно условию: пока число рёбер в T меньше, чем V - 1, где V -- число вершин в графе):
Для каждой компоненты связности (то есть, дерева в остовном лесе) в подграфе с рёбрами T, найдём самое дешёвое ребро, связывающее эту компоненту с некоторой другой компонентой связности. (Предполагается, что веса рёбер различны, или как-то дополнительно упорядочены так, чтобы всегда можно было найти единственное ребро с минимальным весом).
Добавим все найденные рёбра в множество T.
Полученное множество рёбер T является минимальным остовным деревом входного графа.
Сложность алгоритма
На каждой итерации число деревьев в остовном лесу уменьшается по крайней мере в два раза, поэтому всего алгоритм совершает не более O(\log V) итераций. Каждая итерация может быть реализована со сложностью O(E), поэтому общее время работы алгоритмы составляет O(E \log V) времени (здесь V и E -- число вершин и рёбер в графе, соответственно).
Однако для некоторых видов графов, в частности, планарных, оно может быть уменьшено до O(E). Существует также рандомизированный алгоритм построения минимального остовного дерева, основанный на алгоритме Борувки, работающий в среднем за линейное время
Заключение
В курсовой работе был реализован алгоритм для выделения минимального остовного дерева. Были рассмотрены алгоритмы выделения минимального остовного дерева и частные случаи их реализации.
Список использованной литературы
Кузнецов О.П. Дискретная математика для инженера, 3-е изд., перераб. и доп. - СПб: Издательство «Лань», 2004.
Размещено на Allbest.ru
...Подобные документы
Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.
курсовая работа [225,0 K], добавлен 30.04.2011Минимальное остовное дерево связного взвешенного графа и его нахождение с помощью алгоритмов. Описание алгоритма Краскала, возможность строить дерево одновременно для нескольких компонент связности. Пример работы алгоритма Краскала, код программы.
курсовая работа [192,5 K], добавлен 27.03.2011Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
курсовая работа [362,9 K], добавлен 24.11.2010Остовное дерево связного неориентированного графа. Алгоритм создания остовного дерева, его нахождение. Сущность и главные особенности алгоритма Крускала. Порядок построения алгоритма Прима, вершина наименьшего веса. Промежуточная структура данных.
презентация [140,8 K], добавлен 16.09.2013Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
реферат [131,8 K], добавлен 11.11.2008Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Особливості реалізації алгоритмів Прима та Крускала побудови остового дерева у графі. Оцінка швидкодії реалізованого варіанта алгоритму. Характеристика різних методів побудови остовних дерев мінімальної вартості. Порівняння використовуваних алгоритмів.
курсовая работа [177,3 K], добавлен 18.08.2010Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
курсовая работа [466,3 K], добавлен 28.04.2011Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.
курсовая работа [311,3 K], добавлен 15.06.2015Сущность теории графов и ее применение на современном этапе в различных отраслях науки и техники, особенно в экономике и социологии. Понятие дерева, его разновидности, характерные свойства. Операции, совершаемые над графами и возможности их реализации.
контрольная работа [1,6 M], добавлен 08.12.2009Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
контрольная работа [740,3 K], добавлен 09.03.2015Методы решения комбинаторных задач детьми на уроках математики. Определение уровня логического и алгоритмического мышления учащихся. Ознакомление школьников с методом организованного перебора, с помощью графа, таблицы и дерева возможных вариантов.
курсовая работа [1,3 M], добавлен 24.11.2014Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Побудування графа та матриці інцидентності. Перетворення графа у зважений за допомогою алгоритму Дейкстри, знаходження довжини найкоротшого шляху між двома вершинами та побудування дійсного шляху. Обхід дерева у прямому та зворотному порядках.
курсовая работа [144,1 K], добавлен 03.07.2014
