Міністерство освіти та науки України Національний університет «Львівська політехніка» Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Лабораторна робота №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 Висновок: сьогодні в мене була можливість детальніше в практичному відношенні засвоїти тему по знаходженню різних шляхів в графах за допомогою засобів ЕОМ. Виконуючи цю нелегку лабораторну роботу я освоїв навички використання алгоритму Форда-Фалкірсона та зумів запрограмувати його засобами мови С++. Таким чином я підсумував вивчення графів – знаходження максимального потоку в транспортній мережі для мене тепер не проблема.