문제

I'm working with a flow network like the following:

The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, also with capacity 1. X and Y both have edges with capacity 4 to the sink t.

Typically this would have many solutions: all of the ways you could split up A, B, C, and D between X and Y. In the modified version, I have to pick either X or Y. If the flow on (X, t) > 0, the flow on (Y, t) must be 0, and vice versa. So there are only two solutions, sending all 4 units of flow through X or through Y.

I'm wondering if there is a way to reduce this constraint to the standard max-flow so I can just run Ford-Fulkerson on a modified graph. That, or whether this is fundamentally harder and is an isomorphism of a different problem.

In simpler versions like the one I've laid out above you could just reduce the decision to a problem where you have only s, t, and the nodes X and Y and must send 1 unit of flow through the network, but I'm struggling with the general case where we have two edges X and Y, only one of which is allowed to have nonzero flow through it in the solution.

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top