Обзор алгоритмов на графах

Нижегородский Государственный Технический  Университет

 

 

 

Реферат на тему:

«Обзор алгоритмов на графах»

 

 

 

 

 

 

 

                                                                                        Выполнил:

                                                                                        Студент группы 09-В-3

                                                                  Долгов Евгений

   Проверила: Ломакина Л.С.

 

 

 

 

 

 

 

 

 

Нижний Новгород, 2010

 

 

 

О Г Л А  В Л Е Н И Е

                                                                                                                          Стр.

1. Введение   .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .     3
2. Алгоритмы на графах .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .     3

1. Методы систематического обхода вершин графа  .    .    .    .    .     4

• Алгоритм поиска в глубину
• Алгоритм поиска в ширину

2. Остовное дерево наименьшего веса. Задача Штейнера     .    .     7

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

3. Задача плоской укладки   .    .    .    .    .    .    .    .    .    .    .    .    .    .   10

• Гамма-алгоритм

4. Задача раскраски графа     .   .    .    .    .    .    .    .    .    .    .    .    .    .  13

• Метод неявного перебора
• Приближенный алгоритм

5. Нахождение кратчайших путей .    .    .    .    .    .    .    .    .    .    .    .   15

• Алгоритм Дейкстры
• Алгоритм Флойда

6. Эйлеровы графы .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .   18
7. Задача о наибольшем потоке    .    .    .    .    .    .    .    .    .    .    .    .  19

• Алгоритм Форда-Фалкерсона

3. Заключение    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    20

 

 

 

ВВЕДЕНИЕ

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

С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий  метрополитена. Точками на ней представлены станции, а линиями – пути движения поездов. Исследуя свою родословную, мы строим так называемое генеалогическое  древо. И это древо – граф.  Графы служат удобным средством  описания связей между объектами. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда  от пункта А до пункта Б. Если таких маршрутов окажется несколько, хотелось бы выбрать в определенном смысле оптимальный, например самый короткий или самый безопасный. Для решения подобных задач выбора требуется проводить определенные вычисления над графами.

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

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

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

 

 

 

АЛГОРИТМЫ НА ГРАФАХ

Методы систематического обхода вершин графа

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

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

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

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

Алгоритм поиска в глубину

Поиск в глубину представляет собой классический гибкий алгоритм, который применяется для решения задачи связанности и множества других задач обработки графов. Стратегия поиска в глубину такова: после исследования состояния идти «вглубь», пока это возможно (есть непройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной.

Алгоритм  поиска в глубину использует четыре цвета. Каждая из вершин вначале белая. Будучи обнаруженной, она становится темно серой; затем когда она будет полностью обработана, то есть когда список смежных с ней вершин будет просмотрен, мы красим ее в черный цвет.

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

Схема алгоритма:

1. Из множества всех белых вершин выберем любую вершину, обозначим её v1.
2. Выполняем для нее процедуру DFS(v1).
3. Перекрашиваем ее в черный цвет.
4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

     Процедура DFS (параметр — вершина)

1. Перекрашиваем вершину u в серый цвет.
2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).
2. Окрашиваем w в черный цвет.

Возможна  реализация этого алгоритма с  использованием явно заданного стека магазинного типа, хранящего вершины графа. Применение правила LIFO (Last In First Out — последним пришел, первым обслужен), которое характеризует работу стека магазинного типа, соответствует исследованию соседних коридоров в лабиринте: из всех еще не исследованных коридоров выбирается последний из тех, с которым мы столкнулись.

 

Алгоритм поиска в  ширину

Замена стека, используемого в обходе в глубину  очередью FIFO (First In First Out — первым пришел, первым обнаружен) приводит к другому классическому алгоритму — к алгоритму поиска в ширину. Алгоритм поиска в ширину используется для решения других задач обработки графов, связанных с нахождением кратчайших путей. Поиск в ширину — один из базисных алгоритмов, составляющий основу многих других. Например, алгоритм Дейкстры поиска кратчайших путей и алгоритм Прима поиска минимального покрывающего дерева могут рассматриваться как обобщения поиска в ширину. Алгоритм поиска в ширину перечисляет все достижения из начальной вершины (вершины в порядке возрастания от начальной). Словом мы идем «вширь», а не «вглубь» (сначала просматривая все соседние вершины, затем соседей соседей и т. д.)

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

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

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

Схема алгоритма:

1. Из множества всех белых вершин выберем начальную вершину, обозначим её v1. (она становится открытой)
2. Выбираем вершину v, которая является открытой.
3. Делаем вершину v активной.
4. Выполняем для нее процедуру BFS(v).
5. Перекрашиваем ее в черный цвет. (она становится не активной и закрытой)
6. Повторяем шаги 2-4 до тех пор, пока множество открытых вершин не пусто.

     Процедура BFS (параметр — вершина)

1. Перекрашиваем вершину u в серый цвет.
2. Всякую вершину w, смежную с вершиной u, окрашиваем в серый цвет (она становится открытой), причем вершину w1, которую мы посетили первой, делаем активной.
3. Выполняем процедуру BFS(w1)

Поиск в ширину строит дерево поиска в ширину, корнем которого является исходная вершина. Если в процессе сканирования списка смежности уже открытой вершины u открывается белая вершина v, то вершина y и ребро (u,v) добавляются в дерево, при этом, в дереве поиска в ширину u - родитель v.

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с  меткой 1, затем с меткой 2 и т. д.

 

 

 

Практическое применение алгоритмов решения задачи

 

Данные алгоритмы могут найти своё применение в программах для транспортных и коммуникационных сетей, таких как: железнодорожной транспортной сети, где вершины - станции,

связи – дороги, таксомоторная  сеть: вершины – места стоянки  автомобилей, связи – пути подъезда; перемещение потока вещества по системе  труб в определенный пункт назначения и т.д.

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

 

Остовное дерево наименьшего веса. Задача Штейнера.

Пусть дан  связный, неориентированный граф с  весами на ребрах G(V, E), в котором V — множество вершин (терминалов), а E — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения). Задача поиска остовного дерева наименьшего веса  графа G состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

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

w(T) = ∑(u,v)∈T w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом.

 

Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.

 

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

Однако эффективных алгоритмов, дающих точное решение задачи Штейнера, не существует. Даже лучшие из алгоритмов, выполняющиеся на самых быстродействующих компьютерах, не в состоянии дать решение для большого множества заданных точек за реально приемлемое время. Более того, задача Штейнера принадлежит к классу задач, для которых, по мнению многих современных исследователей, эффективные алгоритмы, по-видимому, так никогда и не будут найдены. Несмотря на то, что формулировка этой задачи очень проста, её решения трудно поддаются анализу. Крошечное изменение геометрии задачи, кажущееся несущественным, может коренным образом изменить кратчайшую сеть, являющуюся её решением. Однако, часто для решения задача Штейнера используются алгоритмы поиска остовного дерева наименьшего веса, не допускающие введение точек, отличных от терминальных. Поэтому они находят лишь некоторые приближения точного решения. Наиболее известные алгоритмы: алгоритм Краскала, алгоритм Прима.