• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Теорема про максимальний потік і мінімальний розріз теорема (Форда – Фолкерсона)

Для будь-якої мережі з одним джерелом S і одним стоком t максимальна величина потоку з S у t дорівнює пропускної спроможності мінімального розрізу що відокремлює S від t. Розглянемо алгоритм рішення задачі про максимальний потік, є рішення в табличній формі.

За допомогою теорії про потоки в мережах зважуються задачі про оптимальний потік. У цьому випадку на ряду з пропускною спроможністю існує середня обумовлена на всіх дугах ,наприклад вартість.

У такій постановці розв'язується транспортна задача: у мережі G (I, U) існує функція x (i, j) U така, що

(9.6)

визначена на

(9.7)

Потік x (i, j), задовольняючий умовам називається оптимальним. У матричній постановці всі пункти I, поділяються на дві категорії: відправлення і призначення, що зв'язані єдиним маршрутом, а пункти однієї категорії не зв'язані між собою. Однак у реальних задачах, крім пунктів виробництва і споживання є перевалочні пункти, не виробляючі і не споживаючі потік, а_i сортувальна станція наприклад може бути зв'язана декількома маршрутами, що проходять через різні пункти мережі.

Читайте також:

1. Базовою для інтегрального числення є така теорема: ТЕОРЕМА 2. Якщо функція неперервна, то для неї існує
2. В залежності від мети та характеру угоди, які лежать в основі випуску векселів, а також їх забезпечення розрізняють комерційні, фінансові та фіктивні векселя.
3. В розрізі окремих груп
4. В розрізі окремих груп
5. В. Друга теорема про розклад.
6. Валютна система - це державно-правова форма організації валютних відносин. Слід розрізняти національну, міжнародну (регіональну) та світову валютні системи (ВС).
7. Вигляд гортані у розрізі для демонстрації серединної перснеподібної зв’язки
8. Визначений інтеграл, як границя інтегральної суми. Теорема існування. Геометричний зміст визначеного інтеграла.
9. Виклад запиту видатків/ надання кредитів за бюджетною програмою в розрізі економічної класифікації/ класифікації кредитування.
10. Вихідний потік вимог
11. Відтворення основних засобів виробничого характеру –це процес безперервного їх оновлення. Розрізняють просте і розширене відтворення.
12. ВІКОВІ КОНТИНГЕНТИ НАСЕЛЕННЯ УКРАЇНИ В РОЗРІЗІ СТАТІ станом на 01.01.89 та 01.01.99, % до підсумку

Переглядів: 909