Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Знаходження шляхів графа
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Математика
Група:
ПМ-21
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Інститут прикладної математики
та фундаментальних наук
Кафедра прикладної математики
Лабораторна робота №2
«Знаходження шляхів графа»
Тема: знаходження шляхів в графі.
Мета: дати можливість студентам детальніше в практичному відношенні засвоїти тему по знаходженню різних шляхів в графах за допомогою засобів ЕОМ.
Теоретичні відомості:
Транспортна сітка є сукупністю двох об’єктів
1) зв’язного графа з такими властивостями:
в графі відсутні петлі
в графі існує одна і тільки одна вершина така, що множина .
2) цілочисельної невід’ємної функції , заданої на множині дуг графа .
Вершина називається входом сітки, вершина – виходом. Значення на дузі називається пропускною здатністю дуги.
3) Нехай – множина дуг, що заходять у вершину , а – множина дуг, які виходять із вершини . Цілочисельна невід’ємна функція , задана на множині дуг графа називається потоком, якщо вона задовольняє таким умовам:
а)
б)
Із а) випливає, що .
Величина називається величиною потоку і позначається .
Алгоритм Форда – Фалкерсона (для знаходження потоку найбільшої величини).
10 Перенумерувати довільним чином вершини сітки відмінні від і .
20 Побудувати довільний потік на транспортній сітці (наприклад покласти ).
30 Розглянути шляхи, що з’єднують вхід сітки з виходом , якщо потік повний – перейти до пункту 40. Іншому випадку розглянути шлях , що з’єднує з , всі дуги якого ненасичені. Побудувати новий потік :
Повторити увесь процес до одержання повного потоку .
Присвоїти цілочисельні мітки вершинам сітки і знаки (+) або (-) дугам по правилах:
а) входу присвоїти мітку 0,
б) якщо вершина одержала деяку мітку, а – ще не помічена вершина, то вершині , такій, що , присвоїти мітку , а дузі знак (+); вершині , такій, що , присвоїти мітку , а дузі знак (-); інші вершини і дуги мітки і знаку не отримують.
в) повторяти процес, описаний в 40(б) до тих пір, поки не виявиться, що присвоїти мітку або знак новій непоміченій вершині або дузі неможливо. Якщо в результаті процесу вершина не одержить мітки, то потік володіє найбільшою величиною. В іншому випадку перейти до пункту г).
г) розглянути послідовність відмічених вершин , кожна з яких має мітку, що дорівнює номеру наступної вершини, і послідовність дуг (необов’язково шлях), що з’єднує послідовні вершини із . Побудувати новий потік таким чином:
і перейти до п.4.
Завдання:
Скласти програму знаходження максимального потоку у сітці заданої таким чином:
01
12
23
15
05
06
76
57
68
78
37
34
56
48
49
89
4z
9z
10
11
8
7
8
9
9
11
10
4
5
17
18
20
21
19
20
23
(Варіант 13)
Код програми(С++):
#include<stdio.h>
#include<conio.h>
#define n 11
int C[n][n], N[n], i, j, F[n][n], T[n][n], p;
int Vvid(int &v);
void First(int v);
void Second(int v);
int Potik(int v);
void main()
{
int v;
printf("Algorutm Forda-Falkirsona.");
if (Vvid(v))
{
Second(v);
printf("\nMaksumal'nuj potik transportnoji merezhi = %d\n",Potik(v));
}
getch();
}
int Vvid(int &v)
{
int i, j, k;
char *fname = "Potik.txt";
FILE *F;
if((F = fopen(fname, "r")) == NULL)
{
puts("File not found");
return 0;
}
fscanf(F, "%d",&v);
if(v > n) v = n;
while(!feof(F))
{
fscanf(F, "%d %d %d", &i, &j, &k);
C[i][j] = k;
}
fclose(F);
for(i = 0; i < n; i++)
{
puts("\n");
for(j = 0; j < n; j++)
if (C[i][j] / 10 == 0) printf("%d ", C[i][j]);
else printf("%d ", C[i][j]);
}
return 1;
}
void First(int v)
{
for(int i = 1; i < v; i++) N[i] = -1;
N[0] = 0;
for(p = 1; p; )
{
p = 0;
int i, j;
for(i = 0; i < v; i++)
if(N[i] == -1)
continue;
else
for(j = 0; j < v; j++)
{
if(N[j] != -1)
continue;
if(C[i][j] && (F[i][j] < C[i][j]))
{
N[j] = i;
T[i][j] = 1;
p = 1;
}
if(C[j][i] && F[j][i])
{
N[j] = i;
T[j][i] = -1;
p = 1;
}
}
}
}
void Second(int v)
{
int i;
do
{
First(v);
if(N[v-1] == -1) return;
for(i = v - 1; i; i = N[i])
F[N[i]][i] += T[N[i]][i];
}
while(N[v-1] != -1);
}
int Potik(int v)
{
int MaxPotik = 0;
for(int i = 0; i < v; i++) MaxPotik += F[0][i];
return MaxPotik;
}
Результати програми:
Algorutm Forda-Falkirsona.
0 10 0 0 0 8 9 0 0 0 0
0 0 11 0 0 7 0 0 0 0 0
0 0 0 8 0 0 0 0 0 0 0
0 0 0 0 17 0 0 5 0 0 0
0 0 0 0 0 0 0 0 20 21 20
0 0 0 0 0 0 0 11 0 19 0
0 0 0 0 0 0 0 0 10 0 0
0 0 0 0 18 0 9 0 4 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 23
0 0 0 0 0 0 0 0 0 0 0
Maksumal'nuj potik transportnoji merezhi = 18
Висновок: сьогодні в мене була можливість детальніше в практичному відношенні засвоїти тему по знаходженню різних шляхів в графах за допомогою засобів ЕОМ. Виконуючи цю нелегку лабораторну роботу я освоїв навички використання алгоритму Форда-Фалкірсона та зумів запрограмувати його засобами мови С++. Таким чином я підсумував вивчення графів – знаходження максимального потоку в транспортній мережі для мене тепер не проблема.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора