Le flux maximum avec des bords mutuellement exclusifs peut-il être réduit au problème standard du flux maximum?

Question

Je travaille avec un réseau de flux comme les suivants:

La source S a quatre bords, chacun avec la capacité 1, vers les nœuds A, B, C et D. tous, tous, B, C et D ont des bords à deux autres nœuds, x et y, également avec la capacité 1 1 . X et Y ont tous deux des bords avec une capacité 4 à l'évier t.

En règle générale, cela aurait de nombreuses solutions: toutes les façons de diviser A, B, C et D entre X et Y. Dans la version modifiée, je dois choisir X ou Y. Si le flux sur (x, t )> 0, le flux sur (y, t) doit être 0, et vice versa. Il n'y a donc que deux solutions, envoyant les 4 unités de flux à travers X ou à travers Y.

Je me demande s'il existe un moyen de réduire cette contrainte au flux maximum standard afin que je puisse simplement exécuter Ford-Fulkerson sur un graphique modifié. Cela, ou si cela est fondamentalement plus difficile et est un isomorphisme d'un problème différent.

Dans des versions plus simples comme celle que j'ai disposée au-dessus, vous pouvez simplement réduire la décision à un problème où vous n'avez que S, T et les nœuds x et y et je dois envoyer 1 unité de flux à travers le réseau, mais je suis Aux difficultés avec le cas général où nous avons deux bords x et y, dont un seul est autorisé à faire passer non nulle dans la solution.