Алгоритмы на графах

Министерство  образования и науки

Государственное образовательное учреждение

высшего профессионального образования

 

Тульский  государственный университет

Кафедра «Электронных вычислительных машин»

 

 

 

Алгоритмы на графах

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к контрольно-курсовой работе по дисциплине

«Методы программирования»

 

 

 

 

 

 

Автор работы:   студент гр. 230791 Чернов Денис Владимирович

Руководитель  работы: доц. кафедры ЭВМ Басалова Г.В.

Работа  защищена: ______________ оценка _________________

 

 

 

 

Тула 2011

Оглавление

 

Введение 3

1. Основные сведения о матрицах смежности. 4

2. Математические зависимости для определения заданных свойств графа 5

2.1. Основные определения. 5

2.2. Алгоритм Прима «Построения минимального остовного дерева» 6

2.3. Алгоритм Дейкстры «Нахождение минимального пути» 10

3. Структура программы 14

3.1 Хранение информации о графе 15

3.2 Входные и выходные данные 15

3.3 Анализ программы 17

4. Руководство пользователя 23

Заключение 25

Список литературы 26

Приложение А 27

Схема программной реализации алгоритма Дейкстры 27

Схема программной реализации алгоритма Прима 28

Приложение Б 29

Листинг программы 29

 

Введение

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

Курсовой  проект выполняется с целью закрепления  знаний по курсу «Методы программирования»  и развития навыков самостоятельного проектирования алгоритмов и программ.

Задачами  курсового проекта являются:

• изучение структур хранения графов в ЭВМ
• изучение основных свойств графов 
• оформления и выпуска проектной документации в соответствии с ГОСТ.

Графом  называется алгоритмическая модель, состоящая из множества вершин (узлов) v и соединяющих их ребер e. Ребро - неупорядоченная пара вершин графа. Ребра называются смежными, если они имеют общую вершину. Вершины называются смежными, если есть ребро их соединяющее. Ребро, которое соединяет вершины, называется инцидентным этим вершинам, а вершины – инцидентные этому ребру.

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

Исходные  данные к курсовому проекту:

Способ представления  графа в ЭВМ:

• Матрица смежности.

Перечень  свойств графа, которые необходимо определить:

• Определить минимальное остовное дерево графа.
• Определить минимальный путь между заданными вершинами.

1. Основные  сведения о матрицах смежности.

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

Если  в клетке i,j установлено значение ПУСТО, то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Иначе дуга есть. Чаще всего за значение ПУСТО берут 0, а в клетки, которые обозначают наличие дуги, вписывают вес этой дуги. Если граф не взвешенный, то вес дуги считается равным единице.

        

Рис.1 Невзвешенный граф G и его матрица смежности

         

Рис.2 Взвешенный граф G и его матрица смежности

 

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

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

Разрежённым называется граф, в котором множество рёбер значительно больше квадрата множества вершин.

  Если граф разрежён, то большая  часть памяти напрасно будет  тратиться на хранение нулей,  зато в случае неразрежённых графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно (n^2)/8 байт памяти, что может быть на порядок лучше списков смежности.

2. Математические  зависимости для определения  заданных свойств графа

1. Основные  определения.

 

Неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

• V это непустое множество вершин или узлов,
• E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

 

Путь в графе G =(V,E) последовательность вершин   при  , таких, что две любые последовательные вершины соединены хотя бы одной дугой из E.

Число k рёбер в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном.

 

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

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

 

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

• Для построения минимального остовного дерева во взвешенном графе – алгоритм Прима
• Для нахождения минимального пути между двумя заданными вершинами во взвешенном графе – алгоритм Дейкстры.

2. Алгоритм  Прима «Построения минимального остовного дерева»

 

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

Свойства остовных деревьев:

• Любое остовное дерево в графе с n вершинами содержит ровно n − 1 ребро.
• Число остовных деревьев в полном графе на n вершинах выражается формулой Кэли:
• В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.

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

                         

Рис.3 Минимальное остовное дерево некоторого графа G

 

Свойства минимальных остовов

• Минимальный остов единственен, если веса всех рёбер различны. В противном случае, может существовать несколько минимальных остовов (какой именно будет выбран алгоритмом Прима, зависит от порядка просмотра рёбер/вершин с одинаковыми весами/указателями)
• Минимальный остов также является остовом, минимальным по произведению всех рёбер (предполагается, что все веса положительны). В самом деле, если мы заменим веса всех рёбер на их логарифмы, то легко заметить, что в работе алгоритма ничего не изменится, и будут найдены те же самые рёбра.
• Минимальный остов является остовом с минимальным весом самого тяжёлого ребра.
• Критерий минимальности остова: остов является минимальным тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра. В самом деле, если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом (добавив это ребро в остов, и удалив самое тяжелое ребро из цикла). Если же это условие не выполнилось ни для одного ребра, то все эти рёбра не улучшают вес остова при их добавлении.

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

Этот  алгоритм назван в честь американского  математика Роберта Прима (Robert Prim), который открыл этот алгоритм в 1957 г. Впрочем, ещё в 1930 г. этот алгоритм был открыт чешским математиком Войтеком Ярником (Vojtěch Jarník). Кроме того, Эдгар Дейкстра (Edsger Dijkstra) в 1959 г. также изобрёл этот алгоритм, независимо от них.

Описание алгоритма

Сам алгоритм имеет очень простой вид. Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое,   ребро).

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

Вот как выглядит общий алгоритм построения минимального остовного дерева в псевдокоде:

MST-GENERIC (G, w)

1: A ← 0

2: while (пока) A не является остовом

3: do найти безопасное ребро (u, v) ∈ E для A

4: A ← A ∪ {(u, v)}

5: return A

 

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

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

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

Удалим  теперь из   ребро  , и добавим ребро  . По только что сказанному, вес остова в результате не мог увеличиться (уменьшиться он тоже не мог, поскольку  было оптимальным). Кроме того,   не перестало быть остовом (в том, что связность не нарушилась, нетрудно убедиться: мы замкнули путь   в цикл, и потом удалили из этого цикла одно ребро).

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

3. Алгоритм  Дейкстры «Нахождение минимального пути»

 

Пусть задан простой неориентированный  граф G = (V, E), как конечное множество  вершин V и множество E неупорядоченных  пар {vi, vj} – ребер. Каждому ребру предписано действительное число a[i][j] > 0, которое называется длиной этого ребра. Требуется найти кратчайший путь между заданными вершинами s и q, то есть такую последовательность вершин u1,u2,…,un, что u1=s, un=q, {ui, ui+1}ÎE для всех 1 £ i £ n-1, и сумма длин ребер {ui, ui+1} минимальна. Задача решается с помощью алгоритма Дейкстры:

• Каждой вершине припишем временный вес t (vi) = ¥. Положим t (s) = 0 и далее t (s) изменяться не будет, т.е. t (s) – постоянный вес вершины s. Положим v = s.
• Для всех вершин u = v_i, смежных с v, имеющих временный вес, изменяем вес по формуле .
• Устанавливаем постоянный вес той вершины u, которая имеет наименьший временный вес. Положим v = u. Если v = q, то t (v) – длина кратчайшего пути из s в q. Если v ¹ q, то переходим к шагу 2.