Теория графов

Размещено на http://www.allbest.ru

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

Б. Дизраэли

граф смежность путь алгоритм

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

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

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

В строгом определении графом называется такая пара множеств G=(V,E), где V (множество вершин графа) есть подмножество любого счётного множества, а E (множество ребер графа, или множество неупорядоченных и упорядоченных пар вершин) -- подмножество VЧV. На рисунке слева приведен пример графа с шестью вершинами и семью ребрами.

Теперь сформулируем основные понятия, которыми мы будем «оперировать» в данном пособии.

Граф может быть ориентированным и неориентированным. В ориентированном графе пути (дуги) имеют направление, а в неориентированном - не имеют. Все приведенные выше примеры графов - неориентированные графы. Неориентированное ребро можно представить как две разнонаправленные дуги между двумя вершинами. Пути в неориентированном графе называются рёбрами.

Путь в графе или орграфе - это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины A в вершину B начинается в A и проходит по набору ребер до тех пор, пока не будет достигнута вершина B.

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

Взвешенным называется такой граф, для каждого ребра (дуги) которого определена некоторая функция. А эта функция называется весовой. Иначе говоря, к каждому ребру «привязан» вес - фиксированное число или результат какой-то функции. Чаще всего встречается первый вариант.

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

Петлей называется дуга, ведущая из вершины в нее же.

Рассмотрим пример ориентированного взвешенного графа.

На рисунке точками обозначены вершины графа, стрелками - дуги, чёрные числа - номера вершин графа, а красные - веса дуг. Вес дуги можно представить также как стоимость. Т.е. например: дан граф, нужно дойти от вершины i до вершины j, заплатив минимальное количество денег или потратив наименьшее количество времени. Пусть в нашем графе, который представлен на рисунке, нам нужно пройти из вершины 5 в вершину 2, а вес дуг - стоимость прохода по данному ребру (или время прохода по нему). В данном примере очевидно, что выгоднее пройти через вершину 1 и только потом прийти в вершину 2, так мы заплатим всего 4 единицы денег, иначе, если пойти напрямую, мы заплатим целых 7 единиц.

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

Вот мы и разобрались, что такое граф. На рисунке всё смотрится красиво, все задачи вроде бы решаются легко... Но! А если граф будет большим, например на 1000 вершин? Да, такой граф на бумажке рисовать очень долго и нудно... Пускай лучше всё это делает за нас компьютер! Так давайте научим его этому! Но перед этим стоит ознакомиться с приложением данного пособия, в котором говориться о времени работы различных алгоритмов. Эти знания оказываются очень полезными при решении задач с ограничениями по времени. С каждым алгоритмом в дальнейшем мы будем описывать время его работы.

Глава1. Представление графа

Итак, разобравшись, что такое граф, приступим к «обучению» компьютера работы с ним. От того, как хранить граф в той или иной задаче очень много зависит... После того, как придумано полное решение, но, написав его, получаешь только половину баллов, задумываешься, а правильно ли храниться граф?

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

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

Один из самых распространённых способов хранения графа - матрица смежности. Она представляет собой двумерный массив. Если в клетке i, j (i - строка, j - столбец) установлено значение пусто (как правило, это очень большая величина или величина, которой заведомо не может равняться вес ребра), то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Иначе дуга есть. Если она есть, то в соответствующую ячейку записывают ее вес. Если граф не взвешенный, то вес дуги считается равным единице. Составим матрицу смежности для нашего графа:

Если нам дан неориентированный граф, то ребро можно заменить двумя дугами, т.е. если у нас есть ребро (1,3), то мы можем заменить его на дуги (1,3) и (3,1) - так мы сможем пройти в любом направлении в любое время.

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

Для представления графа матрицей смежности нужно V² (где V - количество вершин) ячеек. Если граф почти полный, т.е. Е сопоставимо V² (где Е - количество дуг), этот способ хранения графа наиболее выгоден, т.к. его очень просто реализовывать и память будет заполнена "нужными" значениями.

Но если это условие не выполняется, например, вершин до 10000 и ребер до 1000, то нам понадобиться ?2 * 100000000 / 1024² Мбайт памяти (по 2 байта на ячейку), что примерно равно 190 Мбайт, памяти. А на олимпиадах, как правило, ограничении на ее использование составляет 64 Мбайт. Значит, этот метод не годиться.

