Многие задачи информатики можно представить в виде графа, состоящего из узлов и связей между ними. Примерами являются проблемы с сетевыми потоками , которые включают транспортировку товаров или материалов по сети, такой как железнодорожная система.
Вы можете представить сетевой поток в виде графа, узлы которого являются городами, а дуги — железнодорожными линиями между ними. (Они называются потоками , потому что их свойства аналогичны свойствам воды, протекающей по сети труб.)
Ключевым ограничением сетевых потоков является то, что каждая дуга имеет пропускную способность — максимальное количество, которое может быть передано по дуге за фиксированный период времени.
Задача о максимальном потоке состоит в том, чтобы определить максимальное общее количество, которое может быть передано по всем дугам в сети с учетом ограничений пропускной способности.
Первым, кто занялся этой проблемой, был русский математик А. Н. Толстой в 1930-х годах. На карте ниже показана фактическая сеть железных дорог, для которой он хотел найти максимальный поток.
OR-Tools предоставляет несколько решателей для задач сетевого потока в своих графовых библиотеках.
В следующих разделах представлены примеры проблем с сетевыми потоками и показано, как их решить: