Поиск максимального потока в графе

Одной из наиболее важных задач в теории графов является задача определения максимального потока, протекающего от некоторой вершины S графа (истока) к некоторой конечной вершине t (стоку). При этом каждый дуге (x_i, x_j) графа G приписана некоторая пропуская способность C_ij, и эта пропуская способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача и её варианты возникают во многих практических приложениях, например, при определении максимальной интенсивности транспортного потока между двумя пунктами по карте дорог, представленных графом. Решая эту задачу, можно указать также ту часть сети дорог, которая «насыщена» и образует «узкое место» в отношении потока между двумя указанными концевыми пунктами.

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