Как рассчитать максимальный поток в графе, который имеет бесконечные возможности

Question

Я хочу реализовать метод, который вычисляет «максимальный поток» на любом графике, включая как минимум одну бесконечную емкость. Я имел обыкновение импортировать библиотеку NetworkX всякий раз, когда есть обработка графа, но, к сожалению, она еще не учитывает неограниченную емкость в соответствии с описанием maximum_flow :

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

Итак, мои вопросы:

• Как просто реализовать Max-Flow с бесконечной емкостью?
• Можно ли адаптировать для этого метод NetworkX?

Любые другие предложения приветствуются.

Спасибо

Answer 1

Предположим, у вас есть сеть потоков, в которой некоторые ребра имеют бесконечную пропускную способность. Есть два возможных варианта:

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

2. В сети не существует пути с бесконечной емкостью. Тогда есть верхняя граница того, сколько общего потока может быть протолкнуто в сети (быстрое доказательство: рассмотрите разрез, сформированный, беря начальный узел и все достижимое краями бесконечной емкости как одну часть разреза, и все остальное как другая часть, тогда максимальный поток ограничен мощностью этого разреза). В этом случае ребра с бесконечной пропускной способностью по существу функционируют как «вы можете протолкнуть столько потоков через это ребро, сколько захотите», но не существует пути потока, который мог бы фактически иметь бесконечный поток через него. Поэтому возьмите каждое ребро с бесконечной емкостью и замените его ребром с огромной, но конечной емкостью (скажем, суммой всех мощностей ребер с конечной емкостью). Теперь максимальный поток в этом измененном графике дает максимальный поток в исходной сети.

Надеюсь, это поможет!