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

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

Рубрика Математика
Вид курсовая работа
Язык русский
Дата добавления 19.09.2011
Размер файла 495,4 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕСИОНАЛЬНОГО ОБРАЗОВАНИЯ

"ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ"

ИНСТИТУТ НЕФТИ И ГАЗА

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Курсовая работа

по дисциплине "Дискретная математика"

на тему "Теория графов"

Выполнил: студент группы

Проверил: ст.преподаватель

Гапанович И.В.

Тюмень 2009

Содержание

  • Введение
    • 1. Постановка задачи
    • 2. Описание алгоритма решения задачи
    • 3. Ручной просчёт задачи
    • 4. Тестирование программы
  • Закючение
  • Список литературы
  • Приложение

Введение

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

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

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

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

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, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма.

Вторая метка (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.

2. Для всех vГp с временными метками выполним: если l*(v)>l*(p)+l(p,v), то l*(v)=l*(p)+l(p,v) и (v) =р. Иначе l*(v) и (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, поэтому положим (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.

5. Найдем минимальный путь из s в t, используя метки (v): П = s…(t)t.

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

2. Описание алгоритма решения задачи

Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.

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

Описание использованных программных средств

Переменная

Тип

Описание

n

int

Количество точек вершин графа

i,j

int

Счётчики

p

int

Номер кратчайшего пути и наименьшей длины пути

xn

int

Номер начальной точки (вершины)

xk

int

Номер конечной точки (вершины)

flag[11]

int

Массив, i-й элемент которого имеет значение 0, когда i-й путь и расстояние временные, и принимает значение 1, когда i-й путь и расстояние становятся постоянными

c[11][11]

word (unsigned int)

Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами)

Замечание:

1. с[i][i]=

2. c[i][j]=c[j][i]

s[80]

char

Строчная переменная, которая содержит промежуточные значения пути

path[80][11]

char

Массив строк, который содержит пути

Замечание:

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

l[11]

word (unsigned int)

Массив, который содержит длины путей (path)

Замечание: После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит длину кратчайшего пути.

Кроме стандартных функций из библиотек iostream.h, string.h, stdio.h, conio.h были использованы также следующие функции.

· word minim(word x, word y) - функция, которая возвращает минимальное из x и y.

· int min(int n) - функция, которая возвращает номер элемента массива l[i] минимальной "неотмеченной" длиной пути(flag[i]=0).

3. Ручной просчёт задачи

Пусть дан граф, заданный матрицей весов:

Получаем, что путь из точки А в точку В: А, F, а длина пути равна 4.

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

Заключение

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

Цель данной работы достигнута: алгоритм и программа решения задачи составлен, правильность работы программы проверена.

Список литературы

1. Гапанович В.С., Гапанович И.В. Дискретная математика: Учебное пособие. Тюмень: ТюмГНГУ, 2002. - 187 с.

2. Дискретная математика для программистов / Ф.А. Новиков - СПб: Питер, 2000. - 304 с.

3. Дискретная математика. Алгоритмы и программы: Учеб. пособие/Б.Н. Иванов. - М.: Лаборатория Базовых Знаний, 2003. - 288 с.

4. Кормен Алгоритмы: построение и анализ / 1990.

Приложение

#include<iostream.h>

#include<string.h>

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define word unsigned int

int i, j, n, p, xn, xk;

int flag[11];

word c[11][11], l[11];

char s[80], path[80][11];

int min(int n)

{

int i, result;

for(i=0;i<n;i++)

if(!(flag[i])) result=i;

for(i=0;i<n;i++)

if((l[result]>l[i])&&(!flag[i])) result=i;

return result;

}

word minim(word x, word y)

{

if(x<y) return x;

return y;

}

void main()

{

cout<<"Vvedite kolichestvo tochek: ";

cin>>n;

for(i=0;i<n;i++)

for(j=0;j<n;j++) c[i][j]=0;

for(i=0;i<n;i++)

for(j=i+1;j<n;j++)

{

cout<<"Vvedite rasstoyanie ot x"<<i+1<<" do x"<<j+1<<": ";

cin>>c[i][j];

}

cout<<" ";

for(i=0;i<n;i++) cout<<" X"<<i+1;

cout<<endl<<endl;

for(i=0;i<n;i++)

{

printf("X%d",i+1);

for(j=0;j<n;j++)

{

printf("%6d",c[i][j]);

c[j][i]=c[i][j];

}

printf("\n\n");

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(c[i][j]==0) c[i][j]=65535; //бесконечность

cout<<"Vvedite nachalnuy tochku: ";

cin>>xn;

cout<<"Vvedite konechnuy tochku: ";

cin>>xk;

xk--;

xn--;

if(xn==xk)

{

cout<<"Nachalnaya I konechnaya tochki sovpadayt."<<endl;

getch();

return;

}

for(i=0;i<n;i++)

{

flag[i]=0;

l[i]=65535;

}

l[xn]=0;

flag[xn]=1;

p=xn;

itoa(xn+1,s,10);

for(i=1;i<=n;i++)

{

strcpy(path[i],"X");

strcat(path[i],s);

}

do

{

for(i=0;i<n;i++)

if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))

{

if(l[i]>l[p]+c[p][i])

{

itoa(i+1,s,10);

strcpy(path[i+1],path[p+1]);

strcat(path[i+1],"-X");

strcat(path[i+1],s);

}

l[i]=minim(l[i],l[p]+c[p][i]);

}

p=min(n);

flag[p]=1;

}

while(p!=xk);

if(l[p]!=65535)

{

cout<<"Put: "<<path[p+1]<<endl;

cout<<"Dlina puti: "<<l[p]<<endl;

}

else

cout<<"takogo puti ne syshestvuet!"<<endl;

getch();

}

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


Подобные документы

  • Минимальное остовное дерево связного взвешенного графа и его нахождение с помощью алгоритмов. Описание алгоритма Краскала, возможность строить дерево одновременно для нескольких компонент связности. Пример работы алгоритма Краскала, код программы.

    курсовая работа [192,5 K], добавлен 27.03.2011

  • Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.

    контрольная работа [466,3 K], добавлен 11.03.2011

  • Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.

    курсовая работа [118,7 K], добавлен 30.04.2011

  • Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.

    курсовая работа [625,4 K], добавлен 30.09.2014

  • Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.

    курсовая работа [362,9 K], добавлен 24.11.2010

  • История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.

    курсовая работа [636,2 K], добавлен 20.12.2015

  • Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.

    контрольная работа [66,3 K], добавлен 06.04.2012

  • Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".

    курсовая работа [2,4 M], добавлен 08.10.2014

  • Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.

    курсовая работа [1,0 M], добавлен 26.09.2013

  • Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.

    курсовая работа [225,0 K], добавлен 30.04.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.