Определите, может ли поток удовлетворять требованиям узла в направленном ациклическом графике

Question

У меня есть следующая проблема, которую я безуспешно пытаюсь решить:

У меня есть направленный график с узлами требования. В отличие от циркуляции с требованиями, эти узлы требуют не «вычтены» из потока - узлы просто требуют, чтобы был поток прочности k , протекающих через них. График является ациклическим, однако, это не дерево - существуют несколько маршрутов от вышеупомянутых к нижним узлам.

Вопрос в том, может ли поток прочности r может удовлетворить все требования узлов. Конечно, поток с прочностью более чем K может проходить через узел с требованием K . Кроме того, на входном графике нет ограничений емкости.

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

Answer 1

Добавить новый источник $ s '$ и Edge $ (S', S) $ С максимальной и минимальной емкостью $ R $ .

Для каждой вершины $ v $ с предложением $ d $ сделать следующее:

.
• Заменить $ V $ с двумя вершинами $ v_1 $ и $ v_2 $ .
• Заменить все бывшие края $ (u, v) $ с $ (u, v_1) $
• Заменить все прежние края $ (v, u) $ с $ (v_2, u) $ .
• Добавление края $ (v_1, v_2) $ с минимальной емкостью $ d $ .

Проблема теперь эквивалентна проверить, существует ли возможным потоком в сети с минимальными и максимальными краевыми мощностями.

Эта проблема хорошо известна и может быть уменьшена до максимального потока (см., Например, «балансы и псевдословные» в книге Алгоритмы jeff Erickson).

По сути, если $ d $ - сумма всех минимальных емкостей ребер:

.
• Добавить новую вершину Source $ S ^ * $ и новая целевая вершина $ t ^ * $ .
• Добавление края $ (s ^ *, s ') $ с максимальной емкостью $ + \ infly $ $ .

• для каждого края $ (u, v) $ с минимальной емкостью $ c \ neq 0 $ < / span> и максимальная емкость $ C $ , добавьте краю $ (u, t ^ *) $ С емкостью $ C $ , край $ (s ^ *, v) $ с емкостью $ C $ , удалите минимальную емкость от $ (u, v) $ и изменить максимальную емкость $ (u, v) $ на $ cc $ (если $ C $ Был $ + \ Infty $ Тогда новая емкость также $ + \ infty $ ).

• Проверьте, будет ли максимальный поток из $ s ^ * $ на $ t ^ * $ равен $ d $ .