0. ВВЕДЕНИЕ И ПОСТАНОВКА ЗАДАЧИ
0.1 Введение
0.2 Постановка задачи и структура работы 4
1. РАНДОМИЗИРОВАННЫЙ АЛГОРИТМ НАХОЖДЕНИЯ
МИНИМАЛЬНОГО РАЗРЕЗА В ГРАФЕ 5
1.1 Описание алгоритма 5
1.2 Теоретическое обоснование алгоритма 8
2. РЕАЛИЗАЦИЯ АЛГОРИТМА НА РАЗЛИЧНЫХ ГРАФАХ 12
2.1 Реализация для сгенерированного случайным образом графа 12
2.2 Реализация для графа, построенного на реальных данных 19
2.2.1 Организация реальных данных 19
2.2.2 Считывание данных 25
2.2.3 Визуализация 30
2.2.4 Особенности реализации алгоритма на реальных данных 37
3. ПРИМЕНЕНИЕ АЛГОРИТМА К РЕАЛЬНЫМ ДАННЫМ 41
3.1 Применение алгоритма на графе небольшой размерности
сгенерированном случайным образом 41
3.2 Применение алгоритма на графе, построенном на реальных данных, не
учитывая кратность ребер 49
3.2 Применение алгоритма на графе, построенном на реальных данных, учитывая кратность ребер 59
3.4 Анализ полученных результатов 67
ЗАКЛЮЧЕНИЕ 68
СПИСОК ЛИТЕРАТУРЫ 69
Приложение 70
На сегодняшний день существует множество проблем, которые можно свести к задаче о нахождении минимального разреза в графе. Минимальному разрезу при моделировании некоторых систем принадлежит важная роль.
Если каждому разрезу поставить в соответствие некоторое число, например количество содержащихся в разрезе элементов, то может быть выделено подмножество разрезов, содержащее минимальное число элементов, т.е. подмножество минимальных разрезов. Они являются важными для практики и интересными для исследования с теоретической точки зрения.
В области получения информации, для примера, минимальные разрезы используются при решении задачи выделения совокупности документов, отвечающих теме запроса. Минимальный разрез и близкие к нему разрезы соответствуют группе документов, которые имеют мало ссылок между собой.
Необходимость решения задачи о минимальном разрезе возникает и при разработке компиляторов для языков параллельного программирования. В графе для этой программы вершины будут означать программные операции, а ребра - потоки данных между программными операциями.
Минимальные разрезы могут быть использованы и в транспортных сетях. Вершинами будут узловые точки, а ребрами - дороги их соединяющие. Как раз о таком использовании минимальных разрезов будет идти речь. Однако это далеко не весь перечень.
В ходе работы был разобран и реализован рандомизированный алгоритм для отыскания минимального разреза, который в качестве начальных данных использует как сгенерированный случайным образом граф, так и граф содержащий информацию о карте дорог части города Казани.
Разработан интерфейс программы и визуализация графа.
Получен набор минимальных разрезов, несущий информацию об узких местах выбранной карты.
Однако, при размерностях графа сопоставимых с размерностью города, имеет смысл работать над улучшением реализации алгоритма, для получения более быстрых результатов.
Работу целесообразно продолжить в этом направлении.
