Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕСИОНАЛЬНОГО ОБРАЗОВАНИЯ
"ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ"
ИНСТИТУТ НЕФТИ И ГАЗА
КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
Курсовая работа
по дисциплине "Дискретная математика"
на тему "Теория графов"
Выполнил: студент группы
Проверил: ст.преподаватель
Гапанович И.В.
Тюмень 2009
Содержание
Введение
1. Постановка задачи
. Описание алгоритма решения задачи
3. Ручной просчёт задачи
. Тестирование программы
Закючение
Список литературы
Приложение
Введение
Существует большое количество практических задач, рассмотрение которых сводится к изучению совокупности объектов, существенные свойства которых описываются связями между ними. Интерес могут представлять различные экономические связи, связи и отношения между людьми, событиями, состояниями, и вообще, между любыми объектами.
В подобных случаях удобно рассматривать объекты точками, называя их вершинами, а связи между ними - линиями (произвольной конфигурации), называя их ребрами. Полученная при этом конфигурация называется графом.
Цель данной работы: рассмотреть решение задачи: "Задана система двусторонних дорог, причем для любой пары городов можно указать соединяющий их путь. Найти такой город, для которого сумма расстояний до остальных городов минимальна", составить алгоритм решения задачи, написать программу и проверить правильность работы программы.
Работа содержит следующие пункты: постановка задачи, описание алгоритма решения задачи, ручной подсчет решения задачи, тестирование программы, листинг программы.
1.Постановка задачи
Задача. Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Дейкстры.
Решение задачи будет произведено по алгоритму Дейкстры.
Пусть в орграфе D из вершины v в вершину w, где v w, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.
Назовем орграф D = (V,X) нагруженным, если на множестве дуг X определена некоторая функция l : X R, которую часто называют весовой функцией. Значение l(x) будем называть длиной дуги x. Предположим, что l(x) 0. Длиной пути П в нагруженном орграфе будем называть величину l(П), равную сумме длин дуг, входящих в П, при этом каждая дуга учитывается столько раз, сколько она входит в данный путь.
Нагруженный орграф можно задать с помощью матрицы весов С(D) = {cij}nxn с элементами
Рассмотрим алгоритм Дейкстры, который позволяет определить минимальный путь в орграфе между двумя заданными вершинами при условии, что этот путь существует.
Пусть s - начальная вершина, t - конечная вершина. На каждой итерации любая вершина v имеет метку l*(v), которая может быть постоянной или временной. Постоянная метка l*(v) - это длина кратчайшего пути от s к v, временная метка l(v) - это вес кратчайшего пути из s в v, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма.
Вторая метка Q(v) - это вершина, из которой вершина v получила свою метку.
Алгоритм Дейкстры
Данные: матрица весов С(D) орграфа D, начальная вершина s.
Результат: расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v V, а также последовательность вершин, определяющая кратчайший путь из s в v .
1.Положим l*(s) = 0 и будем считать эту метку постоянной. Для всех v V, v s, положим l*(v) = и будем считать эти метки временными. Положим p = s.
.Для всех vГp с временными метками выполним: если l*(v)>l*(p)+l(p,v), то l*(v)=l*(p)+l(p,v) и Q(v) =р. Иначе l*(v) и Q(v) не менять, т.е. l*(v) = min (l*(t), l*(p)+cpv). (Идея состоит в следующем: пусть p - вершина, получившая постоянную метку l*(p) на предыдущей итерации. Просматриваем все вершины vГp, имеющие временные метки. Метка l*(v) вершины vГp заменяется на l*(p)+l(p,v), если оказывается, что ее метка l*(v)>l*(p)+l(p,v). В этом случае говорим, что вершина v получила свою метку из вершины p, поэтому положим Q(v) = p. С помощью этих дополнительных меток будем потом восстанавливать сам путь. Если l*(v) l*(p)+cpv, то метки остаются прежними. путь вершина граф схема
3.Пусть V* - множество вершин с временными метками. Найдем вершину v* такую, что l*(v*) = min l*(v), v ?V*. Считать метку l*(v*) постоянной для вершины v*.
4.Положим p = v*. Если p = t, то перейдем к п.5 ( l*(t) - длина минимального пути ). Иначе перейдем к п.2.
.Найдем минимальный путь из s в t, используя метки Q(v): П = s…Q(t)t.
Заметим, что, если продолжить работу алгоритма Дейкстры до тех пор, пока все вершины не получат постоянные метки, то мы получим расстояния от начальной вершины s до произвольной вершины графа.
. Описание алгоритма решения задачи
Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.
При запуске программы на экран выводится запрос о вводе весов рёбер исследуемого графа. Данные, введённые пользователем, отображаются в виде матрицы смежности, в которой не существующие рёбра обозначаются нулями. После указанным рёбрам присваивается значение 65535, которое принимается за бесконечность. Следующим этапом выполнения программы является запрос о вводе ном