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

Question

Как я могу найти максимальный поток в этом неориентированном графике? Кто-нибудь может показать шаг?

Answer 1

Существует алгоритм, называемый алгоритмом Форда-Фулкерсона, который дает максимальный поток сети потоков за полиномиальное время, вы можете найти его в книге "Разработка алгоритмов" Клейнберга и Тардоса или даже в CLRS.

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