На головну

Постановка завдання про максимальний потік

  1. I. ЗАВДАННЯ АРТИЛЕРІЇ
  2. I. Мета і завдання дисципліни
  3. II. Основні завдання та їх реалізація
  4. VII. Шматки ТА ЗАВДАННЯ
  5. А. Умова завдання
  6. А. Умова завдання.
  7. А. Умова завдання.

На мережі з заданими пропускними здатностями дуг потрібно сформувати максимальний за величиною потік  між її витоком і стоком. Цей потік забезпечується призначенням в кожній дузі  величини  переданого нею потоку.

Завдання про максимальний потік в мережі повинна відповідати таким вимогам:

- Сума потоків дуг, що виходять з витоку мережі, повинна дорівнювати сумі потоків дуг, що входять до водостічної труби мережі:

;

- Для вершини , Котра є стоком або витоком, тобто ,  , Кількість одиниць потоку, що входить в вершину, має дорівнювати кількості одиниць потоку, що виходить з неї (тобто потрібно збереження потоку):

;

- Максимальний потік на шляху від витоку  до стоку  визначається тією дугою  , Яка має мінімальну пропускну здатність з усіх дуг, що належать цим шляхом.

Якщо пропускна здатність  дуги  дорівнює йде через неї потоку  (На мережі значення  позначається числом без дужок), то така дуга називається насиченою, А будь-який шлях, в який вона включена, називається насиченим шляхом. потік називається насиченим, Якщо будь-який шлях з витоку  в стік  містить дугу  , для котрої  . Перша частина рішення задачі про максимальний потік якраз і полягає в знаходженні насиченого потоку. Але насичений потік не завжди є максимальним.

За визначенням, потік в мережі буде максимальним, якщо величина цього потоку  буде більше величини будь-якого іншого потоку в цій мережі.

 



Попередня   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   Наступна

Приклад 2.1. | остовне дерева | Приклад 2.2. | Алгоритм Краскала і алгоритм Прима | алгоритм Краскала | алгоритм Прима | алгоритм Дейкстри | Шляхи і цикли Ейлера | Шляхи і цикли Гамільтона. алгоритм Літтла | Рішення завдання комівояжера методом гілок і меж |

© um.co.ua - учбові матеріали та реферати