"justify"> 3. Кожній дузі приписуються значення
С (u) > = 0, u ГЋ U, де
Х 0 , Х n < span align = "justify"> - відповідно вхід і вихід мережі (початкова і завершальна операції технологічного процесу);
С (u) - пропускна здатність дуги В«uВ» (максимальна продуктивність технологічного ділянки).
Алгоритм Форда-Фалкерсона для відшукання максимального потоку в заданій транспортної мережі грунтується на наступних теоремах:
Теорема 1
Нехай m = (Х 0 , Х i1 , ... Х In , Х N ) - шлях, що з'єднує вхід Х 0 з виходом Х N транспортної мережі. Якщо всі дуги цього шляху ненасичені, то можна збільшити потік на величину d * = min ( d (U) = C (U ) -? ( < span align = "justify"> U)), не порушуючи властивостей транспортної мережі.
Теорема 2
Якщо e * > < span align = "justify"> 0, то збільшуючи на e * потік в кожній попутної дузі з Х < span align = "justify"> 0 в Х N і зменшуючи на e * потік в кожній зустрічній дузі, ми збільшуємо потік в ланцюзі.
Теорема 3
Якщо не існує ланцюга n від Х 0 до Х N з e * > 0, то потік ? в мережі не можна більше збільшити, тобто він максимальний.
