![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Постановка задачі. Розглянемо граф (див. л.р
Розглянемо граф (див. л.р. № 1) G={N, A}, де N - множина вузлів, A - множина дуг. Граф G має одне джерело s і один стік t. Дуги (i, j) мають обмежену пропускну здатність
де
Величина потоку з джерела не обмежена; у кожному проміжному вузлі виконується умова збереження потоку.
Задача полягає в визначенні таких дугових потоків, щоб загальний потік з джерела s в стік t був максимальним:
Задача вирішується з допомогою ітераційної процедури розстановки позначок вузлів. Кожна позначка вказує величину потоку та його джерело й може бути як позитивною, так і негативною.
gi , gj - кількість одиниць потоку Позитивна позначка збільшує потік по дузі bij, але так, щоб сумарний потік не перевищив Вузли помічаються послідовно від 1 до n. Якщо вузол На кожної ітерації джерело помічається позначкою Алгоритм закінчує роботу, якщо жоден вузол мережі вже не може бути позначений з джерела.
|