Міністерство освіти та науки України Національний університет «Львівська політехніка» Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Лабораторна робота №2 «Знаходження шляхів графа» Тема: знаходження шляхів в графі. Мета: дати можливість студентам детальніше в практичному відношенні засвоїти тему по знаходженню різних шляхів в графах за допомогою засобів ЕОМ. Теоретичні відомості: В практиці дуже часто приходиться мати справу з задачами знаходження шляхів і контурів певних графів. Цю задачу доцільно розділити на два типи, а саме: 1) кількісна оцінка шляхів графа; 2) якісна оцінка шляхів графа (деякі екстремальні задачі на графах). Саме до першого типу відноситься задача знаходження шляхів, що відповідають трійці цілих невід’ємних чисел α, β, γ. Якщо в графі G(x) через
позначити число дуг, що йдуть з вершини
в вершину
, то матриця
з n-стрічками і n-стовпцями називаэться матрицею суміжності вершин графа G(x). Число шляхів, які відповідають даній трійці невід’ємних цілих чисел. Говорять, що шлях
відповідає трійці α, β, γ чисел, якщо на цьому шляху є дві однакові вершини
та
,
для яких
. Тут
– означає довжину шляху M між точками
. Якщо A – матриця суміжності графа G, а
– число шляхів, які відповідають трійці чисел α, β, γ і які йдуть від
до
, то
де
– означає матрицю, головна діагональ якої така ж, що й в
, а всі інші елементи – нулі. Завдання: знайти число шляхів, які відповідають деякій трійці невід’ємних чисел α, β, γ для матриці суміжності
. Код програми(С++): #include <iostream> #define m 6 using namespace std; void Out_Matrix(int A[m][m], int n); void Null_Matrix(int A[m][m]); void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m void Pow_Matrix(int A[m][m], int As[m][m], int s void D_Matrix(int A[m][m], int B[m][m void Make_Matrix(int A[m][m], int B[m][m], int a, int b, int c); int M[m][m] = {1,1,0,1,1,1, 0,0,1,1,1,0, 1,0,1,0,0,0, 1,0,0,1,1,0, 1,1,0,0,1,1, 0,1,0,1,0,1}; void main() { cout<<"Znahodzhennja 4usla shljahiv, jaki vidpovidajyt' dejakij trijci"<<endl <<"nevidjemnuh 4usel a, b, c dlja matruci symizhnosti:"; Out_Matrix(M, m); int a, b, c, R[m][m]; cout<<"Vvedit' 4usla a, b, c:"; go: cin>>a>>b>>c; if ((a < 0)||(b < 0)||(c < 0)) {cout<<"4usla povuni bytu nevidjemni!"; goto go;}; Make_Matrix(M, R, a, b ,c); Out_Matrix(R, m); } //Îïèñ ôóíêö³é void Out_Matrix(int A[m][m], int n) { for(int i = 0; i < n; i++) { cout<<endl; for(int j = 0; j < n; j++) cout<<A[i][j]<<" "; } cout<<endl; } void Null_Matrix(int A[m][m]) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) { A[i][j] = 0; } } void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m]) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) { C[i][j] = 0; for(int k = 0; k < m; k++) C[i][j] += (A[i][k] * B[k][j]); } } void Pow_Matrix(int A[m][m], int As[m][m], int s) { int R[m][m]; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if (i == j) As[i][j] = 1; else As[i][j] = 0; if (s != 0) for(int k = 0; k < s; k++) { Multiply_Matrix(A, As, R); for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) As[i][j] = R[i][j]; } } void D_Matrix(int A[m][m], int B[m][m]) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if (i!=j) B[i][j] = 0; else B[i][j] = A[i][j]; } void Make_Matrix(int A[m][m], int B[m][m], int a, int b, int c) { int R1[m][m], R2[m][m], dR2[m][m], R3[m][m]; Pow_Matrix(A, R1, a); Pow_Matrix(A, R2, b); Pow_Matrix(A, R3, c); D_Matrix(R2, dR2); Multiply_Matrix(R1, dR2, R2); Multiply_Matrix(R2, R3, B); } Результати програми: Znahodzhennja 4usla shljahiv, jaki vidpovidajyt' dejakij trijci nevidjemnuh 4usel a, b, c dlja matruci symizhnosti: 1 1 0 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 Vvedit' 4usla a, b, c: 0 1 2 3 3 1 4 4 3 0 0 0 0 0 0 2 1 1 1 1 1 3 2 0 2 3 2 2 3 1 3 3 3 1 1 1 3 2 1 Перевірка:





Висновок: я навчився знаходити матрицю числа шляхів в графі що відповідають трійці чисел α, β, γ.