Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Поиск оптимального пути в ненагруженном орграфе

Название: Поиск оптимального пути в ненагруженном орграфе
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 14:36:53 24 апреля 2011 Похожие работы
Просмотров: 295 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Содержание

1. Введение

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

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

б) Понятия смежности, инцидентности, степени

в) Маршруты и пути

г) Матрицы смежности и инцедентности

3. Алгоритм http://hghltd.yandex.com/yandbtm?url=http%3A//www.fos.ru/matemat/9228.html&text=%CF%EE%E8%F1%EA+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE+%EF%F3%F2%E8+%E2+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC+%E3%F0%E0%F4%E5+%2C+%F0%E5%F4%E5%F0%E0%F2&reqtext=%28%CF%EE%E8%F1%EA%3A%3A783+%26+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE%3A%3A22975+%26%26/%28-3+3%29+%EF%F3%F2%E8%3A%3A5309+%26+%E2%3A%3A0+%26+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC%3A%3A42191+%26+%E3%F0%E0%F4%E5%3A%3A31618+%26%26/%28-3+3%29+%F0%E5%F4%E5%F0%E0%F2%3A%3A6724%29//6&dsn=530&d=2003257 - YANDEX_28поиска минимального пути из в в http://hghltd.yandex.com/yandbtm?url=http%3A//www.fos.ru/matemat/9228.html&text=%CF%EE%E8%F1%EA+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE+%EF%F3%F2%E8+%E2+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC+%E3%F0%E0%F4%E5+%2C+%F0%E5%F4%E5%F0%E0%F2&reqtext=%28%CF%EE%E8%F1%EA%3A%3A783+%26+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE%3A%3A22975+%26%26/%28-3+3%29+%EF%F3%F2%E8%3A%3A5309+%26+%E2%3A%3A0+%26+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC%3A%3A42191+%26+%E3%F0%E0%F4%E5%3A%3A31618+%26%26/%28-3+3%29+%F0%E5%F4%E5%F0%E0%F2%3A%3A6724%29//6&dsn=530&d=2003257 - YANDEX_31ориентированном орграфе (алгоритм фронта волны)

4. Листинг программы

5. Примеры выполнения программы

6. Использованная литература


Введение

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

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

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

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

Кратчайший путь рассматривается при помощи графов.

Цель курсовой работы:

Разработать программу поиска оптимального пути в ненагруженном ориентированном графе на любом языке программирования.


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

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

Теория графов как теоретическая дисциплина может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие физические, технические, экономические, биологические, социальные и другие системы. Например, графом, изображенным на рис. 1, в котором точки − вершины графа − города, линии, соединяющие вершины − ребра − дороги, соединяющие города, описывается так называемая транспортная задача (задача нахождения кратчайшего пути из одного города- пункта в другой).

Рис. 1.

Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения V×V, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V,X). Неориентированным графом G называется совокупность множества V и множества ребер − неупорядоченных пар элементов, каждый из которых принадлежит множеству V.

Одинаковые пары - параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Рис.2.

Например, кратность ребра {v1,v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3,v4} − трем.

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

Граф − мультиграф, в котором ни одна пара не встречается более одного раза.

Граф называется ориентированным, если пары (v,w) являются упорядоченными.

Ребра ориентированного графа называются дугами.

Итак, используемые далее обозначения:

V – множество вершин;

X – множество ребер или дуг;

v (или vi)– вершина или номер вершины;

G, G0 - неориентированный граф;

D, D0 – ориентированный;

{v,w} − ребра неориентированного графа;

{v,v} – обозначение петли;

(v,w) − дуги в ориентированном графе;

v,w - вершины, x,y,z – дуги и ребра;

n(G), n(D) количество вершин графа;

m(G) - количество ребер, m(D) - количество дуг.

Примеры

1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},

X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.

Рис. 3.

2) Неориентированный граф G=(V, X), V={v1, v2, v3, v4, v5},

X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.

Рис. 4.

б) Понятия смежности, инцидентности, степени

Если x={v,w} - ребро, то v и w − концы ребер.

Если x=(v,w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x ).