Кроме большого количества требуемой памяти и медленной работы на разреженных графах (графах, у которых E << V²) у матрицы смежности есть ещё один важный недостаток. Иногда в задачах нужно выводить не номера вершин, а номера дуг (рёбер) на вводе. Хранить эти номера матрица смежности «не умеет». Нужно реализовывать восстановление номера дуги (ребра) как-то иначе, а это совсем неудобно.

Приведем расчеты временной сложности хранения графа матрицей смежности:

Список дуг

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

Приведем расчеты временной сложности хранения графа списком дуг:

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

Если в предыдущих представлениях одно ребро мы заменяли двумя дугами, то список дуг может хранить или дуги или рёбра (в зависимости от реализации). Это довольно удобно и может требовать в 2 раза меньше памяти.

Списки смежных вершин

Данный метод хранения графа наиболее часто используется при решении задач с большими ограничениями по памяти и по времени (например, 2 сек и 64 Мбайт памяти на ограничения V< 10000, E < 1000 - случай разреженного графа). Его суть заключается в том, чтобы для каждой вершины Т хранить номера вершин, в которые можно попасть из Т, и вес соответствующих ребер (дуг). Для этого необходимо реализовать такую структуру данных, как список. В языках высокого уровня, таких, как С++ и Java, они уже реализованы. Далее нужно реализовать структуру данных (struct в C++ и record в Pascal) - запись с полями «вершина» и «вес». После этого заводим массив списков с V ячейками (количество вершин) и к каждой ячейке «привязываем» список созданного нами типа (структуры).

Приведем листинг на языке С++:

После этого каждый элемент mass[i] является списком типа ToLongth динамической длины (в зависимости от кол-ва ребер, исходящих из данной вершины).

Эта схема поможет воспринять метод:

где «….» - это длина списка, количество вершин, исходящих из i-ой вершины графа.

Для данного примера массив списков будет выглядеть так (в скобках указаны элементы структуры):

Приведем расчеты временной сложности хранения графа списками смежных вершин:

Времена у всех операций, вроде бы, такие же, как и у списка рёбер. Однако, большинство из них реально намного меньше. Например, проверка смежности вершин x и y и перечисление всех вершин смежных с x в списке рёбер гарантированно будет выполнятся О(Е) операций, т.к. нам обязательно нужно пробежать весь список, а в списке смежности мы бежим только по вершинам, смежным с х.

Кроме того, мы экономим колоссальное количество памяти. Подсчитаем примерный объем для максимального ограничения: 2 * (10000 * 1000) / 1024² ? 19 Мбайт.

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

Итак, мы рассмотрели лишь некоторые методы представления графа в памяти компьютера. Существует ещё много способов представления графа в памяти, как статических, так и динамических. Однако не стоит распыляться на все сразу, так как они мало чем могут помочь на олимпиаде по информатике. Все методы, рассмотренные выше, хороши для решения школьных олимпиадных задач, не требуют долгой и сложной реализации, поэтому нужно иметь их на вооружении. Можно сделать выводы, что наиболее оптимальной структурой является массив списков, так как он экономит память и не тратит драгоценное время. Но чтобы им смело пользоваться, надо много потренироваться в его реализации. В главе «Разборы задач» многие решения хранят графы в виде списков смежных вершин. Однако в теоретической чести мы будем разбирать алгоритмы на примерах реализации графа в виде матрицы смежности. Это позволяет проще понимать суть логики алгоритма.

Глава 2. Обходы и поиск пути в невзвешенном графе

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

Давайте переведем эту легенду на язык графов. Лабиринтом у нас будет связным графом, в котором комнаты будут вершинами, а коридоры - ребрами. Очевидно, что этот граф невзвешенный и неориентированный. Пусть Тезей начал свой путь с вершины (комнаты) 1. Чтобы найти чудовище, ему необходимо обойти (в худшем случае) все комнаты, а чтобы вернуться назад, надо знать путь от данной комнаты до комнаты 1.

На языке графов эти задачи сводятся к следующим:

1) обойти все вершины графа;

2) найти путь между двумя вершинами.

Эти задачи решаются с помощью обходов.

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

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

Глава 3. Поиск кратчайшего пути во взвешенном графе

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

В общем виде задачу можно сформулировать так:

