Теорія графів. Звіт про виконання лабораторної роботи з Математика. Робота № 110125

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

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра прикладної математики

Інформація про роботу

Рік:

2015

Тип роботи:

Звіт про виконання лабораторної роботи

Предмет:

Математика

Група:

ПМ-21

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет “Львівська політехніка” Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Звіт про виконання лабораторної роботи №2 на тему: “Теорія графів ” Теоретичні відомості: Якщо в графі G(х) через позначити число дуг, що йдуть з вершини у вершину , то матриця А= {} з n – стрічками та n –стовпцями називається матрицею суміжності вершин графа G(x). Heхай і відповідають матрицям суміжності та ,тоді матрці + відповідають граф G(х)= + , який отримується об’єднанням дуг графів та на цій же множині вершини . Матриці суміжності відповідає мультиграф побудований таким чином : в вершину з вершини йде стільки дуг, скільки існує різних шляхів в з і складених із двох дуг, перша з яких належить графу , а друга . Ранг елемента − параметр, що дозволяє розподілити елементи графа в порядку їх вагомості Вагомість елемента тут визначається лише кількістю зв’язків з даного елемента з іншими. Характеризуючи значимість елемента рангом − структурним параметром, можна сказати, зо чим більший ранг елемента , тим більше він зв’язаний з іншими елементами графа. Правило Таррі. Щоб знайти шлях із вершини в в симетричному (зв’язному ) графі G(х) , досить дотримуватись правила : ніколи не проходити двічі по одному і тому ж коридору і тому ж напрямку; знаходячись у вершині не вибирати того ребра ,яку привело у вершину в перший раз, якщо є можливість іншого вибору. Транспортна сітка Т є сукупністю двох об’єктів: Зв’язного графа G= (X,) з властивостями : В графі відсутні петлі В графі G існує одна і лише одна вершина така, що множина =Ǿ. В графі G існує одна і лише одна вершина , така ,що множина =Ǿ. Цілочисельною невід’ємною функцією С(u) , заданою на множині дуг графа G. Вершина називається входом сітки, вершина - виходом. Значення функції С(u) на дузі u називається пропускною здатністю дуги. Нехай U- множина дуг, що заходять у вершину , U- множина дуг, що виходять з множини . Цілочисельна невід’ємна функція , задана на множині дуг графа G, називається потоком ,якщо вона задовольняє такі умови: = (,) С(u) Величина - називаться величиною потоку і позначається . Код програми: #include<iostream.h> #include<conio.h> class dijkstra { private: int graph[26][26]; int set[26],predecessor[26],mark[26],pathestimate[26]; int source,target; int num_of_vertices; public: int minimum(); void read(); void initialize(); void printpath(int); void algorithm(); void output(); }; void dijkstra::read() { num_of_vertices =26; int myGraph[26][26]={ {0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0}, {1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1}, {0,1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0}, {0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0}, {0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, {0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0}, {0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0}, {0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0}, {1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0}, {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0}, {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0} }; for (int i=0;i<26;i++) for (int j=0;j<26;j++) graph[i][j]=myGraph[i][j]; cout<<"\nenter the source vertex\n"; cin>>source; cout<<"\nenter the target vertex\n"; cin>>target; } void dijkstra::initialize() { for(int i=0;i<num_of_vertices;i++) { mark[i]=0; pathestimate[i]=999; predecessor[i]=-1; } pathestimate[source]=0; } void dijkstra::algorithm() { initialize(); int count=0; int i; int u; while(count<num_of_vertices) { u=minimum(); set[count++]=u; mark[u]=1; for(i=0;i<num_of_vertices;i++) { if(graph[u][i]>0) { if(mark[i]!=1) { if(pathestimate[i]>pathestimate[u]+graph[u][i]) { pathestimate[i]=pathestimate[u]+graph[u][i]; predecessor[i]=u; } } } } } } void dijkstra::printpath(int i) { cout<<endl; if(i==source) { cout<<source; } else if(predecessor[i]==-1) cout<<"no path from "<<source<<" to "<<i; else { printpath(predecessor[i]); cout<<".."<<i; } } void dijkstra::output() { printpath(target); if(pathestimate[target]!=999) cout<<"->("<<pathestimate[target]<<")\n"; cout<<endl; } int dijkstra::minimum() { int min=999; int i,t; for(i=0;i<num_of_vertices;i++) { if(mark[i]!=1) { if(min>=pathestimate[i]) { min=pathestimate[i]; t=i; } } } return t; } void main() {clrscr(); dijkstra s; s.read(); s.algorithm(); s.output(); getch(); }

Звіт про виконання лабораторної роботи Математика

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись