Міністерство освіти і науки Національний університет “Львівська політехніка” Кафедра СКС / Звіт з лабораторної роботи № 3 з дисципліни: “Дискретна математика” на тему: “Знаходження потоку найбільшої величина” Теоретичні відомості Алгоритм Фолда-Фалкерсона для знаходження потоку найбільшої беличини Послідовність алгоритму Шукаємо довільний шлях з витоку до стоку. Якщо такого немає, то видаємо значення максимальної пропускної спроможності і алгоритм завершується. Знаходимо на обраному шляху ребро з мінімальною пропускною здатністю. Додаємо значення цього ребра до пропускної спроможності, яка на початку виконання алгоритму дорівнює 0. Віднімаємо з усіх значень ребер шляху, значення мінімального ребра цього шляху. При цьому значення даного ребра зводиться до 0 і його вже не можна враховувати в подальшому. Далі продовжуємо з кроку 1. Приклад проходження алгоритму Розглянемо алгоритм Форда-Фалкерсона на прикладі графа зображеної на Мал. 1. Припустимо, що наш витік буде в 1 вузлі, а стік в 4 вузлі. На початку пропускна здатність дорівнює 0 (P = 0). Припустимо, ми знайшли шлях з витоку 1 в стік 4 через вершини 2 і 3, тобто весь шлях можна записати як: 1–>2–>3–>4. На цьому шляху мінімальне ребро з'єднує вершини 2 і 3, а його значення – 5. Збільшуємо пропускну спроможність на 5 (Р = 0 + 5 = 5). Віднімаємо 5 зі значень ребер, що з'єднують вершини 1 і 2, 2 і 3, 3 і 4. З вихідного графа у нас випадає ребро, яке з'єднувало вершини 2 і 3. Таким чином, ми отримуємо граф зображений на Мал. 2. У отриманому графі знову шукаємо довільний шлях з витоку 1 в стік 4. Припускаємо, що шуканий нами шлях: 1–>2–>5–>4, в якому мінімальне ребро з'єднує вершини 2 і 5, а його значення – 6. Збільшуємо пропускну здатність на 6 (P = 5 + 6 = 11). Віднявши 6 зі значень усіх ребер шляху, бачимо, що випадає ребро 2–>5. Отримуємо граф зображений на Мал. 3. Наступним кроком, в отриманому графі знаходимо шлях: 1–>6–>5–>4, на якому мінімальне ребро 1–>6 дорівнює 7, тоді пропускна здатність: (P = 11 + 7 = 18). Віднімаємо з ребер даного шляху 6, при цьому випадає ребро 1–>6 і граф розпадається на дві компоненти (див. Мал. 4). Таким чином, ми вже не можемо знайти шлях з витоку 1 в стік 4, адже вони є складовими двох не поєднаних між собою ребрами компонент, і вважаємо алгоритм завершеним. Отримуємо кінцеву максимальну пропуснну здатність – 18. Індивідуальне завдання Скласти програму знаходження потоку найбільшої величини, згідно з алгоритмом Форда-Фалкерсона і знайти такий потік.