Вершины v, w называются смежными, если {v,w}ÎX.

Степенью вершины v графа G называется число d (v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).

в) Маршруты и пути

Последовательность v1x1v2x2v3...xkvk+1, (где k³1, viÎV, i=1,...,k+1, xiÎX, j=1,...,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj,vj+1} (для ориентированного графа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

г) Матрицы смежности и инцидентности

Пусть D=(V,X) ориентированный граф, V={v1,...,vn}, X={x1,...,xm}.

Матрица смежности ориентированного графа D − квадратная матрица

A(D)=[aij] порядка n, где

Матрица инцидентности − матрица B(D)=[bij] порядка n´m, где


Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[aij] порядка n, где

.

Матрица инцидентности графа G называется матрица B(G)=[bij] порядка n´m, где

Алгоритм http://hghltd.yandex.com/yandbtm?url=http%3A//www.fos.ru/matemat/9228.html&text=%CF%EE%E8%F1%EA+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE+%EF%F3%F2%E8+%E2+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC+%E3%F0%E0%F4%E5+%2C+%F0%E5%F4%E5%F0%E0%F2&reqtext=%28%CF%EE%E8%F1%EA%3A%3A783+%26+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE%3A%3A22975+%26%26/%28-3+3%29+%EF%F3%F2%E8%3A%3A5309+%26+%E2%3A%3A0+%26+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC%3A%3A42191+%26+%E3%F0%E0%F4%E5%3A%3A31618+%26%26/%28-3+3%29+%F0%E5%F4%E5%F0%E0%F2%3A%3A6724%29//6&dsn=530&d=2003257 - YANDEX_28поиска минимального пути из в в http://hghltd.yandex.com/yandbtm?url=http%3A//www.fos.ru/matemat/9228.html&text=%CF%EE%E8%F1%EA+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE+%EF%F3%F2%E8+%E2+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC+%E3%F0%E0%F4%E5+%2C+%F0%E5%F4%E5%F0%E0%F2&reqtext=%28%CF%EE%E8%F1%EA%3A%3A783+%26+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE%3A%3A22975+%26%26/%28-3+3%29+%EF%F3%F2%E8%3A%3A5309+%26+%E2%3A%3A0+%26+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC%3A%3A42191+%26+%E3%F0%E0%F4%E5%3A%3A31618+%26%26/%28-3+3%29+%F0%E5%F4%E5%F0%E0%F2%3A%3A6724%29//6&dsn=530&d=2003257 - YANDEX_31ориентированном орграфе (алгоритм фронта волны)

1) Помечаем вершину индексом 0, затем помечаем вершины Î образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.

2) Если или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.

В противном случае продолжаем:

3) Если , то переходим к шагу 4.

В противном случае мы нашли минимальный путь из в и его длина равна k. Последовательность вершин

теория орграф матрица алгоритм

есть этот минимальный путь. Работа завершается.

4) Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем . Присваиваем k:=k+1 и переходим к 2).

Замечания

Множество называется фронтом волны kго уровня.

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

Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу http://hghltd.yandex.com/yandbtm?url=http%3A//www.fos.ru/matemat/9228.html&text=%CF%EE%E8%F1%EA+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE+%EF%F3%F2%E8+%E2+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC+%E3%F0%E0%F4%E5+%2C+%F0%E5%F4%E5%F0%E0%F2&reqtext=%28%CF%EE%E8%F1%EA%3A%3A783+%26+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE%3A%3A22975+%26%26/%28-3+3%29+%EF%F3%F2%E8%3A%3A5309+%26+%E2%3A%3A0+%26+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC%3A%3A42191+%26+%E3%F0%E0%F4%E5%3A%3A31618+%26%26/%28-3+3%29+%F0%E5%F4%E5%F0%E0%F2%3A%3A6724%29//6&dsn=530&d=2003257 - YANDEX_34 минимальных расстояний R(D)между его вершинами. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю (, i=1,..,n).

Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (, если ). Далее построчно заполняем матрицу следующим образом.

Рассматриваем первую строку, в которой есть единицы. Пусть это строка − i-тая и на пересечении с j-тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем j-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.


