Найти максимальный поток в любой сети по заданному алгоритму

Question

Вы можете помочь мне решить следующую проблему?:

Предположим, у нас есть алгоритм для решения проблемы максимального потока в сети потока, в которой степень каждого узла не превышает 2. Мне нужно показать, как использовать этот алгоритм для решения проблемы максимального потока в любой сети.

Если это повторение, пожалуйста, перенаправьте меня на соответствующие ответы.

Спасибо вам всем

Answer 1

Действительно возможно преобразовать график таким образом, чтобы степень выхода каждого узла была не больше 2, а максимальный поток в преобразованном графе был равен максимальному потоку в исходном графе.

Одно из таких преобразований описано ниже. Предположим, что у нас есть узел, степень выхода которого больше 2. Затем мы можем добавить столько промежуточных узлов, сколько выходной степени этого узла, и соединить их так, как показано на следующем рисунке.

Бесконечные ребра емкости гарантируют, что мы можем послать тот же поток, что и изначально, из A в любой из его преемников. Края от X узлы для B узлы гарантируют, что мы не сможем отправить поток больше, чем это было изначально возможно.

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