Задолго до создания первых электронных компьютеров, в 1936 году, 24-летний британский математик Алан Тьюринг придумал абстрактную вычислительную машину. Эта мысленная конструкция стала абсолютным математическим мерилом того, что в принципе можно вычислить алгоритмическим путем, а что — нельзя. Машина Тьюринга является краеугольным камнем теоретической информатики и дискретной математики.

Существует особый класс графов, который естественным образом описывает системы, где объекты разделены на две непересекающиеся группы, и связи возможны только между представителями разных групп. Студенты и университеты, таксисты и пассажиры, рабочие и станки, покупатели и товары. В дискретной математике такие структуры называются двудольными графами. Анализ таких графов позволяет решать сложнейшие логистические и экономические задачи распределения ресурсов.

Одной из классических задач дискретной оптимизации на графах является задача о максимальном потоке. Представьте сеть трубопроводов разного диаметра, систему городских автомобильных дорог с разной пропускной способностью или компьютерную сеть маршрутизаторов. Как пропустить максимальный объем жидкости, машин или гигабайт данных от источника к потребителю так, чтобы ни на одном участке не превысить лимит? Ответом на этот вопрос является знаменитый алгоритм Форда-Фалкерсона.