Задача о максимальном потоке в теории оптимизации и теории графов заключается в нахождении такого потока по транспортной сети, который бы принимал максимальное значение по сравнению с другими допустимыми потоками. 15

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

Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число — пропускная способность этой дуги. 2

Также в терминах задачи о максимальном потоке формулируются многие задачи комбинаторной оптимизации, например, задача поиска наибольшего паросочетания. 4

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