Автор работы: Пользователь скрыл имя, 06 Апреля 2011 в 04:53, курсовая работа
Теория графов – это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин.
В задаче Прима-Краскала жадный алгоритм дает точное оптимальное решение.
Как
известно (это легко доказать, скажем,
по индукции), дерево с n вершинами имеет
n-1 ребер. Оказывается, каждое ребро надо
выбирать жадно (лишь бы не возникали циклы).
(краткое описание)
1. В цикле n-1 раз делай: выбрать самое короткое еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.
Выбранные таким образом ребра образуют искомое остовное дерево.
Чтобы новое ребро не образовывало цикла со старыми, до построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра (x,y), где x и у имеют разные цвета, вершина у и все, окрашенные в ее цвет (т. е. ранее с ней соединенные) перекрашиваются в цвет x. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.
Итак, более подробный алгоритм выглядит так.
Алгоритм Прима-Краскала
Докажем, что описанный алгоритм получает в точности минимальное решение.
Для доказательства нам понадобится очень простое утверждение:
Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.
Действительно,
пусть добавлено ребро (u, v) – «добавлено»
означает, что ребро – новое, что раньше
его в дереве не было. Поскольку дерево
является связным графом, то существует
цепь С(u, ..., v) из нескольких ребер, соединяющая
вершины u и v. Добавление ребра (u, v) замыкает
цепь, превращая ее в цикл.
Теорема. Алгоритм Прима-Краскала получает минимальное остовное дерево.
Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т. е. ранее не связанные. Этот граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, ..., после проведения (n-1)-го ребра остался один цвет, т. е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер, т. е. n вершин. Следовательно, граф есть остовное дерево.
Осталось доказать, что оно имеет минимальную длину. Пусть { } ребра остовного дерева в том порядке, как их выбирал алгоритм, т. е. . Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е.
Если полученное дерево не минимально, то существует другое дерево, задаваемое набором из n-1 ребер { }, такое что сумма длин меньше суммы длин . С точностью до обозначений
Может быть, , и т.д., но так как деревья разные, то в последовательностях (2) и (3) найдется место, где ребра отличаются. Пусть самое левое такое место – k, так что (k может равняться единице, это не испортит доказательства). Поскольку выбиралось по алгоритму самым малым из необразующих цикла с .ребрами , то . Теперь добавим к дереву (3) ребро в нем появится цикл, содержащий ребро и, может быть, какие-то (или все) ребра из , но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора , причем Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.
Если не предполагать, что все ребра разные, то в доказательстве могло бы получиться, что , и нам пришлось бы двигаться дальше по последовательностям (2) и (3), пока бы мы не нашли . Это усложняет доказательство, но не меняет заключения.
В
заключение анализа алгоритма оценим
требуемую память и требуемое число операций.
В варианте Прима надо хранить 2n координат
точек, в варианте Краскала – n2 расстояний;
в обоих вариантах удобно хранить 2(n-1)
номеров вершин, т е. n-1 ребер ответа. Всего
требуется памяти 0(n ), т.е. порядка n2,
что, учитывая реальные величины n, необременительно.
Для нахождения текущего минимального
ребра надо просмотреть 0(n2) чисел
и сделать это надо n-1 раз, так что временная
сложность алгоритма 0(n3). Это тоже
реально. Задача Прима-Краскала относится
к просто и точно решаемым.
Пример 1. (вариант 17 контрольной работы по теме «Графы»)
Найти остовное дерево минимальной длины для графа, заданного следующей матрицей весов
Решение.
Изобразим граф, заданный таблицей весов:
Воспользуемся алгоритмом Прима-Краскала (описание алгоритма на странице 14 курсового проекта).
1 шаг: Раскрашиваем вершины графа в разные цвета:
2
шаг: Находим ребро минимальной длины
и включаем его в остов. Соединенные вершины
остова перекрашиваем в один цвет:
3 шаг: Находим следующее ребро минимальной длины, не входящее в остов, и включаем его в остов. Все вершины, связанные с ребром, перекрашиваем в один цвет:
4 шаг: повторяем основной шаг:
5 шаг: повторяем основной шаг:
Все вершины графа связаны ребрами – мы получили искомый остов. Его матрица весов имеет вид:
На
этом примере была также протестирована
реализация алгоритма Прима-Краскала
на языке Паскаль, приведенная в
Приложении. Результаты тестирования
совпадают с полученным нами решением:
Примечание:
матрицу неориентированного графа достаточно
задавать выше (ниже) ее главной диагонали.
Пример 2. Найти остовное дерево минимальной длины для следующего графа:
Искомое остовное дерево:
Результаты тестирования программы, приведенной в Приложении:
Пример 3. Случай вырожденного графа с пятью вершинами:
Заключение
Теория графов, будучи крупной ветвью комбинаторной математики, интенсивно изучалась в течение не одной сотни лет. Было выявлено много важных и полезных свойств графов, однако многие задачи еще ждут своего решения. Как и множество других предметных областей, которые приходилось изучать, алгоритмическое исследование графов возникло сравнительно недавно. И хотя некоторые фундаментальные алгоритмы открыты давно, все же большая часть интереснейших алгоритмов получена в течение нескольких последних десятилетий. Даже простейшие алгоритмы на графах позволяют получить полезные компьютерные программы, а нетривиальные алгоритмы относятся к числу наиболее элегантных и интересных из известных алгоритмов. Чтобы продемонстрировать все разнообразие приложений, использующих графы для обработки данных, рассмотрим нескольких примеров.
Географические карты. Путешественник, прежде чем отправиться в путь, желает получить ответ на вопросы типа: "Какой маршрут из Принстона в Сан-Хосе потребует наименьших расходов?' Пассажир, для которого время дороже денег, хотел бы получить от- ответ на такой вопрос: "Каким путем быстрее всего добраться из Принстона в Сан-Хосе?" Чтобы ответить на вопросы подобного рода, мы выполняем обработку информации, характеризующей соединения (пути следования) между элементами (городами и населенными пунктами).
Гипертекст. Когда мы просматриваем Web-каталоги, мы сталкиваемся с документами, содержащими различные ссылки (соединения) на другие документы, и переходим от документа к документу, щелкая мышью на этих ссылках. Сама по себе "всемирная паутина" представляет собой граф, в котором в качестве элементов выступают документы, а соединения суть связи. Алгоритмы обработки графов являются важными компонентами поисковых механизмов, которые помогают определить местоположение информации в Web.
Микросхемы. Микросхемы содержат такие элементы, как транзисторы, резисторы, конденсаторы, которые связаны между собой сложнейшим образом. Для управления машинами, изготавливающими микросхемы, и для проверки, выполняют ли эти цепи заданные функции, используются компьютеры. Мы хотим получить ответы на простые вопросы наподобие "Имеются ли в цепи условия для короткого замыкания?" и на более сложные вопросы, такие как "Можно ли скомпоновать микросхему на кристалле таким образом, чтобы шины не пересекались?". В данном случае, ответ на первый вопрос зависит только от свойств соединений (шин), в то время как для ответа на второй вопрос потребуется подробная информация о шинах, элементах, которые эти шины соединяют, и физических ограничениях, накладываемых кристаллом.
Составление расписаний. Производственный процесс требует решения различных задач под воздействием некоторого множества ограничений, по условиям которых решение одной задачи не может быть начато до тех пор, пока не будет завершено решение другой задачи. Мы представляем эти ограничения в виде соединений между этими задачами (элементами), при этом перед нами возникает задача составления расписаний (scheduling) в ее классическом виде: как построить временной график решения задач таким образом, чтобы удовлетворить заданным ограничениям и завершить данный процесс за минимально возможное время?
Транзакции. Телефонная компания поддерживает базу данных телефонного трафика. В этом случае соединения представляют телефонные вызовы. Мы заинтересованы в том, чтобы знать все, что касается характера структуры соединений, ибо хотим проложить провода и установить коммутаторы так, чтобы эффективно справляться с телефонным трафиком.
Еще одним примером может служить то, как финансовое учреждение отслеживает операции купли/продажи на рынке. Соединение в рассматриваемом случае представляет собой передачу денег продавцом покупателю. Знание свойств структуры соединений в данном случае помогает лучше понять особенности рынка.
Задачи поиска сочетаний. Студенты обращаются с заявлениями на замещение должностей в таких общественных организациях, как общественные клубы, университеты или высшие медицинские учебные заведения. Элементы соответствуют студентам и институтам, тогда как связи соответствуют приложениям. Мы хотим найти методы, устанавливающие соответствие между вакантными должностями и заинтересованными в их получении студентами.