Содержание
1. Введение
2. Теоретическая часть
а) Основные понятия теории графов
б) Понятия смежности, инцидентности, степени
в) Маршруты и пути
г) Матрицы смежности и инцедентности
3. Алгоритм 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поиска минимальногопути из /> в/> в 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
#include
using namespace std;
int main()
{
int N=0,n=0,c=0,i=0,k=0;
cout
cout
cout
case1:
cout
cin>>N;
if(N
{
cout1!!!»
goto case1;
}
///МАТРИЦАсмежности::
cout
float** A = new float*[N];
for(i;i
A[i] = new float[N];
for(i=0;i
for(int k=0;k
{
cout
printf("%d",i+1);
coutV";
printf("%d",k+1);
cout
scanf("%f", &A[i][k]);
if((A[i][k]!=0)&&(A[i][k]!=1))
{
cout
return 0;
}
if((i==k)&(A[i][k]==1))
{
cout
return0;
}
}
////Откудаи куда?(Начальная и конечная вершина в графе!!)
case2:
cout
cin>>n;
if(n>N)
{
cout
goto case2;
}
if(n==0)
{
cout
goto case2;
}
case3:
cout
cin>>c;
if(c>N)
{
cout
goto case3;
}
if(c==0)
{
cout
goto case3;
}
///Массив, гдезаписывается число шагов
int h=1;
float*B= new float[N];
for(i=0;i
{
B[i]=0;
}
//Вмассиве B[N-1] ищем вершины, которые достжимы из начала пути
//т.еза один шаг
for(k=0;k
{
if(A[n-1][k]==1)
B[k]=1;
}
//Элементыфронта волны
while(h
{
for(i=0;i
{
for(k=0;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
for(i=0;i
{
printf("%f ",B[i]);
}
//Поискобратногопути
cout
printf("%d",c);
h=c-1;
int b=B[c-1];
while(b>0)
{
for(i=0;i
if((A[i][h]==1)&&(B[i]==B[h]-1))
{
cout
printf("%d",i+1);
h=i;
b--;
}
}
cout
}
else
{
cout
}
delete A,B;return 0;
}
Примерывыполнения программы:
1.
/>
2.
/>
3.
/>
Использованнаялитература:
1. «Теория графов».Методические указания по подготовке к контрольным работам по дисциплине«Дискретная математика». Сост.: Н.И. Житникова, Г.И. Федорова, А.К. Галимов. — Уфа, 2005 -37 с.
2. Курс лекций подискретной математике Житникова В.П.
3. «Самоучитель С++»,Перевод с англ. –3 изд… – СПб.: БХВ-Петербург, 2005 – 688 с.
4. «Дискретная математика дляпрограммистов», Ф.А.Новиков.
5. «Введение вдискретную математику», Яблонский.
6. «Курс дискретнойматематики», Неферов, Осипова.
7. «Информатика» Л.З.Шауцукова.