Значение сильной двойственности между максимальным потоком и минимальным вырезом

Question

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

Answer 1

Как объясняется в статье this Статья в Википедии, проблема Max-Flow и проблема Min-Cut могут быть сформулированы как двойные линейные программы. Поскольку обе линейные программы возможны, двойственность можно рассматривать как частный случай duality of linear programs.