Свойства гамильтоновых графов - Курсовая работа

Актуальность данной темы заключается в следующем: для решения оптимизационных и других задач строительства, нередко прибегают к формулировке поставленной задачи в виде каких-то хорошо известных математических задач: транспортная задача, задача поиска оптимального пути (задача коммивояжера) и другие. Сформулированную таким образом задачу решают, используя такие математические методы, как метод ветвей и границ. Переборные алгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решении каждой конкретной задачи существенным образом зависит от способа организации перебора. Рассмотреть известные способы решения задачи о коммивояжере.Пара (V,E), где E - произвольное подмножество множества V(2), называется простым графом (неориентированным графом). Элементы множества V называются вершинами графа, а элементы множества E - ребрами. Если |G|=n, |EG|=m, то граф называют (n, m)-графом. Говорят, что две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если e={u, v} - ребро, то вершины u и v называют его концами.1) Всякий незамкнутый (u, v)-маршрут, содержит в себе простую (u, v)-цепь. Вчастности, любая (u, v)-цепь, содержит в себе простую (u, v)-цепь. Причем, если (u, v)-маршрут содержит в себе вершину w (w?u и w?v), то в общем случае, простая (u, v)-цепь может не содержать в себе вершину w.Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам этот цикл также называется гамильтоновым. Слово «гамильтонов» в этих определениях связано с именем известного ирландского математика У. Если |G|=n?3 и для любой вершины v графа G выполняется неравенство deg v?n/2, то G - гамильтонов граф. Если , то в графе существует цикл длиной .Однако, известна изданная в 1832 году книга с названием «Коммивояжер - как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах - советы старого курьера» в которой описана проблема, но математический аппарат для ее решения не применяется. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал ее на математическом коллоквиуме в 1930 году так: «Мы называем проблемой посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, ее решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно.» Учитывая эти свойства, начиная со второй половины 20-го века, исследование задачи коммивояжера имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации. Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжера. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону и Селмеру Джонсону, которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для ее решения метод отсечений.Классическая постановка задачи о коммивояжере выглядит следующим образом: Имеется N городов, которые должен обойти коммивояжер по кратчайшему пути. При этом на его маршрут накладывается два ограничения: · маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение; · в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом, не побывав ни в одном городе дважды. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.Зачастую востребованы алгоритмы постепенно улучшающие некоторое текущее приближенное решение. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т. е. наилучшее из встретившихся решений. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. Сегодня этот алгоритм является популярным как среди практиков благодаря своей простоте, гибкости и эффективности, так и среди теоретиков, поскольку для данного алгоритма удается аналитически исследовать его свойства и доказать асимптотическую сходимость.Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующую последовательность действий: (1) Построение матрицы с исходными данными. (8) Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9. В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д.

План

Введение

1. Понятие Гамильтонова графа

1.1 Основные понятия теории графов

1.2 Свойства маршрутов, цепей и циклов

1.3 Понятие гамильтонова графа. Теорема Дирака

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

2.1 Историческая справка

2.2 Постановка задачи о коммивояжере

2.3 Методы решения задачи о Коммивояжере

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

Заключение

Список использованной литературы