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

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

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

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

Рік:

2015

Тип роботи:

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

Предмет:

Математика

Група:

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

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

2015

Коментарі

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

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

поділитись