Билет 7 (Максимальный поток, минимальный разрез, алгоритм Форда-Фалкерсона)

• Рассматривается задача нахождения максимального потока в транспортной сети.  

• Используется алгоритм Форда-Фалкерсона.  

• Максимальный поток достигается, если пропускная способность потока через разрез максимальна.  

• Начинается с помечивания вершин.  

• Каждая вершина имеет метку, состоящую из двух частей: откуда пришла метка и величина потока на этой метке.  

• Начинаем с истока и помечаем смежные вершины.  

• Если величина потока на дуге меньше пропускной способности, вершина получает метку.  

• Метка включает минимум между меткой предыдущей вершины и разницей между пропускной способностью и величиной потока на дуге.  

• Если величина потока на дуге больше нуля, вершина получает метку, вычитая минимум из метки предыдущей вершины и величины потока.  

• Алгоритм останавливается, если больше не удается пометить ни одну вершину.  

• Если сток не помечен, алгоритм останавливается.  

• Если все дуги забиты, алгоритм останавливается и находит минимальный разрез и максимальный поток.  

• Если сток помечен, изменяем поток.  

• Правило изменения потока: прибавляем сигму ко всем дугам, ведущим к стоку.  

• Пример: если сток получил метку м плюс сигма, прибавляем сигму ко всем дугам, ведущим к стоку.  

• Прибавляем сигму к пропускной способности дуги и переходим к следующей вершине.  

• Если метка вершины равна и плюс икс, прибавляем сигму к дуге и переходим к следующей вершине.  

• Если метка равна и минус икс, вычитаем сигму из пропускной способности дуги и переходим к следующей вершине.  

• Алгоритм останавливается, когда доходит до истока.  

• Если сток не может быть помечен, алгоритм завершает работу и строит максимальный поток.  

• Максимальный поток строится через минимальный разрез, где во множество икс уходят вершины, которые были помечены на последнем шаге.  

• Построен максимальный поток.  

• Минимальный разрез имеет минимальную пропускную способность.  

• Теорема доказывает, что вычисленный поток имеет максимальную величину.  

• Величина потока через разрез равна сумме величин потока из дуг, пересекающих разрез.  

• Пропускная способность разреза равна сумме пропускных способностей дуг, пересекающих разрез.  

• На последнем шаге алгоритма все дуги, пересекающие разрез, имеют одинаковую пропускную способность.  

• Если сумма величин потока не равна нулю, алгоритм продолжает работу.  

• Если сумма равна нулю, величина потока совпадает с пропускной способностью.  

• Величина потока равна пропускной способности минимального разреза.  

• Величина потока через разрез равна пропускной способности разреза.  

• Максимальный поток совпадает с пропускной способностью минимального разреза.  

• Теорема о существовании максимального потока в любой сети доказывается очевидно.  

• Начинаем с вершины С, помечаем её меткой С+1.  

• Переходим к вершине 1, помечаем её меткой 1+.  

• Вершина 2 получает метку 1+ и минимум между метками предыдущей вершины и пропускной способностью.  

• Помечаем сток меткой 2+.  

• Увеличиваем поток на единицу, получаем 3, 2, 4, 5.  

• Переходим к следующему шагу, помечаем вершину 3 меткой 3+.  

• Проверяем правильность пометки вершин.  

• Исправляем ошибки, помечаем вершины правильно.  

• Переходим к следующему шагу, помечаем вершину 4 меткой 4+.  

• Помечаем вершину 5 меткой 5+.  

• Проверяем, что поток не нулевой, помечаем вершину 2 меткой 3-.  

• Увеличиваем поток на единицу, получаем 3, 1, 4.  

• Проверяем возможность пометки вершин.  

• Появляется разрез, вершина С отлетает в множество X.  

• Считаем величину потока и пропускную способность, поток максимальный.  

• Если бы пропускная способность была другой, можно было бы пометить другие вершины.  

• Разрез имел бы другой вид.  

• Завершаем пример, благодарим за внимание и желаем удачи.