Листинг программы:

#include<stdio.h>

#include<iostream>

using namespace std;

int main()

{

int N=0,n=0,c=0,i=0,k=0;

cout<<" ----------------------------------------------"<<endl;

cout<<" |Poisk optimalnogo puti v nenagrujennom orgrafe|"<<endl;

cout<<" ----------------------------------------------"<<endl;

case1:

cout<<"Vvedite chislo vershin v orgrafe: ";

cin>>N;

if(N<=1)

{

cout<<"Kolichestvo vershin doljno bit'>1!!!"<<endl;

goto case1;

}

///МАТРИЦАсмежности::

cout<<"Zapolnite matricu smejnosti (esli puti net,vvedite 0; esli put' est',vvedite 1):";

float** A = new float*[N];

for(i;i<N;i++)

A[i] = new float[N];

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

for(int k=0;k<N;k++)

{

cout<<"V";

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

cout<<"->V";

printf("%d",k+1);

cout<<'=';

scanf("%f", &A[i][k]);

if((A[i][k]!=0)&&(A[i][k]!=1))

{

cout<<"Vvodite tol'ko 0 ili 1!"<<endl;

return 0;

}

if((i==k)&(A[i][k]==1))

{

cout<<"Na glavnoi diagonali doljni bit' nuli!"<<endl;

return 0;

}

}

////Откуда и куда?(Начальная и конечная вершина в графе!!)

case2:

cout<<"Vvedite nachalnuiu vershinu: ";

cin>>n;

if(n>N)

{

cout<<"Net takoi vershini!"<<endl;

goto case2;

}

if(n==0)

{

cout<<"Net takoi vershini!"<<endl;

goto case2;

}

case3:

cout<<"Vvedite konechnuyu vershinu: ";

cin>>c;

if(c>N)

{

cout<<"Net takoi vershini!"<<endl;

goto case3;

}

if(c==0)

{

cout<<"Net takoi vershini!"<<endl;

goto case3;

}

///Массив,где записывается число шагов

int h=1;

float*B= new float[N];

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

{

B[i]=0;

}

//В массиве B[N-1] ищем вершины,которые достжимы из начала пути

//т.е за один шаг

for(k=0;k<N;k++)

{

if(A[n-1][k]==1)

B[k]=1;

}

//Элементы фронта волны

while(h<50)

{

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

{

for(k=0;k<N;k++)

{

if((B[i]==h)&&(A[i][k]==1)&&(B[k]==0))

B[k]=h+1;

}

}

h++;

}

B[n-1]=0;

if(B[c-1]!=0)

{

///Выводнаэкрантаблицу

cout<<"\nTablica stoimosti minimalnogo puti:"<<endl;

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

{

printf("%f ",B[i]);

}

//Поискобратногопути

cout<<"\n\nOptimal'nii put'(v obratnom poryadke):\n"<<"V";

printf("%d",c);

h=c-1;

int b=B[c-1];

while(b>0)

{

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

if((A[i][h]==1)&&(B[i]==B[h]-1))

{

cout<<"V";

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

h=i;

b--;

}

}

cout<<"\n";

}

else

{

cout<<"\nPuti net!\n";

}

delete A,B;return 0;

}


Примеры выполнения программы:

1.

2.


3.


Использованная литература:

1. «Теория графов». Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика». Сост.: Н.И. Житникова, Г.И. Федорова, А.К. Галимов. - Уфа, 2005 -37 с.

2. Курс лекций по дискретной математике Житникова В.П.

3. «Самоучитель С++», Перевод с англ. –3 изд.. – СПб.: БХВ-Петербург, 2005 – 688 с.

4. «Дискретная математика для программистов», Ф.А.Новиков.

5. «Введение в дискретную математику», Яблонский.

6. «Курс дискретной математики», Неферов, Осипова.

7. «Информатика» Л.З.Шауцукова.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:04:42 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:31:38 29 ноября 2015

Работы, похожие на Курсовая работа: Поиск оптимального пути в ненагруженном орграфе

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150061)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru