Знаходження потоку найбільшої величина. Лабораторна робота з Дискретна математика. Робота № 527777

Перехід до торгівельного партнера Binance

Знаходження потоку найбільшої величина

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра СКС

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

Рік:

2015

Тип роботи:

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

Предмет:

Дискретна математика

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки Національний університет “Львівська політехніка” Кафедра СКС / Звіт з лабораторної роботи № 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. Індивідуальне завдання Скласти програму знаходження потоку найбільшої величини, згідно з алгоритмом Форда-Фалкерсона і знайти такий потік.

Лабораторна робота Дискретна математика

fake_fake

27.03.2016 18:03-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись