Теория графов - Курсовая работа

Задача отыскания на графе (как ориентированном, так и неориентированном) кратчайшего пути имеет многочисленные практические приложения. Самыми знаменитыми задачами в теории графов являются: задача о Кенигсбергских мостах, задача о трех домах и трех колодцах, задача о четырех красках. В настоящее время довольно быстро развивается теория графов, которая за последние десять - двадцать лет вступила в новый период интенсивных разработок. Повлияло на этот процесс запросы новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии и многое другое. В данной работе я постараюсь раскрыть понятие графа, описать некоторые определения, алгоритмы решения задач, а также уделить особое внимание задачам коммивояжера, решить их как математически, так и программно.Обычно ее относят к топологии (потому, что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ”Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Рассмотрев эту задачу, в 1736 году Эйлер доказал, что это невозможно, причем он рассмотрел более общую задачу: какие местности, разделенные рукавами рек и соединенные мостами, возможно обойти, побывав на каждом мосту ровно один раз, а какие невозможно.В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным. Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаные линии, состоящие из отрезков прямых. Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скорость выполнения операций над графами. Если в клетке i, j (i - строка, j - столбец) установлено значение пусто (как правило, это очень большая величина или величина, которой заведомо не может равняться вес ребра), то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Е сопоставимо V2 (где Е - количество дуг), этот способ хранения графа наиболее выгоден, т.к. его очень просто реализовывать и память будет заполнена "нужными" значениями. Но если это условие не выполняется, например, вершин до 10000 и ребер до 1000, то нам понадобиться ?2 * 100000000 / 10242 Мбайт памяти (по 2 байта на ячейку), что примерно равно 190 Мбайт, памяти.Задача коммивояжера (коммивояжер - разъездной сбытовой посредник) - одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешевый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжера (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжера (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжера .Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление). Определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину .Коммивояжер хочет объехать N городов и затем вернуться в начальный город, расстояния между которыми заданы.

Содержание

Введение

1. Теоретическая часть

1.1 История теории графов

1.2 Основные термины теории графов

1.3 Представление графов в ЭВМ

1.4 Задача коммивояжера

1.5 Метод ветвей и границ

2. Постановка задачи

3. Решение задачи аналитическим методом

4. Создание приложения для решения задачи

4.1 Тестирование программы

4.2 Руководство пользователя

Заключение

Список использованных источников