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