Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Теорія графів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Математика
Група:
ПМ-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();
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора