I tried using the Ford Fulkerson algorithm with the following question:
The result I got was 25:
I've been told that my solution is not correct. I was not told what the solution was however. What am I missing here?
I also watched this video on Youtube: https://www.youtube.com/watch?v=J0wzih3_5Wo At around 11:38, he speaks about using the reverse flows but I couldn't find an opportunity to use it here.
A fundamental theorem of graph theory flow is the Max-Flow/Min-Cut theorem, which states that if you can find a cut whose capacity is equal to any valid flow, then the flow is a maximum and the cut is a minimum.
A cut is a partition of the vertexes of the graph into 2 sets, where the sink is in one set and the source is in the other, and both sets are connected. The flow of a cut is the flow from the sum of the capacities from the vertexes in the source set to the vertexes in the sink set.
Here is the cut, with the red nodes on one side of the cut and the blue nodes on the other side of the cut (I cheated an found it with pure enumeration of all valid cuts, hehe, don't have to check more than $2^8$). Anyway, you can work backward from this cut to find a flow that satisfies the cut given here:
The cut capacity (given in purple) is $9 + 1 + 16 = 26$, and if you work at it you'll see that there is also a capacity that meet that.
Only read the following hint if you still are having trouble:
This might sound like a troublesome algorithm to learn, but to me it is quite an amazing thing that such an algorithm has a polytime solution. I assure you that learning this algorithm is much more pleasant than trying to figure it out ^_^