Міністерство освіти і науки України Національний університет “Львівська політехніка” Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Звіт про виконання лабораторної роботи №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(); }