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