Знаходження шляхів графа. Лабораторна робота з Математика. Робота № 110140

Знаходження шляхів графа

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

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

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

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Математика

Група:

ПМ-21

Завантажити

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

Міністерство освіти та науки України Національний університет «Львівська політехніка» Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Лабораторна робота №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 Перевірка: Висновок: я навчився знаходити матрицю числа шляхів в графі що відповідають трійці чисел α, β, γ.

Лабораторна робота Математика

2015

Коментарі

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

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

поділитись