0
$\begingroup$

I have the following graph : What is in red is the demand/supply.

When positive -> Supply

When negative -> Demand

When $0$ -> Transfer

On each arc there is residual capacity/given flow.

The goal here is to find the maximum amount of flow we can pass through this graph and afterwards minimize the cost.

graph

My first instinct is to create a super-source et super-sink. I get this graph : graph with super-source and super-sink

I also have the following policy that I have to respect while trying to find an augmenting path:

1.If you have a choice between S1...S2 always choose the one with the lowest number (here it's 1 so S1 will be chosen to be part of the augmenting path). Same thing for T1...T2 and D1...D2.

  1. Between a node with Sx and a node Tx choose Tx first if you can.

  2. Between a node with Tx and a node Dx choose Dx first if you can.

After applying the algorithm I get :

graph with ford-dulkerson algorithm

With this solution I'm supposed to find a partial tree that will be a base solution for the minimal cost flow problem. I'm told that I should find this tree by applying those rules:

  1. Every arc with a flow that is below the capacity is included in the partial tree.

  2. If not all nodes are in the tree add arbitrary arcs to the tree.

However if I follow 1. I get a cycle in my graph because of S1 and S3 is left out.

How do I find the correct partial tree to use? Also, should I remove the super-source and the super-sink? enter image description here

$\endgroup$
6
  • $\begingroup$ Your answer is correct. When it says "tree", that should not be taken too strictly. Every path from source to sink should be cycle-free, that is all. Note that with a single source and single sink, you should expect cycles in the resulting graph. $\endgroup$ – Robby the Belgian Nov 8 '20 at 16:47
  • $\begingroup$ I made a mistake in the last graph by forgetting to include the arc from T2 to D1. However, adding it creates a cycle, right? What am I doing wrong? $\endgroup$ – WindBreeze Nov 8 '20 at 16:50
  • $\begingroup$ It's not a directed cycle, so it's OK. Consider a simple graph with 1 source, 1 sink and two other nodes, arranged in a square, where all edges have capacity 10. Avoiding (undirected) cycles is not always possible. As long as you don't have any directed cycles, it's good. $\endgroup$ – Robby the Belgian Nov 8 '20 at 16:56
  • $\begingroup$ I added a super-source and a super-sink do I remove them or keep them in the final tree? $\endgroup$ – WindBreeze Nov 8 '20 at 17:01
  • $\begingroup$ Personally, I would remove them. That means you will no longer have a tree, but it also means that everything in your solution has a physical meaning. $\endgroup$ – Robby the Belgian Nov 8 '20 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.