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

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

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

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

(9.6)

визначена на

(9.7)

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Прикладні задачі теорії графів для транспортних систем	\|	Використання енергоносіїв та енергозберігаючі технології на транспорті

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.