Дан простой взвешенный граф G(V, E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

На бытовом уровне можно переформулировать ее таким образом:

Вариант 1. Дана сеть автомобильных дорог, соединяющих города Новосибирской области. Найти кратчайшие пути от Новосибирска до каждого города области (если двигаться можно только по дорогам).

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

В данном пособии будут рассматриваться алгоритмы Дейкстры и Флойда-Уоршелла. Это основные алгоритмы для решения данной задачи. Существуют ещё методы, но мы их опустим, так как они либо имеют более плохую асимптотику, либо более трудны в реализации при одинаковой скорости работы. Вообще говоря, для решения олимпиадных задач это базовые алгоритмы, к которым, как правило, можно свести проблему.

Итак, нам необходимо найти кратчайший путь, то есть путь с минимальным весом, между двумя вершинами графа. Эта задача разбивается на 2 подзадачи: нахождение величины пути и вывода самого пути. Пусть нам уже дана матрица кратчайших путей D[1..n], где D[i] храниться кратчайшее расстояние от стартовой вершины (пусть для определенности это вершина 1) до вершины с номером i, причем D[1] = 0. Для двух вершин a и b существует такая вершина c (без ограничения общности скажем, что с смежна с b), что D[b] = D[c] + mass[c][u], где mass - матрица смежности. То есть, при прохождении по кратчайшему пути мы из c попадем в b. Иначе говоря, с является «предком» b. Если создать массив «предков», в котором для каждой вершины будет храниться ее предок, то мы без труда выведем путь от стартовой вершины до любой другой.

Вот рекурсивный пример такого вывода на С++ (par - массив предков):

void Out(int v)

{

if (v == s)

{

cout << v + 1 << " ";

}

else

{

Out(par[v]);

cout << v + 1 << " ";

}

}

Для вывода пути необходимо запустить процедуру с номером последней вершины (финиша).

Теперь самое время научиться решать первую задачу - находить эти кратчайшие пути. Рассмотрим два алгоритма: Дейкстры и Флойда-Уоршелла.

Приложение. Время работы программы

К большинству олимпиадных задач ограничения (по времени, по памяти) жюри подбирает по принципу «как можно больше». То есть чтобы любые разумные реализации правильного решения проходили, а всё остальное -- нет. Когда встречается задача с маленькими ограничениями (например, до 10), это означает, что либо автор намеренно сбивает Вас с правильного пути, либо действительно эта задача решается каким-то (оптимизированным) перебором. Ну а если ограничения на основную входную величину, определяющую (как правило) будущий алгоритм, составляет порядка 109, то пройдет только однопроходной алгоритм.

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

Пусть n - входное число, определяющее скорость будущего решения. Тогда скорость работы алгоритма может быть пропорциональна какой-либо функции от n. Например, корень из , log2n, n2, 2n и т.д. Итак, определимся сразу, какой алгоритм будем выбирать исходя из входных данных так, чтобы количество операций проходило по временным ограничениям (как правило, на олимпиадах это 2 секунды):

1) для n > 1000000000 проходит решение за n операций впритык;

2) 1000000 < n < 10000000 обычно log2n, хотя бывает и (log2n) 2;

3) для 100000 < n < 500000 обычно n*log2n;

4) n < 5000 - это n2;

5) порядка 100-200 n3;

6) менее 20-24 - это 2n.

Временную сложность процесса будем обозначать O(f), f - некоторая функция от n (например, одна из вышеописанных).

Для (1) характерны так называемые однопроходные алгоритмы, которые обрабатывают информацию и решают задачу одновременно при считывании данных, а также линейные алгоритмы обходов графа в ширину и глубину; для (2) можно привести пример алгоритма бинарного поиска элемента в отсортированном массиве; для (3) - сортировка массива «кучей» (heap sort); (4) - с такой асимптотикой работают очень многие алгоритмы, например, алгоритм Дейсктры; для (5) - алгоритм Флойда; для (6) - переборные алгоритмы (комбинаторика).

Источники информации

1. Кормен Т., Лейзерсон Ч., Ривест Р, «Алгоритмы: построение и анализ», M.: МЦНМО, 1999, (Популярнейший американский учебник по программированию. Кладезь всего-всего.)

2. С. Окулов, «Программирование в алгоритмах», Москва, Бином. Лаборатория базовых знаний, 2004 г.

3. В.М. Кирюхин «Информатика. Всероссийские олимпиады», Москва, «Просвещение», 2008 г.

4. ru.wikipedia.org

5. www.olympiads.ru

Размещено на Allbest.ru